Shortlist 2015, C5¶

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

Concepts : Graphes : degrés, chemins, arbres · Principe des tiroirs · Double comptage · AM-GM et moyennes

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 32 (page 33 du PDF)

Problème 6 de l'OIM 2015

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2015, où il était le problème 6 (jour 2).

Énoncé¶

Consider an infinite sequence \(a_1, a_2, \ldots\) of positive integers with \(a_i \leq 2015\) for all \(i \geq 1\). Suppose that for any two distinct indices \(i\) and \(j\) we have \(i + a_i \neq j + a_j\). Prove that there exist two positive integers \(b\) and \(N\) such that

\[\left| \sum_{i=m+1}^{n} (a_i - b) \right| \leq 1007^2\]

whenever \(n > m \geq N\).

Indices : les idées clés

Graphes : degrés, chemins, arbres (solution 1) : on trace une flèche de \(n\) vers \(n + a_n\) ; chaque entier reçoit au plus une flèche, et les entiers qui n'en reçoivent aucune sont les départs de « rayons » disjoints.
Principe des tiroirs : un intervalle de \(2015\) entiers ne peut pas être rencontré par \(2016\) rayons distincts (solution 1) ; de même \(n + 2016\) éléments distincts ne tiennent pas dans \(\{1, \ldots, n + 2015\}\) (solution 2). Il y a donc au plus \(2015\) entiers non atteints : leur nombre est le \(b\) cherché.
Double comptage (solution 2) : la somme des éléments de l'ensemble \(B_r\) calculée de deux façons exprime \(\sum (a_i - b)\) à l'aide d'un ensemble \(C_r \subseteq \{1, \ldots, 2014\}\) à \(b - 1\) éléments.
AM-GM et moyennes : pour conclure, \((b-1)(2015-b) \leq \left(\frac{(b-1) + (2015-b)}{2}\right)^2 = 1007^2\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et une remarque).

Solution 1¶

On représente les entiers positifs comme une suite de points. Pour chaque \(n\), on trace une flèche partant de \(n\) et pointant vers \(n + a_n\) ; sa longueur est \(a_n\). Comme \(m + a_m \neq n + a_n\) pour \(m \neq n\), chaque entier reçoit au plus une flèche. Certains entiers, comme \(1\), n'en reçoivent aucune : on les appelle points de départ. En partant d'un point de départ et en suivant les flèches, on obtient un chemin infini, son rayon, qui visite une suite strictement croissante d'entiers. Comme chaque flèche a une longueur au plus \(2015\), un rayon de point de départ \(s\) rencontre tout intervalle \([n, n + 2014]\) avec \(n \geq s\).

Supposons par l'absurde qu'il y ait au moins \(2016\) points de départ. Prenons \(n\) plus grand que les \(2016\) premiers. L'intervalle \([n, n + 2014]\), qui ne contient que \(2015\) entiers, est alors rencontré par au moins \(2016\) rayons en des points distincts (les rayons sont disjoints) : c'est absurde (principe des tiroirs). Le nombre \(b\) de points de départ vérifie donc \(1 \leq b \leq 2015\). Soit \(N\) un entier plus grand que tous les points de départ ; montrons que \(b\) et \(N\) conviennent.

Soient \(n > m \geq N\). La somme \(\sum_{i=m+1}^{n} a_i\) est la longueur totale des flèches partant de \(m+1, \ldots, n\). Ces flèches forment \(b\) morceaux de rayons (éventuellement vides). Sur chaque rayon, considérons le premier nombre strictement supérieur à \(m\) ; notons \(x_1, \ldots, x_b\) ces nombres, et \(y_1, \ldots, y_b\) (dans le même ordre) ceux définis de même avec \(n\). Les différences \(y_j - x_j\) sont les longueurs de ces morceaux (éventuellement nulles), donc

