Si les mathématiciens s'occupaient de signalisation routière, chaque feu de circulation serait controlé par un panneau comportant trois boutons à trois positions. Chaque bouton aurait ses positions numerotées 0, 1, 2, et le feu de circulation obéirait aux règles suivantes:

1. La couleur (rouge, jaune ou vert) du feu allumé dépend seulement de la position des trois boutons.
   
2. Lorsqu'on tourne les trois boutons en même temps, la couleur du feu allumé change nécessairement.

Supposons que vous vous trouvez devant un tel panneau. Initialement, les trois boutons sont en position 0 et le feu est au rouge.

Vous tournez le premier bouton en position 1 et le feu vire au jaune.

Qu'arrive t'il maintenant si vous tournez le deuxième bouton en position 2?

En fait, pouvez vous dire à quelle couleur du feu correspond chaque position des boutons?

 

Solution au problème MP40

Nous avons reçu des solutions de Pierre Bornsztein (France), Gilles Feyrit (France), Wolfgang Kais (Allemagne), Patrick LoPresti (Etats Unis), Antoine Merle (France), et Juan Mir Pieras (Espagne). La réponse:

Le feu demeure jaune lorsque le deuxième interrupteur est changé à la deuxième position. La couleur du feu allumé dépend seulement de la position du premier interrupteur. 

(En passant, ce problème explique un peu pourquoi ça prend plusieurs mathématiciens pour changer une ampoule.)

Seulement la notation diffère dans les solutions soumises. Le problème peut être exprimé en termes d'un graphe (tel que dans la référence ci-haut), ou d'un tableau (comme ci-bas). On donne la liste des 27 positions, et on place un X dans chacune des cases correspondant à une couleur éliminée par la règle 2. Par exemple, puisque la position 000 correspond à la couleur rouge, celle-ci se trouve éliminée dans toutes les positions ne comportant aucun 0. De même, la couleur jaune est éliminée de toutes les positions dont la première coordonnée est différente de 1 et les autres coordonnées différentes de 0. Ces informations se résument comme suit

	R	J	V		R	J	V		R	J	V
000	R			100		J		200
001				101				201
002				102				202
010				110				210
011		X		111	X			211	X	X	V
012		X		112	X			212	X	X	V
020				120				220
021		X		121	X			221	X	X	V
022		X		122	X			222	X	X	V

Puisque 211, 212, 221 et 222 ne correspondent ni à rouge, ni à jaune, ils doivent donc correspondre à vert, ce qu'on note en écrivant un V dans la colonne correspondante.

Avec quatre états verts connus de la forme 2BC, on peut ensuite déduire que tous les états de la forme 0(B ± 1)(C ± 1) et 1(B ± 1)(C ± 1) (où l'addition est modulo 3) ne sont pas verts. En fait, ce sont là tous les états commençant par 0 ou 1. De plus, on peut déduire que 011, 012, 021, et 022 sont rouges, et 111, 112, 121, et 122 sont jaunes.

	R	J	V		R	J	V		R	J	V
000	R		X	100		J	X	200
001			X	101			X	201
002			X	102			X	202
010			X	110			X	210
011	R	X	X	111	X	J	X	211	X	X	V
012	R	X	X	112	X	J	X	212	X	X	V
020			X	120			X	220
021	R	X	X	121	X	J	X	221	X	X	V
022	R	X	X	122	X	J	X	222	X	X	V

Ces nouvelles informations permettent de compléter la table: Tout triplet de la forme 0BC diffère d'au moins un parmi 111, 112, 121, et 122 dans toutes les positions, donc ne peut être jaune, et diffère d'au moins un parmi 211, 212, 221, et 222 dans toutes les positions, donc ne peut être vert. Par conséquent, le triplet 0BC est rouge. Par un raisonnement similaire, tout triplet de la forme 1BC est jaune, et tout triplet de la forme 2BC est rouge. Notre conclusion est la suivante:

Si le premier interrupteur est en position 0, le feu est rouge, s'il est en position 1, le feu est jaune, et s'il est en position 2, le feu est vert.

Gilles Feyrit a remarqué qu'il existe une symétrie qui nous permet une conclusion plus générale: dès qu'on connaît deux positions correspondant à deux couleurs différentes, et que ces deux positions diffèrent en une seule coordonnée, alors on sait que l'interrupteur correspondant à la coordonnée où les positions diffèrent contrôle à lui seul le feu de circulation. Par exemple, savoir que 211 correspond à vert et 110 correspond à jaune n'est pas suffisant, mais savoir que 210 correspond à vert et 110 correspond à jaune est suffisant. L'énoncé du problème de Alon et al. est encore plus général: "Etant donné n interrupteurs à trois positions contrôlant la couleur d'un feu de circulation, de telle sorte que si on change la position de tous les interrupteurs en même temps, la couleur du feu allumé change. Démontrez que le feu de circulation est contrôlant par un seul des interrupteurs." Le problème semble provenir de Hongrie dans les années 1970. Il admet aujourd'hui plusieurs généralisations.