Petite enigme
Hier, on m’a presente l’enigme suivante:
Enonce
Il y a une salle, avec un interrupteur unique, qui allume une lampe unique. Cette lampe ne chauffe pas.
10 personnes sont dans la salle d’attente.
Une personne est appelee de maniere aleatoire. Elle peut allumer et eteindre la lampe, mais pas communiquer d’une quelconque maniere avec les autres membres du groupe. Ensuite elle retourne au groupe, et une autre personne est appellee.
Les personnes peuvent discuter avant l’epreuve pour mettre au point une strategie.
Question: comment faire pour qu’a un moment donne, une personne puisse affirmer “nous sommes deja tous passes au moins une fois”?
Solution
Soit n le nombre de personnes presentes initialement. Il est possible de restreindre initialement le probleme: en effet, il est equivalent que n=10 ou si n=4, voire meme n=3. En dessous de ce chiffre le probleme ne se pose evidemment plus.
Il y a deux facons d’aborder l’enigme. La premiere consiste a voir les 4 personnes comme des “pairs” (peers), chacun etant “egal” aux autres. Cette voie, que j’ai exploree, ne m’a pas permis de deboucher sur une solution.
La seconde facon consiste a considerer que parmi les 4, il y a 3 bonhommes “normaux“, egaux entre eux, et 1 “super“-bonhomme, avec des droits de “super user”.
Accordons donc les droits suivants:
- chaque bonhomme “normal” a le droit d’allumer une, et une seule, fois la lampe, a un moment bien choisi.
- le “super” bonhomme est le seul a avoir le droit d’eteindre la lampe.
Voici donc l’algorithme de resolution:
- Lorsqu’un bonhomme “normal” est appele:
- Si la lumiere est deja allumee, il ressort.
- Si la lumiere est eteinte et que le bonhomme courant n’a jamais allume la lampe, alors il l’allume.
- (De cette maniere, on s’assure que le bonhomme normal allume au plus une fois.)
- Le “super” user initialise un compteur a 0. Lorsque le super user est appele:
- Si la lumiere est deja allumee, il incremente son compteur, et il eteint la lumiere.
- Si la lumiere est eteinte, il ressort.
D’un point de vue mathematique, on se trouve face a un univers de probabilites discretes. D’apres la loi faible des grands nombres, au bout d’un temps suffisament long, le compteur atteint le nombre d’utilisateurs “normaux” (autrement dit: n-1, lui-meme sachant qu’il est deja passe). Il peut alors s’exclamer: “nous sommes tous deja passes au moins une fois!”.