Solution au problème de novembre 2004
Ce mois-ci, nous nous transportons au Mathematikum de Giessen, en Allemagne, le musée des mathématiques. Une des expositions montre une lampe et un bouton placés sur chacun des sommets d'un heptagone régulier. Pousser sur un quelconque des 7 boutons change l'état de la lampe associée (si elle était éteinte, elle s'allume; si elle était allumée, elle s'éteint), mais aussi l'état des deux lampes placées sur les sommets voisins. Si, au depart, toutes les lampes sont éteintes, combien de boutons faut-il pousser pour allumer toutes les lampes? Dans quel ordre faut-il les pousser?
On peut bien sur généraliser le problème à n lampes et n boutons:
En chacun des sommets d'un n-gone régulier convexe (n ≥ 3),
on a placé une lampe et un bouton. Le fait de pousser sur un
quelconque des n boutons change l'état de la
lampe associée (si elle était éteinte, elle s'allume;
si elle était allumée, elle s'éteint), mais aussi
l'état des deux lampes placées sur les sommets voisins.
Au départ, toutes les lampes sont éteintes. Si on veut qu'elles soient toutes allumées en même temps, on va devoir pousser un certain nombre de fois sur certains des n boutons. Quel est, exprimé en fonction de n, le nombre minimum de pressions sur des boutons permettant d'obtenir ce résultat? Montrez comment le faire, et donnez un argument montrant qu'on ne peut le faire en poussant moins de boutons.
Solution au MP45
Nous avons reçu des solutions correctes de Alexander Akulov (Regina), Pierre Bornsztein (France), Xavier Hecquet (France), Wolfgang Kais (Allemagne), Patrick LoPresti (Etats Unis), and Juan Mir Pieras (Espagne).
Nous passons tout de suite au problème général où il y a n boutons et n ampoules. Au départ toutes les ampoules sont éteintes. Nos correspondant ont tous noté qu'on doit changer l'état de toutes les ampoules un nombre impair de fois pour arriver à une situation où toutes les ampoules sont allumées. L'ordre dans lequel on appuie sur les boutons n'importe donc pas, seulement l'ensemble des boutons choisi. De plus, appuyer sur un bouton deux fois a le même effet que ne pas le toucher du tout, donc dans une solution optimale on n'appuie sur aucun bouton plus d'une fois. Fort de ces observations, trois de correspondants se sont servi d'arithmétique binaire et les autres ont poursuivi en mode informel. Nous allons présenter les deux approches.
La démonstration d'Akulov, Kais, et Mir.
Chaque ampoule est influencée par trois boutons, et
chaque bouton influence trois ampoules. Si on appuie chaque bouton
une fois, chaque ampoule change d'état trois fois donc à la fin
toutes les ampoules sont allumées. La question est de savoir si on
peut atteindre cet état en poussant moins de boutons. On peut changer
l'état de chaque ampoule une seule fois en appuyant n/3 boutons,
ce qui est possible lorsque n est un multiple de 3. Dans les autres
cas, il existe au moins une ampoule dont on doit changer l'état trois
fois, en appuyant sur les trois boutons qui l'influencent. Cependant
les deux ampoules voisines se trouvent alors éteintes, et on doit
appuyer sur les autres boutons qui
les influencent pour les réallumer. On commence ainsi une réaction
en chaîne qui nous mène à appuyer sur tous les boutons. On obtient
donc la conclusion suivante:
Si n est un multiple de trois, on peut allumer toutes les ampoules en appuyant sur n/3 boutons. Autrement on doit appuyer sur tous les boutons. En particulier, lorsque n = 7, on doit appuyer sur tous les boutons une fois (dans n'importe quel ordre) pour allumer toutes les ampoules.
La démonstration de Bornsztein, LoPresti et Hecquet.
Un étiquette les boutons 0, 1, ..., n - 1 consécutivement dans le sens anti-horaire. Soit xk, le nombre de fois que l'on appuie sur le bouton k (donc xk ε { 0, 1 }). L'état terminal de l'ampoule dépend de la valeur xk-1 + xk + xk+1 (où les indices sont modulo n). Par conséquent, toutes les ampoules seront allumées si et seulement si la somme de tous les triplets de variables consécutives est impaire. Ainsi, pour tout triples consécutif xk-1, xk, xk+1, la valeur de xk+1 est uniquement déterminée par celles de xk-1 et de xk. Il existe quatre façons de donner des valeurs initiales à (x0, x1), soit (0,0), (0,1), (1,0) et (1,1). La règle énoncée plus haut permet d'en déduire toute la suite x0, x1, x2, x3, ... On a donc quatre solutions possibles:
0,0,1,0,0,1,0,0,1,...
0,1,0,0,1,0,0,1,0,...
1,0,0,1,0,0,1,0,0,...
1,1,1,1,1,1,1,1,1,...
Les trois premières solutions sont consistantes seulement
lorsque n est un multiple de 3. La quatrième solution est valide
en tout temps. On obtient ainsi la même conclusion
qu'avec l'autre approche.
Commentaire
L'argument de LoPresti était plus long, mais il a également
démontré que lorsque n n'est pas un multiple de 3, chacune des
2n configurations d'ampoules allumées et éteintes peut être
réalisée en appuyant sur les boutons appropriés. Par contre lorsque
n est un multiple de 3, certaines configurations ne peuvent pas etre
atteintes. Il affirme de plus pouvoir démontrer qu'on peut toujours
allumer toutes les ampoules, indépendemment de la façon dont
elles sont connectées (notre problème correspond au cas ou les
ampoules sont connectées en cycle). Bornsztein mentionne aussi cette
généralisation, pour laquelle il donne la référence suivante:
K. Sutner, Linear cellular automata and the Garden-of-Eden, The Mathematical Intelligencer, 12:2 (1989), p. 49-53.
Il dit que la démonstration donnée dans cet article peut être beaucoup simplifiée, mais que le nombre minimal d'opérations nécessaires n'est pas encore connu.