\[\sum_{i=m+1}^{n} a_i = \sum_{j=1}^{b} (y_j - x_j), \qquad \text{d'où} \qquad \sum_{i=m+1}^{n} (a_i - b) = \sum_{j=1}^{b} (y_j - n) - \sum_{j=1}^{b} (x_j - m).\]

Chacun des \(b\) rayons rencontre l'intervalle \([m+1, m+2015]\), donc \(x_1 - m, \ldots, x_b - m\) sont \(b\) éléments distincts de \(\{1, \ldots, 2015\}\). De plus, \(m + 1\) n'est pas un point de départ, donc appartient à un rayon : la valeur \(1\) figure parmi ces nombres. Ainsi

\[1 + \sum_{j=1}^{b-1} (j + 1) \leq \sum_{j=1}^{b} (x_j - m) \leq 1 + \sum_{j=1}^{b-1} (2016 - b + j).\]

Le même argument pour \(n\) et \(y_1, \ldots, y_b\) donne

\[1 + \sum_{j=1}^{b-1} (j + 1) \leq \sum_{j=1}^{b} (y_j - n) \leq 1 + \sum_{j=1}^{b-1} (2016 - b + j).\]

Au total, avec AM-GM à la fin :

\[\left| \sum_{i=m+1}^{n} (a_i - b) \right| \leq \sum_{j=1}^{b-1} \big((2016 - b + j) - (j + 1)\big) = (b-1)(2015-b) \leq \left(\frac{(b-1) + (2015-b)}{2}\right)^2 = 1007^2. \qquad \blacksquare\]

Solution 2¶

Posons \(s_n = n + a_n\) pour tout \(n \geq 1\). Par hypothèse, \(n + 1 \leq s_n \leq n + 2015\) et les \(s_n\) sont deux à deux distincts. On étudie l'ensemble

\[M = \mathbb{Z}_{>0} \setminus \{s_1, s_2, \ldots\}.\]

Affirmation. \(M\) a au plus \(2015\) éléments.

Preuve. Sinon, soient \(m_1 < m_2 < \cdots < m_{2016}\) des éléments de \(M\). Pour \(n = m_{2016}\),

\[\{s_1, \ldots, s_n\} \cup \{m_1, \ldots, m_{2016}\} \subseteq \{1, 2, \ldots, n + 2015\},\]

où le membre de gauche est une réunion disjointe de \(n + 2016\) éléments, alors que celui de droite n'en a que \(n + 2015\) : contradiction (principe des tiroirs). \(\square\)

Montrons que \(b = |M|\) et \(N = \max M\) conviennent ; on vient de voir que \(b \leq 2015\). Soit \(r \geq N\). Comme dans la preuve de l'affirmation,

\[B_r = M \cup \{s_1, \ldots, s_r\} \tag{1}\]

est une partie de \([1, r + 2015] \cap \mathbb{Z}\) à exactement \(b + r\) éléments. Par définition de \(M\) et \(N\), on a aussi \([1, r+1] \cap \mathbb{Z} \subseteq B_r\) (un entier \(k \leq r+1\) hors de \(M\) est un \(s_i\) avec \(i \leq k - 1 \leq r\)). Il existe donc un ensemble \(C_r \subseteq \{1, 2, \ldots, 2014\}\) avec \(|C_r| = b - 1\) et

\[B_r = \big([1, r+1] \cap \mathbb{Z}\big) \cup \{r + 1 + x \mid x \in C_r\}. \tag{2}\]

Pour un ensemble fini d'entiers \(J\), notons \(\sum J\) la somme de ses éléments. En calculant \(\sum B_r\) de deux façons, avec (1) et (2) :

\[\sum M + \sum_{i=1}^{r} s_i = \sum_{i=1}^{r} i + b(r+1) + \sum C_r,\]

c'est-à-dire, puisque \(s_i - i = a_i\),

\[\sum M + \sum_{i=1}^{r} (a_i - b) = b + \sum C_r. \tag{3}\]

Soient maintenant \(n > m \geq N\). En écrivant (3) pour \(r = n\) et \(r = m\) et en soustrayant :

\[\sum_{i=m+1}^{n} (a_i - b) = \sum C_n - \sum C_m.\]

Comme \(C_n\) et \(C_m\) sont des parties de \(\{1, \ldots, 2014\}\) à \(b - 1\) éléments, la valeur absolue du membre de droite est maximale quand \(C_m = \{1, \ldots, b-1\}\) et \(C_n = \{2016 - b, \ldots, 2014\}\), ou l'inverse ; elle vaut alors \((b-1)(2015-b)\). Dans tous les cas, par AM-GM,

\[\left| \sum_{i=m+1}^{n} (a_i - b) \right| \leq (b-1)(2015-b) \leq \left(\frac{(b-1) + (2015-b)}{2}\right)^2 = 1007^2. \qquad \blacksquare\]

Remarques¶

Remarque 1 (le tableau noir). On peut visualiser les ensembles \(C_n\) ainsi : on part d'un tableau vide ; à l'étape \(n\), on écrit \(a_n\) au tableau, puis on diminue de \(1\) tous les nombres écrits, et on efface les zéros apparus. Les nombres présents après \(n\) étapes sont distincts et forment l'ensemble \(C_n\). On peut aussi bâtir une solution complète sur cette idée.