Enigme : Les yeux verts [Solution]

Voici donc la solution à l’énigme des yeux verts. Ça va c’était pas trop difficile ?
La réponse est :

Les 100 personnes aux yeux verts partent au bout de 100 jours, et les autres restent sur l’île.

Le plus intéressant reste d’expliquer pourquoi. Pour cela on va réduire le problème à un cas extrême, puis remonter jusqu’à obtenir une solution générale.
Supposons qu’il y ait une personne A avec les yeux verts et 100 avec les yeux bruns. A ne sait pas sa propre couleur et n’a aucune raison de supposer qu’il a les yeux verts. Voyant 100 personnes avec les yeux bruns il aurait plutôt des raisons de penser que les siens sont bruns, mais ça non plus il ne peut en être sûr. Le Grand Prêtre annonce voir quelqu’un avec les yeux verts. Pour les 100 aux yeux bruns qui eux voient 1 personne aux yeux verts et 99 bruns, l’annonce n’apporte rien (en fait si, voir plus bas). Pour A, ne voyant personne aux yeux verts, il en déduit que c’est lui qui les a verts et part donc le soir même.
Ainsi avec 1 aux yeux verts et les autres bruns, celui aux yeux verts part le 1er jour. Ce cas de base n’est pas très intéressant.
Supposons maintenant qu’il y ait deux personnes A et B aux yeux verts et 100 aux yeux bruns. A et B voient chacun une personne aux yeux verts et 100 aux yeux bruns. Vient l’annonce du Grand Prêtre. A tient le raisonnement suivant : « Si j’ai les yeux bruns, B ne voit personne avec les yeux verts et partira donc ce soir ». B tient le même raisonnement. Le lendemain voyant chacun que l’autre n’est pas parti, ils s’en vont tous deux.
Ainsi avec 2 aux yeux verts et les autres bruns, les deux aux yeux verts partent le 2e jour. On commence à voir le schéma.
Un troisième pour la route : 3 aux yeux verts, A B et C, et 100 aux yeux bruns. A voit B et C aux yeux verts et tient le raisonnement suivant : « Si j’ai les yeux bruns, B et C partiront le deuxième jour (cf le cas d’avant) ». B et C tiennent le raisonnement identique. Arrivé au 3e jour, A B et C en déduisent qu’ils ont les yeux verts et partent.
On voit ainsi par une simple récurrence, qu’avec k personnes aux verts, ils partent tous au k-ème jour. Et ceux aux yeux bruns alors ? Le k+1-ème jour quand tous leurs potes aux yeux verts sont partis, ce serait tentant pour eux de partir en clamant qu’ils ont les yeux bruns. Mais ils ne peuvent pas le prouver, chacun pouvant avoir une autre couleur (jaune, bleu, ou n’importe autre que vert).

La beauté de cette énigme vient surtout de l’apport du Grand Prêtre qui, face à 100 personnes aux yeux verts et 100 aux yeux bruns, affirme « Je vois quelqu’un aux yeux verts ». Cette phrase semble évident pour tous, après tout, chacun voit au moins 99 personnes aux yeux verts. Alors à quoi sert réellement cette déclaration qui semble n’ajouter aucune information ?
Pour mieux saisir la clé du problème, regardons encore une fois des cas simples.
– A et B aux yeux verts. A et B (qui se voient l’un l’autre) savent qu’il y une personne aux yeux verts. Mais A ne sait pas que B voit une personne aux yeux verts. La connaissance « il existe une personne aux yeux verts » n’est que sur un seul rang, si je peux l’exprimer maladroitement ainsi.
– A B C aux yeux verts. A voit B et C aux yeux verts. A sait qu’il y a 2 ou 3 personnes aux yeux verts. A sait que B voit 1 ou 2 personnes aux yeux verts. Pour A, si B voit 1 personne aux yeux verts, il y en a en fait 2 ; si B voit 2 personnes aux yeux verts, il y en a en fait 3. Pour A, si B ne voit qu’une personne aux yeux verts, A sait que B pense « il y a 1 ou 2 personnes aux verts, et C voit 0 ou 1 personne aux yeux verts. Si C voit 0 personne aux yeux verts, pour C il y a 0 personne aux yeux verts ou il n’y en a qu’une. »
L’affirmation du Grand Prêtre réduit ces deux dernières possibilités en une seule. Avant ça, A ne savait pas si B savait que C savait qu’il y avait quelqu’un aux yeux verts sur l’île. Après sa déclaration, A sait que B sait que C sait qu’il y a des yeux verts sur l’île, et l’induction peut commencer. Le fait qu’il y ait des yeux verts sur l’île est passé en connaissance commune (common knowledge).

