Shortlist 2006, C1¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : France
Concepts : Récurrence et constructions récursives · Invariants et monovariants
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 19 (page 20 du PDF)
Énoncé¶
We have \(n \geq 2\) lamps \(L_1, \ldots, L_n\) in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows:
— if the lamp \(L_i\) and its neighbours (only one neighbour for \(i = 1\) or \(i = n\), two neighbours for other \(i\)) are in the same state, then \(L_i\) is switched off;
— otherwise, \(L_i\) is switched on.
Initially all the lamps are off except the leftmost one which is on.
(a) Prove that there are infinitely many integers \(n\) for which all the lamps will eventually be off.
(b) Prove that there are infinitely many integers \(n\) for which the lamps will never be all off.
Indices : les idées clés
- (a) \(n = 2^k\) : la matrice \(A_k\) de l'évolution (\(2^k\) lignes) a une dernière ligne formée de \(1\) ; on le prouve par récurrence en découpant \(A_{k+1}\) en quatre blocs.
- Symétrie : la règle est symétrique gauche/droite ; le bloc \(C_k\) évolue comme \(A_k\) (ses voisins de gauche sont ses propres copies), et \(B_k\) est son image miroir.
- (b) \(n = 2^k + 1\) : après \(2^k\) étapes apparaît la deuxième ligne retournée ; l'évolution devient périodique sans jamais passer par l'état tout éteint.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2006 (une solution).
Solution¶
(a) Des essais pour de petits \(n\) amènent à conjecturer que tout \(n\) de la forme \(2^k\) convient. C'est bien le cas, et plus précisément : soit \(A_k\) la matrice \(2^k \times 2^k\) dont les lignes représentent l'évolution du système, avec des coefficients \(0\), \(1\) (pour éteint et allumé respectivement). La première ligne montre l'état initial \([1, 0, 0, \ldots, 0]\) ; la dernière ligne montre l'état après \(2^k - 1\) étapes. On affirme que :
La dernière ligne de \(A_k\) est \([1, 1, 1, \ldots, 1]\).
Cela suffit évidemment, car un pas de plus produit alors \([0, 0, 0, \ldots, 0]\), comme voulu.
La preuve se fait par récurrence sur \(k\). Le cas de base \(k = 1\) est évident. Supposons l'affirmation vraie pour un \(k \geq 1\) et écrivons la matrice \(A_{k+1}\) par blocs
avec quatre matrices \(2^k \times 2^k\). Après \(m\) étapes, le dernier \(1\) d'une ligne est en position \(m + 1\). Donc \(O_k\) est la matrice nulle. D'après l'hypothèse de récurrence, la dernière ligne de \([A_k \ O_k]\) est \([1, \ldots, 1, 0, \ldots, 0]\), avec \(2^k\) uns et \(2^k\) zéros. La ligne suivante est donc
Elle est symétrique par rapport à son milieu, et cette symétrie est conservée dans toutes les lignes suivantes, car le procédé décrit dans l'énoncé est symétrique gauche/droite. Donc \(B_k\) est l'image miroir de \(C_k\). En particulier, la colonne la plus à droite de \(B_k\) est identique à la colonne la plus à gauche de \(C_k\).
Imaginons la matrice \(C_k\) isolée du reste de \(A_{k+1}\). Supposons qu'elle évolue comme défini dans l'énoncé : le premier terme (le plus à gauche) d'une ligne ne dépend que des deux premiers termes de la ligne précédente, selon qu'ils sont égaux ou non. Replaçons maintenant \(C_k\) dans \(A_{k+1}\). Les termes « les plus à gauche » des lignes de \(C_k\) ont maintenant des voisins à gauche — mais ces voisins en sont des copies exactes. L'évolution réelle à l'intérieur de \(C_k\) est donc la même, que \(C_k\) soit considérée comme une partie de \(A_{k+1}\) ou isolément. Et comme la première ligne de \(C_k\) est \([1, 0, \ldots, 0]\), il s'ensuit que \(C_k\) est identique à \(A_k\).
La dernière ligne de \(A_k\) est \([1, 1, \ldots, 1]\) ; c'est aussi la dernière ligne de \(C_k\), donc aussi de \(B_k\), qui est le miroir de \(C_k\). La dernière ligne de \(A_{k+1}\) n'est donc formée que de uns, et la récurrence est complète.
(b) Il existe de nombreuses façons de produire une suite infinie de \(n\) pour lesquels l'état \([0, 0, \ldots, 0]\) ne sera jamais atteint. Par exemple, considérons \(n = 2^k + 1\) (pour \(k \geq 1\)). L'évolution du système se représente par une matrice \(A\) de largeur \(2^k + 1\) ayant une infinité de lignes. Les \(2^k\) premières lignes forment la matrice \(A_k\) étudiée ci-dessus, complétée à droite par une colonne de zéros.
À la ligne suivante, on a alors le vecteur \([0, 0, \ldots, 0, 1, 1]\). Mais c'est exactement la deuxième ligne de \(A\) retournée. Les lignes suivantes seront les images miroirs des précédentes, à partir de la deuxième. La configuration \([1, 1, 0, \ldots, 0, 0]\), c'est-à-dire la deuxième ligne de \(A\), réapparaîtra donc. Les lignes suivantes répéteront périodiquement ce motif, et il n'y aura jamais de ligne de zéros. \(\blacksquare\)