Aller au contenu

Shortlist 2020, C4

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Croatia

Concepts : Graphes : degrés, chemins, arbres · Principe extrémal · Sommes, télescopage et transformation d'Abel

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 34 (page 36 du PDF)

Énoncé

The Fibonacci numbers \(F_0, F_1, F_2, \ldots\) are defined inductively by \(F_0 = 0\), \(F_1 = 1\), and \(F_{n+1} = F_n + F_{n-1}\) for \(n \geq 1\). Given an integer \(n \geq 2\), determine the smallest size of a set \(S\) of integers such that for every \(k = 2, 3, \ldots, n\) there exist some \(x, y \in S\) such that \(x - y = F_k\).

Indices : les idées clés
  • Graphe sans cycle : on relie les éléments de \(S\) dont la différence vaut \(F_1, F_3, \ldots, F_{2d-1}\) ; ce graphe à \(d\) arêtes n'a pas de cycle, donc il a au moins \(d + 1\) sommets.
  • Arête la plus longue : dans un cycle, l'arête la plus longue serait plus longue que la somme des autres.
  • Télescopage : \(F_1 + F_3 + \cdots + F_{2m-1} = F_{2m} < F_{2m+1}\).
  • Construction : \(S = \{F_0, F_2, F_4, \ldots, F_{2d}\}\) réalise toutes les différences \(F_1, \ldots, F_{2d}\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (une solution).

Réponse : \(\lceil n/2 \rceil + 1\).

Solution

Minoration. Montrons d'abord que si \(S \subset \mathbb{Z}\) vérifie les conditions, alors \(|S| \geq \frac{n}{2} + 1\). Soit \(d = \lceil n/2 \rceil\), de sorte que \(n \leq 2d \leq n + 1\) ; il s'agit de prouver \(|S| \geq d + 1\). Construisons un graphe dont les sommets sont les éléments de \(S\). Pour chaque \(1 \leq k \leq d\), choisissons deux éléments \(x, y \in S\) tels que \(x - y = F_{2k-1}\) et ajoutons l'arête \((x, y)\). (D'après l'énoncé, un tel couple existe pour tout \(3 \leq 2k - 1 \leq 2d - 1 \leq n\) ; de plus, comme \(F_1 = F_2\), il existe aussi un couple avec \(x - y = F_1\).) Appelons longueur de l'arête \((x, y)\) le nombre \(|x - y|\).

Montrons que ce graphe ne contient pas de cycle. Supposons par l'absurde qu'il contienne un cycle \((x_1, \ldots, x_\ell)\), et que l'arête la plus longue du cycle soit \((x_1, x_\ell)\), de longueur \(F_{2m+1}\). Les autres arêtes \((x_1, x_2), \ldots, (x_{\ell-1}, x_\ell)\) du cycle sont plus courtes que \(F_{2m+1}\) et distinctes, donc leurs longueurs forment une partie de \(\{F_1, F_3, \ldots, F_{2m-1}\}\). C'est impossible, car par télescopage

\[\begin{aligned} F_{2m+1} = |x_\ell - x_1| &\leq \sum_{i=1}^{\ell-1} |x_{i+1} - x_i| \leq F_1 + F_3 + F_5 + \cdots + F_{2m-1} \\ &= F_2 + (F_4 - F_2) + (F_6 - F_4) + \cdots + (F_{2m} - F_{2m-2}) = F_{2m} < F_{2m+1}. \end{aligned}\]

Ainsi le graphe a \(d\) arêtes et aucun cycle ; il a donc au moins \(d + 1\) sommets, c'est-à-dire \(|S| \geq d + 1\).

Construction. Exhibons un ensemble convenable à \(d + 1\) éléments. Soit

\[S = \{F_0, F_2, F_4, F_6, \ldots, F_{2d}\}.\]

Le livret écrit \(\{F_0, F_2, F_4, F_5, \ldots, F_{2d}\}\) ; il faut lire \(\{F_0, F_2, F_4, F_6, \ldots, F_{2d}\}\) (les \(F\) d'indice pair).

Pour \(1 \leq k \leq d\), on a \(F_0, F_{2k-2}, F_{2k} \in S\), avec les différences \(F_{2k} - F_{2k-2} = F_{2k-1}\) et \(F_{2k} - F_0 = F_{2k}\). Ainsi chacun des nombres \(F_1, F_2, \ldots, F_{2d}\) (donc en particulier \(F_2, \ldots, F_n\)) est la différence de deux éléments de \(S\). Cet ensemble à \(d + 1\) éléments convient. \(\blacksquare\)