Quant aux yeux bruns, après que tous les yeux verts soient partis le 100e jour, ils ne peuvent quitter l’île le lendemain, le fait que quelqu’un ait les yeux bruns n’étant pas en connaissance commune. Un exemple simple serait de voir avec 100 aux yeux verts et 2 aux yeux bruns, A et B. On a vu que les 100 aux yeux verts partaient au bout de 100 jours. Le 101e jour, A et B sont seuls sur l’île. A et B voient chacun quelqu’un aux yeux bruns. A sait donc qu’il y a des gens aux yeux bruns. Mais A ne sait pas que B le sait. Si A avait les yeux jaunes par exemple, B ne pourrait pas savoir qu’il y a des gens aux yeux bruns. Et au final, aucun des deux ne pourra partir. Bref, pas besoin de continuer au rang supérieur, vous avez compris le principe.
Le Grand Prêtre non plus ne pourra jamais quitter l’île. Même s’il avait lui-même les yeux verts ; les habitants savent bien que le Grand Prêtre ne peut pas voir ses propres yeux.

J’ai rencontré cette énigme sur le site XKCD, dont l’auteur (qui n’est pas non plus l’inventeur) la présente comme le problème de logique le plus dur au monde. Le plus intéressant était sur le forum le sujet qui lui était consacré. Ce thread avait en effet une particularité que j’ai trouvée captivante et amusante. Bien que l’explication y a été détaillée et discutée de long en large des pages durant, à chaque fois quelqu’un y débarque, affirmant avoir lu la solution mais avoir trouvé une « faille » dans le raisonnement, ou une « solution alternative » complètement différente. Il présente alors sa réponse miracle à laquelle il s’accroche, jusqu’à ce que quelqu’un, un membre récurrent du sujet habituellement, finisse par le convaincre de la fausseté de son raisonnement. Et ce sur plus de 1000 messages pendant près de 7 ans ! Le plus beau dans tout ça, c’est qu’à chaque fois, les gens reconnaissent ensuite leur erreur, ce qui sur le net est suffisamment rare pour être signalé.

Publicités
Cet article, publié dans Enigme, est tagué . Ajoutez ce permalien à vos favoris.

