La suite du précédent :
Un prisonnier tiré au hasard parmi N est amené chaque jour dans une pièce où se trouve une ampoule, allumée ou éteinte, dans l'état dans lequel l'a laissée le prisonnier précédent.
Les prisonniers seront libérés si l'un d'eux affirme un jour, avec raison, que tout le monde est déjà passé dans la pièce.
Les prisonniers ne communiquent pas entre eux, sauf au tout début, pour mettre au point une stratégie gagnante.

La stratégie adoptée est la suivante:
- le premier prisonnier allume la lumière chaque fois qu'elle est éteinte
- les autres l'éteigne, mais uniquement la première fois qu'ils la voient allumée.
Ce qui permettra a terme au premier d'affirmer que tout le monde est passé après N allumages de la lampe.

Comme l'a fait remarqué scrabblor, parfois le 1er à passer n'est pas le premier à savoir que tout le monde est passé.
http://www.prise2tete.fr/forum/viewtopi … 80#p185274



Pour N=2 par exemple, la séquence "1 2" suffit : 2 sait que quelqu'un est passé la veille, et ça n'est pas lui. La séquence la plus courte est donc "1 2" (impossible de faire moins, sinon tout le monde n'est pas passé)

Pour N=3, la séquence "1 2 3" suffit aussi : 3 voit la lumière éteinte, il sait donc qu'en 2 jours quelqu'un l'a allumé, puis éteinte, donc que 1 et 2 sont passés.
(et encore une fois, impossible de faire moins).

La question est la suivante : pour N=4, 5, ...., jusqu'à 10 mettons, quelle est la séquence la plus courte qui permette à un prisonnierautre que le premier d'affirmer que tout le monde est passé, et ce avant le premier.

Je ferai un tableau de score en fonction des réponses. En cas d'égalité, un petit bonus pour le rang le plus élevé possible pour le prisonnier qui fait l'affirmation
(ex : "1 séquence de 10 coups avec 2 qui affirme à la fin" vaut moins que "une séquence de 10 coups avec 3  qui affirme à la fin", qui elle même vaut moins que "une séquence de 9 coups avec 2 qui affirme à la fin")



Klim : 1er