Shortlist 2023, C5

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

Concepts : Jeux et stratégies gagnantes · Invariants et monovariants

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 45 (page 47 du PDF)

Énoncé

Elisa has \(2023\) treasure chests, all of which are unlocked and empty at first. Each day, Elisa adds a new gem to one of the unlocked chests of her choice, and afterwards, a fairy acts according to the following rules:

• if more than one chests are unlocked, it locks one of them, or
• if there is only one unlocked chest, it unlocks all the chests.

Given that this process goes on forever, prove that there is a constant \(C\) with the following property: Elisa can ensure that the difference between the numbers of gems in any two chests never exceeds \(C\), regardless of how the fairy chooses the chests to lock.

Indices : les idées clés

• Jeux et stratégies gagnantes : une stratégie gloutonne suffit, mettre la gemme dans le coffre ouvert le moins rempli (solution 1), ou une variante par blocs de \(n\) jours (solution 2).
• Majoration (au sens des suites ordonnées) : on compare la suite triée des contenus à une suite de référence explicite \((b_i^t)\) (solution 1) ou \((d_i^t)\) (solution 2) dont les sommes partielles sont toujours plus petites.
• Invariants et monovariants : la relation de majoration est une propriété conservée d'un jour à l'autre, prouvée par récurrence ; pour l'optimalité (remarque 2), les écarts de sommes partielles \(I_k\) ne peuvent que décroître.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (deux solutions et deux remarques).

Solution 1

On démontre l'existence de \(C\) pour \(n\) coffres, \(n\) impair ; on peut même prendre \(C = n - 1\). La stratégie d'Elisa est simple : mettre la gemme dans le coffre (ouvert) qui contient le moins de gemmes (en cas d'égalité, n'importe lequel).

Pour tout entier \(t \geq 0\), notons \(a_1^t \leq a_2^t \leq \cdots \leq a_n^t\) les nombres de gemmes des \(n\) coffres à la fin du \(t\)-ième jour. En particulier \(a_1^0 = \cdots = a_n^0 = 0\) et \(a_1^t + \cdots + a_n^t = t\).

Pour chaque \(t \geq 0\), il existe un unique indice \(m = m(t)\) tel que \(a_m^{t+1} = a_m^t + 1\) (en choisissant convenablement l'ordre des coffres ex aequo). On a \(a_j^t > a_{m(t)}^t\) pour tout \(j > m(t)\), puisque \(a_{m(t)}^t < a_{m(t)}^{t+1} \leq a_j^{t+1} = a_j^t\). La stratégie d'Elisa garantit aussi que si l'indice \(j\) est strictement supérieur au reste de \(t\) modulo \(n\) (c'est-à-dire au nombre de coffres fermés à la fin du jour \(t\)), alors \(a_j^t \geq a_{m(t)}^t\) : en effet, un coffre contenant au plus \(a_j^t\) gemmes est encore ouvert à la fin du jour \(t\).

Rappelons qu'une suite \(x_1 \leq \cdots \leq x_n\) majorise une suite \(y_1 \leq \cdots \leq y_n\) si pour tout \(1 \leq k \leq n\),

\[x_1 + x_2 + \cdots + x_k \leq y_1 + y_2 + \cdots + y_k, \quad \text{et} \quad x_1 + \cdots + x_n = y_1 + \cdots + y_n.\]

Pour prouver \(a_n^t - a_1^t \leq n - 1\), on montre par récurrence que \((a_i^t)\) est majorisée par une autre suite \((b_i^t)\), définie ainsi : \(b_k^0 = k - \frac{n+1}{2}\) pour \(1 \leq k \leq n\) (comme \(n\) est impair, c'est une suite strictement croissante d'entiers, de somme nulle), et

\[b_i^t = b_i^0 + \left\lfloor \frac{t - i}{n} \right\rfloor + 1 \quad (t \geq 1,\ 1 \leq i \leq n).\]

Ainsi, pour \(t \geq 0\),

\[b_i^{t+1} = \begin{cases} b_i^t & \text{si } t + 1 \not\equiv i \pmod n, \\ b_i^t + 1 & \text{si } t + 1 \equiv i \pmod n. \end{cases}\]

On en déduit facilement que :

• \(b_1^t + b_2^t + \cdots + b_n^t = t\) pour tout \(t \geq 0\) ;
• \(b_i^t \leq b_{i+1}^t\) pour tout \(t \geq 0\) et \(1 \leq i \leq n - 1\), avec inégalité stricte si \(t \not\equiv i \pmod n\).

Affirmation 1. Pour tout \(t \geq 0\), la suite \(b_1^t, \ldots, b_n^t\) majorise la suite \(a_1^t, \ldots, a_n^t\).