4 commentaires pour Enigme : Les yeux verts [Solution]

  1. Clément Naar dit :

    J’ai trouvé une faille dans le raisonnement ! Plus sérieusement, il y a un point que je comprends mal. C’est à propos du paragraphe suivant :

    « A B C aux yeux verts. A voit B et C aux yeux verts. A sait qu’il y a 2 ou 3 personnes aux yeux verts. A sait que B voit 1 ou 2 personnes aux yeux verts. Pour A, si B voit 1 personne aux yeux verts, il y en a en fait 2 ; si B voit 2 personnes aux yeux verts, il y en a en fait 3. Pour A, si B ne voit qu’une personne aux yeux verts, A sait que B pense « il y a 1 ou 2 personnes aux verts, et C voit 0 ou 1 personne aux yeux verts. Si C voit 0 personne aux yeux verts, pour C il y a 0 personne aux yeux verts ou il n’y en a qu’une. »
    L’affirmation du Grand Prêtre réduit ces deux dernières possibilités en une seule. Avant ça, A ne savait pas si B savait que C savait qu’il y avait quelqu’un aux yeux verts sur l’île. Après sa déclaration, A sait que B sait que C sait qu’il y a des yeux verts sur l’île, et l’induction peut commencer. Le fait qu’il y ait des yeux verts sur l’île est passé en connaissance commune (common knowledge). ».

    Dans le cas de 3 personnes, je comprends ce qu’il se passe. Mais s’ils sont 100 à avoir les yeux verts, personne sur l’île ne pouvait ignorer qu’il existait des personnes avec des yeux verts. Ni A, ni B, ni C, ni D, ni Z. A sait forcément que B sait que C sait que … que Z sait que quelqu’un a les yeux verts.

    D’ailleurs, même dans le cas de 3 personnes, ce raisonnement à ses limites. Cette idée se base sur l’hypothèse suivante : « si B ne voit qu’une personne aux yeux verts ».
    Oui mais dans le cas réel de cette île où ils sont 3 à avoir les yeux verts, B voit deux personnes aux yeux verts. Donc sous cette hypothèse, A sait que B pense : « il y a 2 ou 3 personnes aux yeux verts, et C voit 1 ou 2 personnes aux yeux verts. »
    Donc dans ce cas là, même C sait qu’il y a au moins une personne avec les yeux verts. Donc le grand prêtre n’a rien initié du tout !

    Bref, je me doute que quelqu’un a déjà plus ou moins dit la même chose et qu’on lui a expliqué qu’il avait tort, mais justement j’ai besoin d’explications là 😀

    • 0rpheoh dit :

      Hello !
      Que ce soit avec 3 ou 100 personnes, il manque un « cran » pour commencer l’induction, que donnr le Grand Prêtre.
      Pour reprendre ton dernier exemple d’un cas avec 3 personnes aux yeux verts :
      – B voit effectivement 2 personnes aux yeux verts.
      – Mais A ne sait pas la couleur de ses propres yeux ! A voit C et B voit C, donc A sait que B voit la couleur des yeux de C.
      – Ainsi pour A, B voit 1 ou 2 personnes aux yeux verts.
      – De même pour C, A sait que C voit 1 ou 2 personnes aux yeux verts. Mais ce que A sait n’importe pas, ce qui compte c’est ce les autres savent à partir des informations que lui a.
      Mettons-nous dans la tête de A :
      « Je vois B et C aux yeux verts. Donc B voit C aux yeux verts. Pour B, il y a au moins une personne aux yeux verts. Mais que pense C pour B ? C voit les yeux de B mais B ne sait pas ses propres yeux, donc pour B, C pourrait ne voir aucune personne aux yeux verts. Je sais que c’est faux mais B ne le sait pas. Et ce indépendamment du fait que j’ai ou non les yeux verts. »
      Ainsi pour A, B pense que C voit 0 ou 1 personne aux yeux verts. L’annonce du Grand Prêtre alors ces deux possibilité à une seule et l’induction se lance.

      • Clément Naar dit :

        Hello et merci de ta réponse ! J’ai bien compris ce cas là, mais encore une fois je ne vois pas en quoi il est valable au delà de 3 personnes.
        Prenons le cas avec 4 personnes, A, B, C et D aux yeux verts. Je copie colle ton commentaire en changeant juste les valeurs.

        – B voit effectivement 3 personnes aux yeux verts.
        – Mais A ne sait pas la couleur de ses propres yeux ! A voit C et D et B voit C et D, donc A sait que B voit la couleur des yeux de C et D.
        – Ainsi pour A, B voit 2 ou 3 personnes aux yeux verts.
        – De même pour C, A sait que C voit 2 ou 3 personnes aux yeux verts. Mais ce que A sait n’importe pas, ce qui compte c’est ce les autres savent à partir des informations que lui a.
        Mettons-nous dans la tête de A :
        « Je vois B, C et D aux yeux verts. Donc B voit C et D aux yeux verts. Pour B, il y a au moins deux personne aux yeux verts. Mais que pense C pour B ? C voit les yeux de B et D.  »

        Et c’est là que j’ai l’impression que tout change par rapport au raisonnement : B a beau ne pas connaitre la couleur de ses propres yeux, il ne peut à aucun moment penser que C pourrait ne voir aucune personne aux yeux verts (il y a au moins D). Et idem pour D qui lui voit au moins C.

      • 0rpheoh dit :

        C’est parce qu’en rajoutant une personne, il faut aller un cran plus loin. Ca complique pour l’écrire mais le raisonnement est le même.
        Mettons-nous dans la tête de A :
        « Je vois B, C et D aux yeux verts. B voit C et D aux yeux verts. Mais que penserait B alors ? Si je me mettais dans sa tête, il penserait que C voit au moins une personne aux yeux verts (D). Mais que penserait D pour C (toujours du point de vue de B) ? D voit les yeux de C mais C ne sait pas ses propres yeux, donc pour C, D pourrait ne voir aucune personne aux yeux verts. B sait que c’est faux mais C ne le sait pas »
        Les guillemets sont la pensée de A. Dans ma réponse précédente on avait A qui imaginait ce que B pensait que C voyait ; ici on a A qui imagine ce que B imagine ce que C pense que D voit.
        En résumé (je tente une reformulation pour rendre toute cette confusion un poil plus clair xD),
        – Il y a 4 personnes yeux verts (rang absolu que personne ne peut déduire sans apport extérieur)
        – Pour A, il y a 3 ou 4 personnes aux yeux verts (il en voit 3 et ignore les siens)
        – A va imaginer ce que B pense : Pour A, B pense qu’il y a au moins 2 personnes aux yeux verts (C et D), donc 2 ou 3 (B ignorant les siens) ou 4 (si A a les yeux verts)
        – A va imaginer ce que B va imaginer que C pense : « B sait que pour C il y a au moins 1 personne aux yeux verts (D), mais si C n’avait pas les yeux verts, D pourrait ne voir personne aux yeux verts » (on est dans le point de vue de A qui imagine B imaginant C, les couleurs des yeux de A et B ne sont donc pas connues).
        Donc A imagine que B imagine que C pourrait penser que D ne voit aucune personne aux yeux verts ! Sans cette connaissance commune de l’existence de la couleur verte, ils n’ont aucune raison de commencer l’induction (qui est de se dire 1 pers. part le 1er soir, 2 pers. partent le 2e soir, etc.)
        Arrive l’annonce du Grand Prêtre.
        L’existence d’une personne aux yeux verts passe en connaissance commune. On sait donc (relire le début de la solution) qu’une fois en connaissance commune, s’il y a 1 seule personne aux yeux verts elle partira le 1er soir, s’il y en a 2 au 2e soir, etc. Chacun en voyant 3 autres aux yeux verts, on trouve alors que A, B, C et D partiront le 4e soir.

        A ce stade je sais plus si c’est plus clair ou plus confus à chaque reformulation, hésite pas à me redemander :p

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s