Rappel de l'énoncé

Pour  un poste de logicien, on a retenu les dix meilleurs candidats. Pour les départager, on leur propose l'épreuve suivante:

Les dix candidats sont enfermés dans une salle.

Certains d'entre eux ont une marque dans le dos. Personne ne peut voir s'il a une marque dans le dos mais chacun peut voir le dos des autres. Toute communication entre les candidats est interdite. Les candidats ne savent pas combien ils sont à avoir une marque dans le dos, ils savent seulement qu'il y en a au moins un d'entre eux.

Chaque minute, les portes entre la salle A où les candidats sont enfermés et une salle B s'ouvrent pendant quelques secondes, ce qui permet, à qui veut, de passer en salle B.

On donne une demi-heure aux candidats: à la fin de cette demi-heure, tous les candidats ayant une marque dans le dos (et uniquement eux) devront se trouver en salle B.

On a marqué 5 candidats. L'épreuve se déroule. Aucun mouvement n'a lieu lors des ouvertures de portes 1, 2, 3, 4. A la cinquième ouverture de portes, les cinq candidats marqués changent tous de salle. Et il n'y a ensuite plus aucun changement de salle.

Quel raisonnement ont pu faire nos candidats ?

Un trouveur

L'énigme a été résolue par Clément Arnould.

Résolution

Etape 1.

On commence par analyser la situation dans le cas où un seul candidat est marqué.

L'unique candidat marqué, ne voyant aucune personne marquée et sachant qu'il y a au moins une personne marquée, en déduit sans problème qu'il est marqué. Il sortira donc dès la première ouverture des portes.

Les autres candidats:

- ne sortent pas lors de la première ouverture. En effet, ils voyaient un candidat marqué et ne pouvaient donc pas savoir dans la première minute s'ils étaient marqués.

- ne sortent pas lors des ouvertures suivantes non plus. En effet, ils ont vu le candidat marqué sortir lors de la première ouverture et donc peuvent faire le raisonnement: "s'il est sorti, c'est qu'il savait qu'il était marqué et s'il a su cela c'est nécessairement qu'il n'a vu personne de marqué".

Etape 2.

Supposons maintenant qu'il y a deux personnes marquées.

- A la première ouverture, personne ne sort. En effet, chacun voit au moins un marqué et ne sait donc pas s'il est lui-même marqué.

- A la seconde ouverture, les deux marqués sortent. En effet, chaque marqué se dit: "si la personne marquée que je vois était seule marquée, elle aurait pu faire le raisonnement "étape 1" et sortir à la première ouverture. Il y a donc un autre marqué et ce ne peut être que moi".

- Les non marqués ne sortent pas. En effet, ils voient deux marqués et se disent donc: "S'ils sont seuls à être marqués, ils pourront faire les raisonnements (ci-dessus) et sortiront à la seconde ouverture. J'en déduirai que je ne suis pas marqué".

Etape 3.

Vous avez maintenant normalement saisi le principe. Rédigeons encore cette étape 3.

On suppose que trois personnes sont marquées.

- A la première et seconde ouverture, chacun voyant au moins deux marqués ne peut rien en déduire.

- A la troisième ouverture, chaque marqué sort. En effet, un marqué se dit: "si les deux marqués que je vois étaient les seuls à être marqués, ils auraient fait le raisonnement de l'étape 2 et seraient sortis à la seconde ouverture. Il y a donc un autre marqué et ce ne peut être que moi".

- Les non marqués ne sortent pas. En effet, ils voient trois marqués et se disent donc: "S'ils sont seuls à être marqués, ils pourront faire les raisonnements (ci-dessus) et sortiront à la troisième ouverture. J'en déduirai que je ne suis pas marqué".

Conclusion.

En poursuivant ainsi, on voit que lorsque n logiciens sont marqués, les n logiciens sortiront à l'ouverture n et aucun autre ne sortira.

Bien sûr, tout cela ne fonctionne que parce que chacun dans le groupe sait que les autres sont aussi des candidats au poste de logicien et part donc du postulat que les autres savent aussi raisonner.