Preuve. Par récurrence sur \(t\) ; le cas \(t = 0\) est immédiat. Supposons que \((b_i^t)\) majorise \((a_i^t)\). Les suites \((b_i^{t+1})\) et \((a_i^{t+1})\) ont toutes deux pour somme \(t + 1\). Il reste à voir que pour \(1 \leq k < n\),

\[b_1^{t+1} + \cdots + b_k^{t+1} \leq a_1^{t+1} + \cdots + a_k^{t+1}.\]

Supposons par l'absurde que cela échoue, et soit \(k\) le plus petit indice pour lequel c'est le cas. Comme le membre de gauche augmente d'au plus \(1\) entre \(t\) et \(t + 1\), l'échec n'est possible que si simultanément :

• \(b_1^t + \cdots + b_k^t = a_1^t + \cdots + a_k^t\) ;
• \(t + 1 \equiv j \pmod n\) pour un certain \(1 \leq j \leq k\) (de sorte que \(b_j^{t+1} = b_j^t + 1\)) ;
• \(m(t) > k\) (de sorte que \(a_i^{t+1} = a_i^t\) pour \(1 \leq i \leq k\)).

Le premier point et la minimalité de \(k\) montrent que \(b_1^t, \ldots, b_k^t\) majorise aussi \(a_1^t, \ldots, a_k^t\) (par l'hypothèse de récurrence), et en particulier \(b_k^t \geq a_k^t\).

Le deuxième point indique que le reste de \(t\) modulo \(n\) est au plus \(k - 1\), donc \(a_k^t \geq a_{m(t)}^t\) (stratégie d'Elisa). Mais, par le troisième point (\(m(t) \geq k + 1\)) et la croissance de \((a_i^t)\), on a les égalités \(a_k^t = a_{k+1}^t = a_{m(t)}^t\). D'autre part, \(a_k^t \leq b_k^t < b_{k+1}^t\), la seconde inégalité étant stricte car \(t \not\equiv k \pmod n\). On en conclut

\[b_1^t + b_2^t + \cdots + b_{k+1}^t > a_1^t + a_2^t + \cdots + a_{k+1}^t,\]

ce qui contredit l'hypothèse de récurrence. \(\square\)

Cela conclut, car l'affirmation (appliquée à \(k = 1\) et \(k = n - 1\)) donne

\[a_n^t - a_1^t \leq b_n^t - b_1^t \leq b_n^0 - b_1^0 = n - 1. \quad \blacksquare\]

Solution 2

On résout le problème avec \(n\) coffres, \(n\) entier quelconque. Elisa utilise la stratégie suivante.

Au début du jour \(nt + 1\), Elisa numérote ses coffres \(C_1^t, \ldots, C_n^t\) de sorte qu'avant l'ajout de la gemme, \(C_i^t\) contient au plus autant de gemmes que \(C_j^t\) pour tous \(1 \leq i < j \leq n\). Ensuite, pendant les jours \(nt + 1, nt + 2, \ldots, nt + n\), elle ajoute la gemme dans le coffre \(C_i^t\) ouvert d'indice \(i\) minimal.

Notons \(c_i^t\) le nombre de gemmes de \(C_i^t\) au début du jour \(nt + 1\), de sorte que \(c_1^t \leq c_2^t \leq \cdots \leq c_n^t\), et \(\delta_i^t\) le nombre total de gemmes ajoutées à \(C_i^t\) pendant les jours \(nt + 1, \ldots, nt + n\). On observe que :

• \(c_1^0 = c_2^0 = \cdots = c_n^0 = 0\) ;
• \(c_1^t + \cdots + c_n^t = nt\), puisque \(n\) gemmes sont ajoutées tous les \(n\) jours ;
• la suite \((c_i^{t+1})\) est une permutation de la suite \((c_i^t + \delta_i^t)\) ;
• \(\delta_1^t + \cdots + \delta_n^t = n\) ;
• comme Elisa choisit le coffre ouvert \(C_i^t\) d'indice minimal, \(\delta_1^t + \delta_2^t + \cdots + \delta_k^t \geq k\) pour tous \(1 \leq k \leq n\) et \(t \geq 0\).

On définit une suite de référence :

\[d_i^0 = 3n\left(i - \frac{n+1}{2}\right), \qquad d_i^t = d_i^0 + t,\]

de sorte que \(d_1^t + \cdots + d_n^t = c_1^t + \cdots + c_n^t = nt\).

Affirmation 3. Pour tout \(t \geq 0\), la suite \((d_i^t)\) majorise la suite \((c_i^t)\).

Preuve. Par récurrence sur \(t\). Pour \(t = 0\), c'est clair puisque tous les \(c_i^0\) sont égaux. Supposons que \((d_i^t)\) majorise \((c_i^t)\) et soit \(1 \leq k \leq n - 1\) ; montrons que \(d_1^{t+1} + \cdots + d_k^{t+1} \leq c_1^{t+1} + \cdots + c_k^{t+1}\).

Cas 1 : \(c_1^{t+1}, \ldots, c_k^{t+1}\) est une permutation de \(c_1^t + \delta_1^t, \ldots, c_k^t + \delta_k^t\). Par hypothèse de récurrence,

\[\sum_{i=1}^{k} d_i^{t+1} = k + \sum_{i=1}^{k} d_i^t \leq k + \sum_{i=1}^{k} c_i^t \leq \sum_{i=1}^{k} (c_i^t + \delta_i^t) = \sum_{i=1}^{k} c_i^{t+1}.\]

Cas 2 : ce n'est pas une permutation. Il existe alors \(i \leq k < j\) avec \(c_i^t + \delta_i^t > c_j^t + \delta_j^t\). Il s'ensuit que

\[c_k^t + n \geq c_i^t + n \geq c_i^t + \delta_i^t > c_j^t + \delta_j^t \geq c_j^t \geq c_{k+1}^t.\]

En utilisant \(d_k^t + 3n = d_{k+1}^t\) et l'hypothèse de récurrence :

\[\begin{aligned} \sum_{i=1}^{k} c_i^{t+1} \geq \sum_{i=1}^{k} c_i^t &> c_1^t + \cdots + c_{k-1}^t + \frac{1}{2} c_k^t + \frac{1}{2} c_{k+1}^t - \frac{n}{2} = \frac{1}{2} \sum_{i=1}^{k-1} c_i^t + \frac{1}{2} \sum_{i=1}^{k+1} c_i^t - \frac{n}{2} \\ &\geq \frac{1}{2} \sum_{i=1}^{k-1} d_i^t + \frac{1}{2} \sum_{i=1}^{k+1} d_i^t - \frac{n}{2} = n + \sum_{i=1}^{k} d_i^t \geq k + \sum_{i=1}^{k} d_i^t = \sum_{i=1}^{k} d_i^{t+1}. \end{aligned}\]

(La première inégalité vient de ce que les \(k\) plus petits termes de \((c_i^t + \delta_i^t)\) sont au moins les \(k\) plus petits \(c_i^t\).) Cela achève la récurrence. \(\square\)

On en déduit

\[c_n^t - c_1^t \leq d_n^t - d_1^t = 3n(n-1).\]

Entre le jour \(nt + 1\) et le jour \(n(t+1) + 1\), Elisa ajoute \(n\) gemmes, donc l'écart peut augmenter d'au plus \(n\). Ainsi, l'écart entre deux coffres ne dépasse jamais \(C = 3n(n-1) + n\). \(\blacksquare\)

Remarques

Remarque 1 (\(n\) pair). L'énoncé reste vrai pour \(n\) pair : dans la solution 1, on prend comme état initial

\[b_k^0 = \begin{cases} k - \frac{n}{2} - 1 & \text{si } k \leq \frac{n}{2}, \\ k - \frac{n}{2} & \text{si } k > \frac{n}{2}, \end{cases}\]

et le même argument montre que \(C = n\) convient.

Remarque 2 (optimalité). Les constantes \(C = n - 1\) pour \(n\) impair et \(C = n\) pour \(n\) pair sont optimales. Supposons que la fée ferme toujours un coffre contenant le moins de gemmes. Alors, à tout moment, si un coffre est fermé, tout coffre contenant moins de gemmes l'est aussi ; donc \(m(t)\) est toujours strictement supérieur au reste de \(t\) modulo \(n\). Il en résulte que les quantités

\[I_k = a_1^t + \cdots + a_k^t - b_1^t - \cdots - b_k^t \quad (0 \leq k \leq n)\]

ne peuvent pas augmenter, quoi que fasse Elisa (monovariant). Si Elisa parvient à garder \(a_n^t - a_1^t\) borné, ces quantités sont bornées, donc constantes à partir d'un certain rang \(t_0\). Cela implique que pour tout \(t \geq t_0\), \(m(t)\) vaut \(1\) plus le reste de \(t\) modulo \(n\).

Affirmation 2. Pour \(T \geq t_0\) multiple de \(n\), \(a_1^T < a_2^T < \cdots < a_n^T\).

Preuve. Sinon, soit \(j\) tel que \(a_j^T = a_{j+1}^T\). On a \(m(T + k - 1) = k\) pour tout \(1 \leq k \leq n\) : après les jours \(T + 1, \ldots, T + j\), le coffre en position \(j\) a reçu une gemme et pas celui en position \(j + 1\), d'où \(a_j^{T+j} > a_{j+1}^{T+j}\), contradiction. \(\square\)

On obtient \(a_n^T - a_1^T \geq n - 1\), ce qui prouve l'optimalité de \(C = n - 1\) pour \(n\) impair. Pour \(n\) pair, la somme des \(a_i^T\) est divisible par \(n\), alors que la somme de \(n\) entiers consécutifs ne l'est pas ; donc \(a_n^T - a_1^T \geq n\).