Shortlist 2009, C7

Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Russia

Concepts : Récurrence et constructions récursives · Principe extrémal · Principe des tiroirs

Solution officielle : Shortlist officielle 2009 (avec solutions), p. 38 (page 40 du PDF)

Problème 6 de l'OIM 2009

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

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Variant 1. A grasshopper jumps along the real axis. He starts at point \(0\) and makes \(2009\) jumps to the right with lengths \(1, 2, \ldots, 2009\) in an arbitrary order. Let \(M\) be a set of \(2008\) positive integers less than \(1005 \cdot 2009\). Prove that the grasshopper can arrange his jumps in such a way that he never lands on a point from \(M\).

Variant 2. Let \(n\) be a nonnegative integer. A grasshopper jumps along the real axis. He starts at point \(0\) and makes \(n + 1\) jumps to the right with pairwise different positive integral lengths \(a_1, a_2, \ldots, a_{n+1}\) in an arbitrary order. Let \(M\) be a set of \(n\) positive integers in the interval \((0, s)\), where \(s = a_1 + a_2 + \cdots + a_{n+1}\). Prove that the grasshopper can arrange his jumps in such a way that he never lands on a point from \(M\).

Indices : les idées clés

• Variante 1 : on atterrit sur les multiples de \(2009\) (ou sur un résidu \(r\) évité par \(M\), choisi par les tiroirs), puis on choisit gloutonnement un point par intervalle, en traitant les intervalles du plus chargé au moins chargé.
• Variante 2, récurrence sur \(n\) : il suffit de faire \(m\) sauts sans tomber dans \(M\) en ayant dépassé au moins \(m\) points de \(M\) ; on renforce l'hypothèse en ne comptant que les points de \((0, s - \min a_i)\).
• Indices lisses : on considère le plus grand \(k^*\) tel que les sauts \(a_1 > \cdots > a_{k^*}\) (les plus grands d'abord) puissent être faits, puis le plus petit \(\overline{k}\) avec \(T_{\overline{k}} \in M\) et \(\lvert M \cap (0, T_{\overline{k}}) \rvert \geq \overline{k}\), et l'on échange un saut.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (une solution pour chaque variante et une remarque). La variante 2 est le problème 6 de l'OIM 2009.

Solution de la variante 1

On construit l'ensemble des points d'atterrissage de la sauterelle.

Cas 1 : \(M\) ne contient aucun multiple de \(2009\). On fixe les nombres \(2009k\), \(k = 1, 2, \ldots, 1005\), comme points d'atterrissage. Considérons les intervalles ouverts \(I_k = (2009(k - 1), 2009k)\), \(k = 1, 2, \ldots, 1005\). Montrons qu'on peut choisir exactement un point hors de \(M\) comme point d'atterrissage dans \(1004\) de ces intervalles, de sorte que toutes les longueurs de \(1\) à \(2009\) soient réalisées. Comme il reste un intervalle sans point choisi, la longueur \(2009\) apparaîtra bien. Chaque intervalle a une longueur \(2009\), donc un nouveau point d'atterrissage dans un intervalle donne une longueur \(d\) et aussi la longueur \(2009 - d\). Il suffit donc de réaliser les longueurs de \(D = \{1, 2, \ldots, 1004\}\). On le fait de façon gloutonne. Soit \(n_k\), \(k = 1, 2, \ldots, 1005\), le nombre d'éléments de \(M\) dans l'intervalle \(I_k\). On ordonne ces nombres de façon décroissante : soit \(p_1, p_2, \ldots, p_{1005}\) une permutation de \(\{1, 2, \ldots, 1005\}\) telle que \(n_{p_1} \geq n_{p_2} \geq \cdots \geq n_{p_{1005}}\). On ne choisit pas de point d'atterrissage dans \(I_{p_1}\). Supposons que des points d'atterrissage aient déjà été choisis dans les intervalles \(I_{p_2}, \ldots, I_{p_m}\) et que les longueurs \(d_2, \ldots, d_m\) de \(D\) soient réalisées, \(m = 1, \ldots, 1004\). Montrons qu'il existe un \(d \in D \setminus \{d_2, \ldots, d_m\}\) qui peut être réalisé par un nouveau point d'atterrissage dans \(I_{p_{m+1}}\). Supposons le contraire. Alors les \(1004 - (m - 1)\) autres longueurs sont bloquées par les \(n_{p_{m+1}}\) points de \(M\) dans \(I_{p_{m+1}}\). Chaque longueur \(d\) peut être réalisée par deux points d'atterrissage, à savoir \(2009(p_{m+1} - 1) + d\) et \(2009p_{m+1} - d\), donc

\[n_{p_{m+1}} \geq 2(1005 - m). \tag{1}\]

De plus, comme \(\lvert M \rvert = 2008 = n_1 + \cdots + n_{1005}\),

\[2008 \geq n_{p_1} + n_{p_2} + \cdots + n_{p_{m+1}} \geq (m + 1)n_{p_{m+1}}. \tag{2}\]

Par conséquent, d'après (1) et (2),

\[2008 \geq 2(m + 1)(1005 - m).\]

Le membre de droite de cette inégalité atteint évidemment son minimum pour \(m = 1004\), et cette valeur minimale (\(2010\)) est supérieure à \(2008\), ce qui est une contradiction.

Cas 2 : \(M\) contient un nombre \(\mu\) divisible par \(2009\). Par le principe des tiroirs, il existe un \(r \in \{1, \ldots, 2008\}\) tel que \(M\) ne contienne aucun nombre de reste \(r\) modulo \(2009\). On fixe les nombres \(2009(k - 1) + r\), \(k = 1, 2, \ldots, 1005\), comme points d'atterrissage, ainsi que \(1005 \cdot 2009\). Considérons les intervalles ouverts \(I_k = (2009(k - 1) + r, 2009k + r)\), \(k = 1, 2, \ldots, 1004\). Comme dans le cas 1, il suffit de montrer qu'on peut choisir dans \(1003\) de ces intervalles exactement un point d'atterrissage hors de \(M \setminus \{\mu\}\), de sorte que chacune des longueurs de \(D = \{1, 2, \ldots, 1004\} \setminus \{r\}\) soit réalisée. Remarquons que \(r\) et \(2009 - r\) sont réalisées par le premier et le dernier saut, et que choisir \(\mu\) réaliserait de nouveau ces deux différences. Soit \(n_k\), \(k = 1, 2, \ldots, 1004\), le nombre d'éléments de \(M \setminus \{\mu\}\) dans l'intervalle \(I_k\), et \(p_1, \ldots, p_{1004}\) une permutation de \(\{1, 2, \ldots, 1004\}\) telle que \(n_{p_1} \geq n_{p_2} \geq \cdots \geq n_{p_{1004}}\). Par le même raisonnement que dans le cas 1, on vérifie qu'un choix glouton des points d'atterrissage dans \(I_{p_2}, I_{p_3}, \ldots, I_{p_{1004}}\) est possible. Il suffit de remplacer (1) par

\[n_{p_{m+1}} \geq 2(1004 - m)\]

(\(D\) a un élément de moins) et (2) par

\[2007 \geq n_{p_1} + n_{p_2} + \cdots + n_{p_{m+1}} \geq (m + 1)n_{p_{m+1}}. \qquad \blacksquare\]

Remarque. Le cardinal \(2008\) de \(M\) dans le problème est la plus grande valeur possible. Pour \(M = \{1, 2, \ldots, 2009\}\), la sauterelle tombe forcément sur un point de \(M\).

Solution de la variante 2

Remarquons d'abord que l'énoncé du problème implique un renforcement de lui-même : au lieu de \(\lvert M \rvert = n\), il suffit de supposer \(\lvert M \cap (0, s - \overline{a}] \rvert \leq n\), où \(\overline{a} = \min\{a_1, a_2, \ldots, a_{n+1}\}\). Ce fait sera utilisé dans la preuve.

Prouvons l'énoncé par récurrence sur \(n\). Le cas \(n = 0\) est évident. Soit \(n > 0\), et supposons l'affirmation vraie pour tous les entiers positifs ou nuls inférieurs à \(n\). Soient de plus \(a_1, a_2, \ldots, a_{n+1}\), \(s\) et \(M\) donnés comme dans l'énoncé. Sans perte de généralité, on peut supposer \(a_{n+1} < a_n < \cdots < a_2 < a_1\). Posons

\[T_k = \sum_{i=1}^{k} a_i \qquad \text{pour } k = 0, 1, \ldots, n + 1.\]

Remarquons que \(0 = T_0 < T_1 < \cdots < T_{n+1} = s\). On utilisera l'hypothèse de récurrence de la façon suivante.

Affirmation 1. Il suffit de montrer que, pour un certain \(m \in \{1, 2, \ldots, n + 1\}\), la sauterelle peut faire au moins \(m\) sauts sans tomber sur un point de \(M\), et qu'en plus, après ces \(m\) sauts, elle a sauté par-dessus au moins \(m\) points de \(M\).

Preuve. Remarquons que \(m = n + 1\) est impossible, puisque \(\lvert M \rvert = n\). Posons \(n' = n - m\). Alors \(0 \leq n' < n\). Les \(n' + 1\) sauts restants peuvent être faits sans tomber sur l'un des au plus \(n'\) points interdits restants, d'après l'hypothèse de récurrence et une translation de l'origine. Cela prouve l'affirmation. \(\square\)

Un entier \(k \in \{1, 2, \ldots, n + 1\}\) est dit lisse si la sauterelle peut faire \(k\) sauts de longueurs \(a_1, a_2, \ldots, a_k\) de sorte qu'elle ne tombe jamais sur un point de \(M\), sauf peut-être au tout dernier saut.

Évidemment, \(1\) est lisse. Il existe donc un plus grand nombre \(k^*\) tel que tous les nombres \(1, 2, \ldots, k^*\) soient lisses. Si \(k^* = n + 1\), la preuve est terminée. Dans la suite, supposons \(k^* \leq n\).

Affirmation 2. On a

\[T_{k^*} \in M \qquad \text{et} \qquad \lvert M \cap (0, T_{k^*}) \rvert \geq k^*. \tag{3}\]

Preuve. Si \(T_{k^*} \notin M\), toute suite de sauts qui réalise le caractère lisse de \(k^*\) peut être prolongée par \(a_{k^*+1}\), ce qui contredit la maximalité de \(k^*\). On a donc \(T_{k^*} \in M\). Si \(\lvert M \cap (0, T_{k^*}) \rvert < k^*\), il existe un \(l \in \{1, 2, \ldots, k^*\}\) avec \(T_{k^*+1} - a_l \notin M\). D'après l'hypothèse de récurrence avec \(k^* - 1\) au lieu de \(n\), la sauterelle peut atteindre \(T_{k^*+1} - a_l\) en \(k^*\) sauts de longueurs prises dans \(\{a_1, a_2, \ldots, a_{k^*+1}\} \setminus \{a_l\}\), sans tomber sur aucun point de \(M\). Donc \(k^* + 1\) est aussi lisse, ce qui contredit la maximalité de \(k^*\). L'affirmation 2 est prouvée. \(\square\)

D'après l'affirmation 2, il existe un plus petit entier \(\overline{k} \in \{1, 2, \ldots, k^*\}\) tel que

\[T_{\overline{k}} \in M \qquad \text{et} \qquad \lvert M \cap (0, T_{\overline{k}}) \rvert \geq \overline{k}.\]

Affirmation 3. Il suffit de considérer le cas

\[\lvert M \cap (0, T_{\overline{k}-1}] \rvert \leq \overline{k} - 1. \tag{4}\]

Preuve. Si \(\overline{k} = 1\), (4) est clairement vérifiée. Dans la suite, soit \(\overline{k} > 1\). Si \(T_{\overline{k}-1} \in M\), alors (4) découle immédiatement de la minimalité de \(\overline{k}\). Si \(T_{\overline{k}-1} \notin M\), par le caractère lisse de \(\overline{k} - 1\), on obtient une situation comme dans l'affirmation 1 avec \(m = \overline{k} - 1\), pourvu que \(\lvert M \cap (0, T_{\overline{k}-1}] \rvert \geq \overline{k} - 1\). On peut donc même se restreindre à \(\lvert M \cap (0, T_{\overline{k}-1}] \rvert \leq \overline{k} - 2\) dans ce cas, et l'affirmation 3 est prouvée. \(\square\)

Choisissons un entier \(v \geq 0\) tel que \(\lvert M \cap (0, T_{\overline{k}}) \rvert = \overline{k} + v\). Soient \(r_1 > r_2 > \cdots > r_l\) exactement les indices \(r\) de \(\{\overline{k} + 1, \overline{k} + 2, \ldots, n + 1\}\) pour lesquels \(T_{\overline{k}} + a_r \notin M\). Alors

\[n = \lvert M \rvert = \lvert M \cap (0, T_{\overline{k}}) \rvert + 1 + \lvert M \cap (T_{\overline{k}}, s) \rvert \geq \overline{k} + v + 1 + (n + 1 - \overline{k} - l),\]

et par conséquent \(l \geq v + 2\). Remarquons que

\[T_{\overline{k}} + a_{r_1} - a_1 < T_{\overline{k}} + a_{r_1} - a_2 < \cdots < T_{\overline{k}} + a_{r_1} - a_{\overline{k}} < T_{\overline{k}} + a_{r_2} - a_{\overline{k}} < \cdots < T_{\overline{k}} + a_{r_{v+2}} - a_{\overline{k}} < T_{\overline{k}},\]

et que ce sont \(\overline{k} + v + 1\) nombres de \((0, T_{\overline{k}})\). On trouve donc un \(r \in \{\overline{k} + 1, \overline{k} + 2, \ldots, n + 1\}\) et un \(s \in \{1, 2, \ldots, \overline{k}\}\) tels que \(T_{\overline{k}} + a_r \notin M\) et \(T_{\overline{k}} + a_r - a_s \notin M\). Considérons l'ensemble de longueurs de sauts \(B = \{a_1, a_2, \ldots, a_{\overline{k}}, a_r\} \setminus \{a_s\}\). On a

\[\sum_{x \in B} x = T_{\overline{k}} + a_r - a_s\]

et

\[T_{\overline{k}} + a_r - a_s - \min(B) = T_{\overline{k}} - a_s \leq T_{\overline{k}-1}.\]

D'après (4) et le renforcement mentionné tout au début (avec \(\overline{k} - 1\) au lieu de \(n\)), la sauterelle peut atteindre \(T_{\overline{k}} + a_r - a_s\) en \(\overline{k}\) sauts de longueurs prises dans \(B\), sans tomber sur aucun point de \(M\). De là, elle peut sauter en \(T_{\overline{k}} + a_r\), et l'on se trouve dans une situation comme dans l'affirmation 1 avec \(m = \overline{k} + 1\), ce qui termine la preuve. \(\blacksquare\)