Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 13-11-2017 17:02:38

zobizob
Amateur de Prise2Tete
Enigmes résolues : 1
Messages : 8

L'céhiquier du diable

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 ?

  • |
  • Répondre

#0 Pub

 #2 - 13-11-2017 18:51:43

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

l'échiquier du diablz

Ca ressemble beaucoup à ça :http://www.prise2tete.fr/forum/viewtopic.php?id=13181

Vasimolo

 #3 - 13-11-2017 22:07:53

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

L'échiquie rdu diable

On numérote les cases entre 0 et 63 : étant donnée une disposition des pierres sur l'échiquier, on lui associe un nombre entre 0 et 63 en faisant la nim-addition des cases sur lesquelles il y a une pierre. Du fait des propriétés de la nim-addition sur un ensemble du type [latex][0;2^n-1][/latex], Alice peut laisser à Bob une disposition associée au nombre qu'elle veut entre 0 et 63.

Elle aurait même pu le faire si le diable lui avait imposé de modifier une case.

 #4 - 14-11-2017 10:03:21

Bastidol
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 152

L'échiquier du dibale

Bonjour Zobizob,

Lors de la mise en place de la stratégie Bob et Alice ont ils connaissance de l'état initial de l'échiquier ?

Cordialement.

 #5 - 14-11-2017 10:06:08

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

L'échiquier du diabl

Celui là, si on ne l'a pas vu déja au moins une fois sous une forme ou une autre, on peut difficilement le deviner.....

On attribue à chaque case un code à 6 chiffres binaires (2^6 = 64) et on pose cette règle: code actif si pierre, code 000000 si pas de pierre.


Avec une configuration donnée, on calcule un code-somme de 6 bits: chaque bit représente la parité du nombre de bits à 1 de même rang pour toutes les cases.

La case mystère est ce code-somme.

Pour le corriger, il suffit de changer une case (ôter ou ajouter une pierre) qui représente la différence binaire du code-somme lu et du code-somme de la case mystère.
Exemple :
code-somme lu :....... 001010
code case mystère.....000111
Différence : ..............001101

On ajoute ou on ôte une pierre à la case affectée au code 001101 (case 13) pour changer la parité des bits de rang 3, 4 et 6.

 #6 - 14-11-2017 10:21:37

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

L'échiqier du diable

XOR, j'adore big_smile

Bref. Les cases sont numérotées de 0 à 63 (en fait, on peut avoir autant de cases qu'on veut).
Alice rentre, calcule le XOR des cases qui ont une pierre dessus.
Un dernier XOR ajoute la valeur de la case mystère, et ça nous indique quelle case doit être modifiée.
Bob rentre, calcule le XOR des cases avec pierres, et donne le résultat.

Démonstration: les premiers XOR donnent une valeur A.
La case mystère est notée M, et A XOR M = C, la case à changer.
Du coup, une fois la case C changée, le résultat des XOR sur la grille donne A XOR C. Et magique, si A XOR M = C, alors A XOR C = M

 #7 - 15-11-2017 18:33:10

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 3446
Lieu: 94110

L'échiquierr du diable

On commence par se mettre d'accord pour numéroter les cases en octal. Les numéros de colonne de 0 à 7 représentent les unités, le lignes de 0 à 7 les « huitaines ».
Alice fait la somme de toutes les cases occupées par une pierre. Si cette somme modulo 64 (en décimal, soit 80 en octal) est égale au numéro de la case mystère, elle ne change rien.
Si elle est différente elle peut soit ajouter une pierre dans la case (si celle-ci est libre !) qui donnera un total modulo 64 égal au numéro de la case mystère, soit enlever une pierre dans une case (si celle-ci est remplie !) pour obtenir le même résultat.

Statistiquement, si les cases du diable sont choisies au hasard, je pense qu'Alice et Bob ont de bonnes chances de s'en tirer (je laisse aux matheux de service, le soin de calculer cette probabilité dans le cas général de N pierres wink ).
Mais si le diable veut vraiment être diabolique, il choisira une case mystère et un placement des pièces tels qu'aucune de ces deux conditions ne soit valide.

Un grand merci big_smile pour cette énigme qui m'est apparue au premier ras bord comme insoluble, mais qui m'a permis de bien titiller mes neurones.

 #8 - 15-11-2017 22:38:12

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

l'échiquier di diable

Bonsoir,
Voici une méthode.
Les cases de l'échiquier sont numérotées de 0 à 63, dans un ordre quelconque. On écrit en binaire, sur une colonne, les numéros des cases occupées.
En dessous, on écrit le numéro de la case mystère, puis le numéro de la case à modifier, qui est tel que chaque colonne contienne un nombre pair de bits à 1.

Code:

Exemple :
Cases 0 à 63, codées sur 6 bits

Cases occupées au début = [1, 4, 7, 16, 18, 61]
Cailloux                =   1 000001
Cailloux                =   4 000100
Cailloux                =   7 000111
Cailloux                =  16 010000
Cailloux                =  18 010010
Cailloux                =  61 111101
Case mystère donnée     =  10 001010

Case à modifier         =  55 110111

Pour trouver la case mystère à partir de la nouvelle disposition, on écrit sur une colonne les numéros des cases occupées, puis le numéro de la case cherchée, qui est tel que chaque colonne contienne un nombre pair de bits à 1.

Code:

Avec l'exemple précédent :
Cases occupées à la fin = [1, 4, 7, 16, 18, 55, 61]
Cailloux                =   1 000001
Cailloux                =   4 000100
Cailloux                =   7 000111
Cailloux                =  16 010000
Cailloux                =  18 010010
Cailloux                =  61 111101
Cailloux                =  55 110111

Case mystère calculée   =  10 001010

Si le numéro de la case à modifier est 0, on a le choix entre ajouter ou retirer une pierre, ou ne rien faire. On peut donc imposer à Alice de toujours modifier une case.

Voici un script en python3 qui calcule la case à modifier, et qui vérifie que la nouvelle disposition permet de retrouver la case mystère.

Code:

#!/usr/bin/env python3
import sys
from functools import reduce
k=0
k+=1;n=int(sys.argv[k])
k+=1;case_mystere=int(sys.argv[k])
N=1<<n

def vbin(s): return ("%3d %s"%(s,(bin(s)[2:]).zfill(n)))

k+=1;cailloux=set()
for case in sys.argv[k:]: cailloux.add(int(case))
cailloux=list(sorted(cailloux))

print('\nCases 0 à %d, codées sur %d bits'%(N-1,n))
print('\nCases occupées au début = %s'%cailloux)

parite=reduce(lambda x,y:x^y, cailloux, 0)
modifier=case_mystere ^ parite

print('Case mystère donnée     = %s'%(vbin(case_mystere)))
print('\nCase à modifier         = %s'%(vbin(modifier)))
if modifier in cailloux: cailloux.remove(modifier)
else:                    cailloux.append(modifier)

print('\nCases occupées à la fin = %s'%sorted(cailloux))

parite=reduce(lambda x,y:x^y, cailloux, 0)
print('Case mystère calculée   = %s'%(vbin(parite )))

Il faut lui indiquer en entrée :
- le nombre de bits permettant de coder les numéros des cases
- le numéro de la case mystère
- la liste des cases occupées

Code:

Exemple :
$ ./echiq0.py 6 10 1 7 4 61 18 16 

Cases 0 à 63, codées sur 6 bits

Cases occupées au début = [1, 4, 7, 16, 18, 61]
Case mystère donnée     =  10 001010

Case à modifier         =  55 110111

Cases occupées à la fin = [1, 4, 7, 16, 18, 55, 61]
Case mystère calculée   =  10 001010

 #9 - 16-11-2017 21:38:22

extasy300
Amateur de Prise2Tete
Enigmes résolues : 11
Messages : 1

L'échiqiuer du diable

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...)

 #10 - 17-11-2017 17:41:29

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

l'échisuier du diable

Bonjour, il suffit de associer tout les nombres binaires de 0 à 63 à chaque case et de faire un XOR bits par bits pour chaque case marquée.
Soit M le résultat de cette opération, et N le numéro de la case que doit trouver Bob.
Il suffit à Alice de changer d'état la case correspondant au nombre binaire tel que son n-ième bit vaut 1 si les n-ièmes bits de M et N sont différents, 0 sinon.

 #11 - 19-11-2017 12:55:04

Bastidol
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 152

L'échiquire du diable

Bonjour

Bravo à @zobizob pour cette super énigme. big_smile
A mon grand regret je n'ai pas su la résoudre.

Continuons à faire vivre ce site !!!

 #12 - 20-11-2017 13:19:44

zobizob
Amateur de Prise2Tete
Enigmes résolues : 1
Messages : 8

l'échiquier su diable

Bravo à Ebichu, nodgim, scarta, Jackv, enigmatus (super pour le code python! cependent je doute que le diable autorise Alice et Bob a venir avec un ordinateur wink), et caduk pour leurs solutions ! C'est effectivement ce qu'il fallait faire !

Vasimolo, merci je n'avait pas vu l'énigme présentée sous cette forme!

extasy300, je ne suis pas sûr de bien comprendre mais je pense qu'une stratégie au cas par cas est voué a l'echec, et même si c'est possible ce serait vraiment trop compliqué à démontrer, je t'encourage à regarder les solutions proposées par les autres!

Maintenant que l'on a fait la partie facile (le cas où le nombre de cases est une puissance de 2) passons au cas général, est-ce toujours possible ?

certains auront remarqué que le diable peut imposer à Alice de changer au moins une case (si l'on a déjà le bon codage, changer la case ayant pour code zéro ne change pas la somme binaire).

Qui peut montrer que si le diable impose à Alice de changer exactement une exactement case, alors il existe une solution marchant à tous les coups uniquement dans le cas où le nombre de case est une puissance de deux ?

 #13 - 20-11-2017 13:20:33

zobizob
Amateur de Prise2Tete
Enigmes résolues : 1
Messages : 8

L'chiquier du diable

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Mots clés des moteurs de recherche

Mot clé (occurences)

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
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete