Shortlist 2019, C3

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

Concepts : Récurrence et constructions récursives · Invariants et monovariants · Bijections et dénombrement

Solution officielle : Shortlist officielle 2019 (avec solutions), section C3 (livret PDF)

Problème 5 de l'OIM 2019

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

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(n\) be a positive integer. Harry has \(n\) coins lined up on his desk, each showing heads or tails. He repeatedly does the following operation: if there are \(k\) coins showing heads and \(k > 0\), then he flips the \(k\)-th coin over; otherwise he stops the process. (For example, the process starting with \(THT\) would be \(THT \to HHT \to HTT \to TTT\), which takes three steps.)

Letting \(C\) denote the initial configuration (a sequence of \(n\) H's and T's), write \(\ell(C)\) for the number of steps needed before all coins show T. Show that this number \(\ell(C)\) is finite, and determine its average value over all \(2^n\) possible initial configurations \(C\).

Indices : les idées clés

• Récurrence et constructions récursives (solutions 1 et 2) : le graphe des configurations à \(n\) pièces se construit à partir de deux copies de celui à \(n-1\) pièces, d'où \(E(n) = E(n-1) + \frac n2\).
• Monovariant (solution 3) : la quantité \(t(i) = I_i + 2(\min\{i, H_n\} - H_i)\) compte exactement les retournements futurs de la pièce \(i\).
• Bijections et dénombrement (solutions 3, 4 et 5) : bijection entre configurations et suites croissantes \(a_1 < \cdots < a_t \leq n\) (solution 4), sommes de coefficients binomiaux (solutions 3 et 5).
• Description explicite du processus (solution 5) : \(\ell(C) = 2\sum c_j - k^2\) si les faces sont aux positions \(c_1 < \cdots < c_k\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (cinq solutions).

Réponse : la moyenne vaut \(\dfrac{n(n+1)}{4}\).

Remarque commune. Dans toutes les solutions, \(E(n)\) désigne la moyenne cherchée.

Solution 1

On représente le problème par un graphe orienté \(G_n\) dont les sommets sont les chaînes de longueur \(n\) formées de H et de T, avec une arête de chaque chaîne vers son successeur (sauf pour \(TT\cdots T\), qui n'en a pas). On note \(\bar H = T\) et \(\bar T = H\). Le graphe \(G_0\) a un seul sommet : la chaîne vide. L'affirmation principale est que \(G_n\) se décrit récursivement à partir de \(G_{n-1}\) :

• on prend deux copies \(X\) et \(Y\) de \(G_{n-1}\) ;
• dans \(X\), on ajoute un T à la fin de chaque chaîne : \(s_1 \cdots s_{n-1}\) devient \(s_1 \cdots s_{n-1} T\) ;
• dans \(Y\), on retourne toutes les pièces, on renverse l'ordre et on ajoute un H à la fin : \(s_1 \cdots s_{n-1}\) devient \(\bar s_{n-1} \bar s_{n-2} \cdots \bar s_1 H\) ;
• enfin on ajoute une arête de \(Y\) vers \(X\) : \(HH\cdots HH \to HH\cdots HT\).

Voici \(G_4\) selon cette construction :

Preuve par récurrence. \(X\) est correct comme sous-graphe de \(G_n\) : un T supplémentaire à la fin ne change pas l'opération ; si \(s_1 \cdots s_{n-1}\) est envoyé sur \(t_1 \cdots t_{n-1}\), alors \(s_1 \cdots s_{n-1}T\) est envoyé sur \(t_1 \cdots t_{n-1}T\).

\(Y\) est aussi correct : si \(s_1 \cdots s_{n-1}\) contient \(k\) fois H, alors \(\bar s_{n-1} \cdots \bar s_1 H\) en contient \((n - 1 - k) + 1 = n - k\) ; la pièce retournée est la \((n-k)\)-ième, qui correspond à la \(k\)-ième de la chaîne d'origine. Donc (si \(k > 0\)), si \(s_1 \cdots s_{n-1}\) est envoyé sur \(t_1 \cdots t_{n-1}\), alors \(\bar s_{n-1} \cdots \bar s_1 H\) est envoyé sur \(\bar t_{n-1} \cdots \bar t_1 H\).

Enfin, l'arête de \(Y\) vers \(X\) est correcte, puisque l'opération envoie bien \(HH\cdots HHH\) sur \(HH \cdots HHT\).

Pour conclure : les chaînes de \(X\) mettent en moyenne \(E(n-1)\) étapes pour s'arrêter ; celles de \(Y\) mettent en moyenne \(E(n-1)\) étapes pour atteindre \(HH\cdots H\) (image de \(TT\cdots T\)), puis encore \(n\) étapes pour s'arrêter (\(HH \cdots H\) va en une étape sur \(HH\cdots HT\), qui est dans \(X\) l'image de \(HH\cdots H\) à \(n-1\) pièces, laquelle demande \(n-1\) étapes). Donc

\[E(n) = \frac12\Big(E(n-1) + \big(E(n-1) + n\big)\Big) = E(n-1) + \frac n2.\]

Comme \(E(0) = 0\), on obtient par récurrence \(E(n) = \frac12(1 + \cdots + n) = \frac14 n(n+1)\), qui est en particulier fini. \(\blacksquare\)

Solution 2

On distingue les configurations selon leur première et leur dernière pièce.

• Si la configuration commence par H, les \(n - 1\) dernières pièces suivent les règles, comme si elles étaient seules, jusqu'à être toutes sur T ; puis la première pièce est retournée.
• Si la configuration finit par T, la dernière pièce n'est jamais retournée, et les \(n - 1\) premières suivent les règles comme si elles étaient seules.
• Si la configuration commence par T et finit par H, les \(n - 2\) pièces du milieu suivent les règles comme si elles étaient seules, jusqu'à être toutes sur T. Il reste alors \(2n - 1\) étapes : les pièces \(1, 2, \ldots, n-1\) sont retournées dans cet ordre, puis les pièces \(n, n-1, \ldots, 1\).

Cela couvre toutes les configurations, et le nombre d'étapes est clairement fini pour \(0\) ou \(1\) pièce ; par récurrence sur \(n\), il est toujours fini.

Notons \(E_{AB}(n)\), où \(A\), \(B\) valent H, T ou \(*\), la moyenne du nombre d'étapes sur les configurations de longueur \(n\) qui commencent par \(A\) (si \(A \neq *\)) et finissent par \(B\) (si \(B \neq *\)) ; \(*\) signifie « H ou T ». Les observations ci-dessus donnent, pour \(n \geq 2\) :

• \(E_{H*}(n) = E(n-1) + 1\) ;
• \(E_{*T}(n) = E(n-1)\) ;
• \(E_{HT}(n) = E(n-2) + 1\) (en combinant les deux observations précédentes) ;
• \(E_{TH}(n) = E(n-2) + 2n - 1\).

Comme \(E_{H*}(n) = \frac12\big(E_{HH}(n) + E_{HT}(n)\big)\), on a \(E_{HH}(n) = 2E(n-1) - E(n-2) + 1\). De même, \(E_{TT}(n) = 2E(n-1) - E(n-2) - 1\). Donc

\[E(n) = \frac14\big(E_{HT}(n) + E_{HH}(n) + E_{TT}(n) + E_{TH}(n)\big) = E(n-1) + \frac n2.\]

Avec \(E(0) = 0\) et \(E(1) = \frac12\), on obtient par récurrence \(E(n) = \frac14 n(n+1)\). \(\blacksquare\)

Solution 3

Soit \(H_i\) le nombre de faces (H) parmi les positions \(1\) à \(i\) (donc \(H_n\) est le nombre total de faces), et \(I_i = 1\) si la \(i\)-ième pièce est sur H, \(0\) sinon. Posons

\[t(i) = I_i + 2\big(\min\{i, H_n\} - H_i\big).\]

Affirmation : \(t(i)\) est le nombre total de fois où la pièce \(i\) sera retournée (ce qui implique que le processus s'arrête). On a \(t(i) = 0\) quand toutes les pièces sont sur T, et \(t(i)\) est toujours un entier positif ou nul ; il suffit donc de montrer que, quand on retourne la pièce \(k\) (avec \(k = H_n\)), \(t(k)\) diminue de \(1\) et les autres \(t(i)\) sont inchangés (monovariant) :

• si \(i < k\) : \(I_i\) et \(H_i\) ne changent pas, et \(\min\{i, H_n\} = i\) avant et après, donc \(t(i)\) est inchangé ;
• si \(i > k\) : \(\min\{i, H_n\} = H_n\) avant et après, et \(H_n\) et \(H_i\) varient de la même quantité, donc \(t(i)\) est inchangé ;
• si \(i = k\) et la pièce est sur H : \(I_i\) diminue de \(1\), ainsi que \(\min\{i, H_n\} = H_n\) et \(H_i\) ; donc \(t(i)\) diminue de \(1\) ;
• si \(i = k\) et la pièce est sur T : \(I_i\) augmente de \(1\), \(\min\{i, H_n\} = i\) ne change pas et \(H_i\) augmente de \(1\) ; donc \(t(i)\) diminue de \(1\).

Il faut maintenant calculer la moyenne de

\[\sum_{i=1}^n t(i) = \sum_{i=1}^n I_i + 2\sum_{i=1}^n \min\{i, H_n\} - 2\sum_{i=1}^n H_i.\]

La moyenne du premier terme est \(\frac12 n\), celle du troisième est \(-\frac12 n(n+1)\) (car \(H_i\) vaut \(\frac i2\) en moyenne). Pour le deuxième, on somme selon le nombre total \(j\) de faces, puis sur \(i\) (avec \(\sum_{i=1}^n \min\{i,j\} = nj - \binom j2\)) :

\[2^{1-n} \sum_{j=0}^n \binom nj \sum_{i=1}^n \min\{i, j\} = 2^{1-n} \sum_{j=0}^n \binom nj \left(nj - \binom j2\right).\]

Avec des coefficients trinomiaux (dénombrement),

\[\sum_{j=0}^n j\binom nj = \sum_{j=1}^n \binom{n}{n-j,\ j-1,\ 1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = 2^{n-1} n\]

et

\[\sum_{j=0}^n \binom j2 \binom nj = \sum_{j=2}^n \binom{n}{n-j,\ j-2,\ 2} = \binom n2 \sum_{j=0}^{n-2}\binom{n-2}{j} = 2^{n-2}\binom n2.\]

Le deuxième terme vaut donc

\[2^{1-n}\left(2^{n-1} n^2 - 2^{n-2}\binom n2\right) = n^2 - \frac{n(n-1)}{4},\]

et la moyenne cherchée est

\[E(n) = \frac12 n + n^2 - \frac{n(n-1)}{4} - \frac12 n(n+1) = \frac{n(n+1)}{4}. \qquad \blacksquare\]

Solution 4

Harry a construit une machine de Turing qui retourne les pièces pour lui. La machine est initialement placée sur la \(k\)-ième pièce, où \(k\) est le nombre de faces (la position avant la première pièce est considérée comme la pièce numéro \(0\)). Elle se déplace selon les règles suivantes, et s'arrête quand elle atteint la position avant la première pièce : si la pièce à sa position est H, elle la retourne et recule d'une position ; si c'est T, elle la retourne et avance d'une position. (On vérifie que cela reproduit exactement le processus : après chaque retournement, la machine est sur la pièce de numéro égal au nouveau nombre de faces.)

Considérons les suites maximales de déplacements consécutifs dans le même sens. Si la machine avance \(a\) fois de suite avant de reculer, alors après ces \(a\) déplacements, les \(a\) pièces retournées sont toutes sur H, ainsi que la pièce où se trouve la machine ; donc les \(a + 1\) déplacements suivants au moins sont des reculs. De même, \(a\) reculs consécutifs sont suivis d'au moins \(a + 1\) avancées consécutives. Il ne peut pas y avoir plus de \(n\) déplacements consécutifs dans le même sens, donc le processus s'arrête (par un recul de la première pièce vers la position \(0\)).

On obtient ainsi une suite (éventuellement vide) \(a_1 < \cdots < a_t \leq n\) des longueurs des suites maximales de déplacements dans le même sens, les \(a_t\) derniers déplacements étant des reculs qui se terminent avant la première pièce. Affirmation : il y a une bijection entre les configurations initiales et ces suites. Cela donne

\[E(n) = \frac12(1 + 2 + \cdots + n) = \frac{n(n+1)}{4},\]

car chaque \(i\) (\(1 \leq i \leq n\)) apparaît dans la moitié des suites et contribue alors \(i\) au nombre de déplacements.

Pour la bijection, on suit la suite de déplacements à l'envers, en partant de la machine placée avant la première pièce et de toutes les pièces sur T. Cela détermine une unique configuration pouvant correspondre à la suite donnée. De plus, chaque pièce retournée lors des \(a_j\) déplacements consécutifs l'est aussi lors de chaque bloc ultérieur de \(a_k\) déplacements, \(k > j\) ; donc, en remontant le temps, chaque pièce est toujours dans le bon état au moment d'être retournée pour produire un déplacement dans le sens voulu. (Autre argument : il y a \(2^n\) configurations et \(2^n\) telles suites croissantes ; comme la suite de déplacements détermine au plus une configuration, on a une injection des configurations vers les suites, qui est donc une bijection, sans avoir à vérifier l'état des pièces en remontant.) \(\blacksquare\)

Solution 5

On décrit explicitement le processus pour une configuration \(C\) quelconque. Supposons que \(C\) a \(k\) faces, aux positions \(1 \leq c_1 < c_2 < \cdots < c_k \leq n\).

Soit \(i\) le plus petit indice tel que \(c_i \geq k\). Les premières étapes retournent les pièces \(k, k+1, \ldots, c_i, c_i - 1, c_i - 2, \ldots, k\) dans cet ordre. On obtient alors une configuration à \(k - 1\) faces, aux mêmes positions qu'au départ sauf \(c_i\). Cette partie dure \(2(c_i - k) + 1\) étapes.

Ensuite le processus se répète ; par récurrence sur le nombre de faces, il s'arrête. De plus, si les \(c_i\) disparaissent dans l'ordre \(c_{i_1}, \ldots, c_{i_k}\), le processus complet dure

\[\ell(C) = \sum_{j=1}^k \Big(2\big(c_{i_j} - (k + 1 - j)\big) + 1\Big) = 2\sum_{j=1}^k c_j - 2\sum_{j=1}^k (k + 1 - j) + k = 2\sum_{j=1}^k c_j - k^2\]

étapes.

Calculons la somme \(S_k\) des \(\ell(C)\) sur les \(\binom nk\) configurations à exactement \(k\) faces. Chaque \(1 \leq i \leq n\) apparaît comme un \(c_j\) exactement \(\binom{n-1}{k-1}\) fois (dénombrement). Donc

\[S_k = 2\binom{n-1}{k-1}\sum_{i=1}^n i - \binom nk k^2 = 2\,\frac{(n-1)\cdots(n-k+1)}{(k-1)!}\cdot\frac{n(n+1)}{2} - \frac{n\cdots(n-k+1)}{k!}\,k^2\]

\[= \frac{n(n-1)\cdots(n-k+1)}{(k-1)!}\big((n+1) - k\big) = n(n-1)\binom{n-2}{k-1} + n\binom{n-1}{k-1}.\]

La somme de \(\ell(C)\) sur toutes les configurations vaut donc

\[\sum_{k=1}^n S_k = n(n-1)\sum_{k=1}^n \binom{n-2}{k-1} + n\sum_{k=1}^n\binom{n-1}{k-1} = n(n-1)2^{n-2} + n 2^{n-1} = 2^n\,\frac{n(n+1)}{4}.\]

La moyenne cherchée est donc \(E(n) = \dfrac{n(n+1)}{4}\). \(\blacksquare\)