Shortlist 2014, C2

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

Concepts : Invariants et monovariants · AM-GM et moyennes

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 28 (page 29 du PDF)

Énoncé

We have \(2^m\) sheets of paper, with the number \(1\) written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are \(a\) and \(b\), then we erase these numbers and write the number \(a + b\) on both sheets. Prove that after \(m 2^{m-1}\) steps, the sum of the numbers on all the sheets is at least \(4^m\).

Indices : les idées clés

• Monovariant : le produit \(P_k\) des nombres écrits est au moins multiplié par \(4\) à chaque étape, car \((a + b)^2 \geq 4ab\).
• AM-GM : après \(m 2^{m-1}\) étapes, \(P \geq 4^{m 2^{m-1}} = (2^m)^{2^m}\), donc la somme des \(2^m\) nombres est au moins \(2^m \cdot 2^m = 4^m\).
• Optimalité : \(m\) « tours de doublement » de \(2^{m-1}\) étapes chacun atteignent exactement \(4^m\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et trois remarques).

Solution

Soit \(P_k\) le produit des nombres écrits sur les feuilles après \(k\) étapes.

Supposons qu'à la \((k+1)\)-ème étape, les nombres \(a\) et \(b\) soient remplacés par \(a + b\). Dans le produit, le facteur \(ab\) est remplacé par \((a + b)^2\), et les autres facteurs ne changent pas. Comme \((a + b)^2 \geq 4ab\), on a \(P_{k+1} \geq 4 P_k\). Partant de \(P_0 = 1\), une récurrence immédiate donne \(P_k \geq 4^k\) pour tout entier \(k \geq 0\) ; en particulier

\[P_{m \cdot 2^{m-1}} \geq 4^{m \cdot 2^{m-1}} = (2^m)^{2^m}.\]

Par l'inégalité arithmético-géométrique, la somme des nombres écrits sur les feuilles après \(m 2^{m-1}\) étapes est donc au moins

\[2^m \cdot \sqrt[2^m]{P_{m \cdot 2^{m-1}}} \geq 2^m \cdot 2^m = 4^m. \qquad \blacksquare\]

Remarques

Remarque 1. On peut atteindre la somme \(4^m\) en \(m 2^{m-1}\) étapes. Par exemple, en partant de \(2^m\) nombres égaux, on peut doubler tous les nombres en \(2^{m-1}\) étapes consécutives. Après \(m\) tours de doublement, chaque feuille porte le nombre \(2^m\).

Remarque 2. La solution admet plusieurs variantes. Par exemple, on peut essayer d'attribuer à chaque entier \(n \geq 1\) un poids \(w_n\) de sorte que la somme des poids des nombres écrits augmente d'au moins \(2\) à chaque étape. Il faut pour cela que

\[2 w_{a+b} \geq w_a + w_b + 2 \tag{1}\]

pour tous entiers \(a, b \geq 1\).

En partant de \(w_1 = 1\) et en cherchant des poids aussi petits que possible, on trouve la définition suivante : pour tout entier \(n \geq 1\), on prend \(k\) maximal tel que \(n \geq 2^k\), et l'on pose

\[w_n = k + \frac{n}{2^k} = \min_{d \in \mathbb{Z}_{\geq 0}} \left(d + \frac{n}{2^d}\right). \tag{2}\]

Pour montrer (1), prenons des entiers \(a, b \geq 1\) et un entier \(d \geq 0\) tel que \(w_{a+b} = d + \frac{a+b}{2^d}\). Alors

\[2 w_{a+b} = 2d + 2 \cdot \frac{a + b}{2^d} = \left((d - 1) + \frac{a}{2^{d-1}}\right) + \left((d - 1) + \frac{b}{2^{d-1}}\right) + 2 \geq w_a + w_b + 2.\]

Comme la somme initiale des poids vaut \(2^m\), après \(m 2^{m-1}\) étapes elle vaut au moins \((m + 1) 2^m\). Pour conclure, on remarque que d'après (2), pour tout entier \(a \geq 1\),

\[w_a \leq m + \frac{a}{2^m}, \quad \text{c'est-à-dire} \quad a \geq 2^m (-m + w_a). \tag{3}\]

La somme des nombres \(a_1, a_2, \ldots, a_{2^m}\) écrits sur les feuilles vérifie donc

\[\sum_{i=1}^{2^m} a_i \geq \sum_{i=1}^{2^m} 2^m (-m + w_{a_i}) = -m 2^m \cdot 2^m + 2^m \sum_{i=1}^{2^m} w_{a_i} \geq -m 4^m + (m + 1) 4^m = 4^m.\]

On peut aussi établir (1) et (3) par un argument de convexité, au lieu de la seconde définition de \(w_n\) dans (2). On vérifie que \(\log_2 n \leq w_n \leq \log_2 n + 1\) : en un sens, cette approche revient à « prendre le logarithme » de la solution ci-dessus.

Remarque 3. Une stratégie intuitive pour minimiser la somme consiste à choisir à chaque étape les deux plus petits nombres : c'est la stratégie gloutonne. Montrons qu'elle donne bien la plus petite somme possible.

Affirmation. En partant de nombres réels positifs quelconques \(x_1, \ldots, x_N\) sur \(N\) feuilles, pour tout nombre \(k\) d'étapes, la stratégie gloutonne donne la plus petite somme possible.

Preuve. Par récurrence sur \(k\) ; pour \(k = 1\), c'est évident. Soit \(k \geq 2\), et supposons l'affirmation vraie pour les valeurs plus petites.

Toute suite de \(k\) étapes se code par \(S = \big((i_1, j_1), \ldots, (i_k, j_k)\big)\), où \(i_r\) et \(j_r\) sont les indices des deux feuilles choisies à la \(r\)-ème étape. La somme finale est une combinaison linéaire \(c_1 x_1 + \cdots + c_N x_N\) à coefficients entiers strictement positifs \(c_1, \ldots, c_N\) qui ne dépendent que de \(S\) ; on appelle \((c_1, \ldots, c_N)\) le vecteur caractéristique de \(S\).

Choisissons une suite d'étapes \(S_0 = \big((i_1, j_1), \ldots, (i_k, j_k)\big)\) qui donne la somme minimale à partir de \(x_1, \ldots, x_N\), et soit \((c_1, \ldots, c_N)\) son vecteur caractéristique. Quitte à renuméroter les feuilles, on peut supposer \(c_1 \geq c_2 \geq \cdots \geq c_N\). Si l'on permute les feuilles (et les nombres) par une permutation \(\pi\) des indices puis qu'on effectue les mêmes étapes, on obtient la somme \(\sum_{t=1}^{N} c_t x_{\pi(t)}\). Par l'inégalité de réordonnement, la plus petite somme est atteinte quand \((x_1, \ldots, x_N)\) est croissante ; on peut donc supposer aussi \(x_1 \leq x_2 \leq \cdots \leq x_N\).

Soit \(\ell\) le plus grand indice tel que \(c_1 = \cdots = c_\ell\), et soit la \(r\)-ème étape la première pour laquelle \(c_{i_r} = c_1\) ou \(c_{j_r} = c_1\). Les rôles de \(i_r\) et \(j_r\) étant symétriques, on peut supposer \(c_{i_r} = c_1\), donc \(i_r \leq \ell\). Montrons que \(c_{j_r} = c_1\) et \(j_r \leq \ell\) aussi.

Avant la \(r\)-ème étape, la feuille \(i_r\) portait le nombre \(x_{i_r}\). La feuille \(j_r\) portait une combinaison linéaire contenant \(x_{j_r}\) avec un coefficient entier strictement positif, et éventuellement d'autres termes. À la \(r\)-ème étape, \(x_{i_r}\) rejoint cette combinaison. À partir de là, chaque feuille porte une combinaison linéaire de \(x_1, \ldots, x_N\) dans laquelle le coefficient de \(x_{j_r}\) est au moins celui de \(x_{i_r}\), et cela reste vrai jusqu'à la fin ; donc \(c_{j_r} \geq c_{i_r}\). Comme \(c_{i_r} = c_1\) est maximal, \(c_{j_r} = c_{i_r} = c_1\), donc \(j_r \leq \ell\).

Que ce soit par \(c_{j_r} = c_{i_r} = c_1\) ou par l'argument précédent, ni la feuille \(i_r\) ni la feuille \(j_r\) n'ont été utilisées avant l'étape \(r\). La combinaison linéaire finale ne change donc pas si l'on effectue l'étape \((i_r, j_r)\) en premier : la suite

\[S_1 = \big((i_r, j_r), (i_1, j_1), \ldots, (i_{r-1}, j_{r-1}), (i_{r+1}, j_{r+1}), \ldots, (i_k, j_k)\big)\]

donne la même somme minimale (le livret termine cette suite par \((i_N, j_N)\) ; il faut lire \((i_k, j_k)\)). On peut donc remplacer \(S_0\) par \(S_1\) et supposer \(r = 1\) et \(c_{i_1} = c_{j_1} = c_1\).

Comme \(i_1 \neq j_1\), on a \(\ell \geq 2\) et \(c_1 = c_2 = c_{i_1} = c_{j_1}\). Soit \(\pi\) la permutation des indices qui échange \(1, 2\) avec \(i_1, j_1\) et laisse les autres indices fixes, et soit

\[S_2 = \big((\pi(i_1), \pi(j_1)), \ldots, (\pi(i_k), \pi(j_k))\big).\]

Comme \(c_{\pi(i)} = c_i\) pour tout \(i\), cette suite donne la même somme minimale. De plus, à la première étape, on choisit \(x_{\pi(i_1)} = x_1\) et \(x_{\pi(j_1)} = x_2\), les deux plus petits nombres.

On peut donc atteindre la somme optimale en suivant la stratégie gloutonne à la première étape, puis, par l'hypothèse de récurrence, en la suivant aux étapes suivantes. \(\square\)