Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » L'échiquier du diable Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=extasy300]Ahemm, j'espère vraiment que je ne me suis pas totalement planté haha : Selon moi, le principe de départ sur lequel Alice et Bob devraient fonder tout leur système est le suivant : puisque le diable leur demande de trouver une stratégie sûre, c'est qu'elle doit exister. Or il apparaît tout un ensemble de conditions dans lesquelles une stratégie garantie gagnante n'est pas envisageable : Si on imagine qu'il y a trois pierres qui sont disposées sur l'échiquier et que la case mystère est recouverte par l'une d'entre elles, on peut "difficilement" s'en sortir avec une astuce : si alors Alice tente de retirer la pierre de la case mystère, il en restera deux et il sera impossible pour Bob de savoir si la case mystère se trouve sur l'une de ces deux pierres ou sur une quelconque autre case. Il en va de même pour n'importe quel nombre plus grand de pierres qui seraient réparties de manière aléatoire. Alice et Bob auraient beau essayer, jamais ils ne trouveraient de stratégie dans de telles conditions. Partant de ce constat, et repensant à la requête du diable de trouver une stratégie sûre, et posant l'existence d'une telle stratégie, ils conviendront que le diable aura disposé les pierres et choisi la case mystère de manière à ce qu'ils puissent infailliblement trouver la solution. Alors, ils se mettront à examiner les conditions dans lesquelles une stratégie permettrait de faire deviner la bonne case à tous les coups : Premier cas : s'il n'y a pas de pierre sur l'échiquier, alors il faudra qu'Alice dépose une pierre sur la case mystère. Conclusion : si Bob ne trouve qu'une seule pierre sur l'échiquier, c'est que là se trouve la case mystère. Second cas : Il y a une pierre sur l'échiquier. Si elle se trouve sur la case mystère, ne toucher à rien. Si elle se trouve autre part, il n'existe aucun moyen d'indiquer la bonne case. Alors elle ne se trouvera pas autre part. Conclusion : une fois encore, s'il n'y a qu'une seule pierre sur l'échiquier, c'est la bonne case. Troisième cas : Il y a plus d'une pierre sur l'échiquier. La case mystère se trouve ou non sous l'une de ces pierres. Alice et Bob savent déjà que l'arrangement des pierres ne peut être chaotique. S'il y a plus d'une pierre sur l'échiquier, alors celles-ci doivent être "ordonnées" d'une manière ou d'une autre ; et alors, le seul élément de désordre qui apparaîtra dans la configuration des pierres contiendra la solution du problème. Mais quel peut être l'ordonnancement des pierres ? Cas simple des lignes : Alice et Bob se disent que si les pierres forment des lignes simples, horizontales, verticales ou diagonales, et que la case mystère se trouve "loin" ailleurs, il suffira de poser une pierre dessus et la case se distinguera alors, son isolation exprimant sa présence. A présent qu'ils ont étudié le cas où la case mystère se trouve isolée d'une série de cases et de pierres ordonnées en lignes simples, Alice et Bob s'intéressent au cas où la case mystère se trouverait sur l'une de ces pierres. Ils pourraient penser à "retirer" la pierre de la case, et l'espace laissé entre deux lignes indiquerait la présence de la case mystère. Ainsi, Alice et Bob essaieraient de s'entendre sur une stratégie d'isolation de la case mystère, et cette isolation pourrait se manifester de deux manières : soit une pierre qui n'est pas en contact avec les autres, soit un trou qui suggère sans ambiguïté de par sa présence celle de la case mystère. Leur système d'isolation de case dans le cas de lignes se traduit alors ainsi : Est considérée comme isolée une case qui n'a strictement aucun contact avec une ligne de cases sur laquelle s'étend une ligne de pierres. Une case isolée est une case remarquable, de par sa manifestation évidente sous forme d'une pierre isolée des autres pierres ou d'une case d'espace vide isolée des autres espaces vides. Si une case est remarquable, alors il s'agit de la case mystère. Arrivés là, Alice et Bob ont achevé le plus gros de leur travail. Mais leur vision s'étend tout à coup : et si des lignes de cases, ils élargissaient leur théorie au cas des surfaces, ou "blocs" de cases ? Ils supposent un bloc de cases rempli de pierres, puis très vite généralisent aux cas de plusieurs blocs de cases remplies de pierres occupant plusieurs surfaces de l'échiquier. Si la case mystère est isolée de tous les blocs, alors il suffira de déposer une pierre dessus. Si elle se trouve à l'intérieur d'un des blocs et qu'il est possible d'isoler cette case en retirant une pierre de manière à marquer sa présence par un trou, et à condition que ni ce bloc ni aucun autre bloc ne soit doté de trous, alors ce seul trou représentera la case mystère. Evidemment, si l'ensemble de l'échiquier est plein, il suffira de retirer la bonne pierre, et s'il n'y a qu'une seule case libre sur tout l'échiquier, alors ce sera forcément celle de la case mystère et il ne faudra toucher à rien. Et enfin, alors qu'ils ont presque terminé, Alice et Bob s'arrêtent encore à une dernière éventualité, celle où les choses s'arrangeraient d'une telle façon que Bob se retrouverait face à un échiquier composé d'un bloc avec un trou et d'une pierre isolée. En effet, Alice et Bob s'imaginent que le diable serait capable de leur jouer un pareil coup : il lui suffirait, par exemple, de créer un carré de pierres de neuf cases, puis de retirer la pierre centrale de manière à laisser un trou à sa place, et enfinyy de choisir comme case mystère n'importe quelle case éloignée du bloc. Alice serait alors forcée de déposer une pierre sur cette case, sans pouvoir effacer le trou au milieu du bloc. Mais ils trouvent rapidement une astuce : la pierre isolée l'emportera sur le trou. Alors, Alice et Bob résument leur stratégie collective en un unique principe : Pour trouver la solution au problème, il faut isoler une case. Et s'assurent de la complétude d'un tel système en le recouvrant d'un unique axiome : S'il existe une solution au problème, alors il existe une case isolée. Et ils résument leurs stratégies individuelles ainsi : Pour Alice, isoler la case mystère, soit en ajoutant une pierre et en créant une pierre isolée, soit en retirant une pierre et en créant un vide isolé, un trou ; soit encore en laissant l'échiquier intact si la case mystère apparaît déjà isolément. Pour Bob : repérer la case qu'Alice a isolée par la pierre ou par le trou, en se rassurant par le fait que si Alice n'a touché à rien, alors il devra quand même exister une case isolée. Et s'ils n'y arrivent pas, alors c'est que les dés sont pipés et que le diable ne voulait pas qu'ils réussissent (ou que je suis con ^^). EDIT : ah bah non, je me suis planté. J'ai pensé à faire le même raisonnement mais en partant à l'envers, en accordant la primauté au trou sur la case pleine, en allant ainsi : Si toutes les cases sont pleines alors vider la case mystère ; s'il y a un trou alors ne pas toucher à l'échiquier, et s'il y a plusieurs trous ordonnés en lignes et ou en blocs, remplir la ligne ou le bloc par une pierre si la case mystère s'y trouve, et vider la case mystère si elle se trouve sur une case pleine. Et alors dans le cas où on trouverait un trou et une case pleine, ce serait le trou qui aurait la primauté et donc c'est là que se trouverait la case mystère, non ? Alors du coup je ne comprends plus rien. Comment interpréter le cas d'un échiquier rempli de pierres sauf dans un carré de huit cases vides et d'une case pleine (disons au centre), et où la case mystère se trouverait sur une case pleine quelconque en dehors dudit carré ? Alors si la primauté revient à la case pleine, Alice ne peut pas retirer la pierre de la case mystère car elle deviendrait un trou ; et si la primauté est accordée au trou sur la case pleine, alors un échiquier vide sauf dans un carré de huit cases pleines et une case vide (toujours la centrale), où la case mystère serait une case vide quelconque en dehors dudit carré, la case mystère serait marquée par une case pleine et non un trou. Que faire ? Comparer la surface pleine et la surface vide de l'échiquier, et accorder la primauté à la case pleine s'il la surface pleine supérieure à la surface vide ; et accorder la primauté au trou si la surface vide est inférieure à la surface pleine ? Je ne sais pas pourquoi je propose ça... Et puis il y a le cas d'un échiquier équitablement proportionné en surfaces vide et pleine : imaginons un échiquier rempli de pierres sur toute la surface gauche et vide sur tout la surface droite. Si la case mystère se trouve sur la surface vide, alors il suffirait d'y déposer une pierre, et si elle se trouve sur la surface pleine, il suffirait d'y retirer une pierre. Sauf qu'il semble exister deux cas impossibles à résoudre : Une moitié de surface pleine sauf sur une case, avec la case mystère se trouvant sur une case de la surface vide. Alors il faudrait déposer une pierre dessus et accorder à la pierre la primauté sur le trou. Une moitié de surface vide sauf sur une case, avec la case mystère se trouvant sur une case de la surface pleine. Alors il faudrait retirer la pierre dessus et accorder au trou la primauté sur la pierre. En gros, si on a un échiquier avec une moitié de surface pleine creusée par un trou et une surface vide remplie par une pierre, on ne saura jamais où se trouve la case mystère : sur le trou entouré de pierres ou sous la pierre entourée de trous, parce qu'on saura pas si c'est le trou ou la pierre qui l'emporte. J'avoue que je suis perdu ^^ (et je n'ai pas envie de supposer que nos deux amis seront assurés de ne pas tomber non plus sur ce cas sous prétexte que c'est encore impossible à résoudre. A l'aide...)[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Pim, Pam et ? Retour Résumé de la discussion zobizob 13-11-2017 17:02:38 Le diable propose à Alice et Bob un défi afin de tester leur logique. Il convoque d'abord Alice et lui présente un échiquier sur lequel sont posé des pierres sur certaines cases. Il montre alors à Alice une case "mystère" et lui laisse la possibilité de changer l'état d'une case. Alice peut donc rajouter une pierre sur une case vide ou au contraire enlever la pierre présente sur une case, ou laisser l’échiquier comme ça, mais dans tous les cas elle ne peut changer la valeur que d'une seule case. Une fois Alice partie, Bob est convoqué à son tour et le diable lui demande de lui désigner la case mystère. Précisions : Évidement aucun contact n'est autorisé entre Alice et Bob une fois le défi commencé. En revanche, Alice et Bob peuvent se mettre d'accord sur une stratégie à suivre avant le début du défi. Le diable est libre de choisir la disposition initiale de l’échiquier ainsi que la position de la case mystère. La case mystère peut être n'importe quelle case de l'échiquier. Quelle stratégie faut-il mettre en place pour être sûr de trouver la case mystère à tous les coups ? Pied de page des forums P2T basé sur PunBB Screenshots par Robothumb © Copyright 2002–2005 Rickard Andersson
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact