Prisonniers, chapeaux, damiers, etc. Jouons!

[ffback]

Salut. Cette semaine je délaisse l'exo défi traditionnel (il reste toujours un défi retors d'Imod en cours^^) et ouvre à la place ce topic consacré à tous ces types de problèmes concernant des jeux et leurs stratégies gagnantes. Je pense surtout à ces jeux impliquant plusieurs personnes qui doivent collaborer avec une bonne stratégie afin de gagner/augmenter les chances de victoire, mais le topic se veut ouvert à tous types de jeux.

Un 1er exemple:
Deux personnes A et B participent au jeu. Elles connaissent les règles et peuvent établir une stratégie au début, mais ne peuvent plus communiquer une fois que le jeu commence. Le déroulement est le suivant: A entre dans une salle où se situe un échiquier 8x8 où sur chaque case est posée une pièce de 1 euro, soit sur pile soit sur face. On lui désigne une des cases de l'échiquier. Ensuite, il retourne n'importe quelle pièce, mais une seule, puis il sort. B entre alors, et son but et de trouver la case désignée.
Existe t-il une stratégie 100% gagnante?
Et avec un damier 10x10, ou plus généralement k x k? (ouvert)

[nodgim]

Vu comme tu le présentes, il suffit que A et B s'entendent pour retourner la pièce de la case 1A.

[ffback]

Ah, oups! Souvenir un peu vieux pour ma défense. Bon j'essaie de retrouver l'enoncé correct et je rectifie.

[Imod]

Si nous pensons au même problème , il me semble que le joueur A doit faire deviner au joueur B une pièce choisie par un troisième larron en retournant au maximum une des pièces

Imod

[Ben314]

Salut,
Dans le cas d'un échiquier (8x8), j'y arrive relativement facilement.
Mais dans le cas d'un damier, là, je suis assez sec, donc je conjecturerais éventuellement que c'est pas possible. . .

[ffback]

Je suis désolé pour cet énoncé tout écorché. Je suis allé me renseigner à la source et c'est effectivement l'énoncé d'Imod le bon, donc j'ai tout modifié en conséquence. Du coup je suis même pas sûr que j'ai moi même une solution, va falloir que je réfléchisse un peu

[Imod]

Quand le côté du carré est une puissance de 2 , on peut coder la grille et trouver la bonne pièce . Pour un carré 3X3 , il y a 9 choix possibles pour 9 cases à trouver ( la grille initiale n'est toujours pas connue ) .

Qu'est-ce qui achoppe ?

Imod

[ffback]

Pour un damier á K cases (K carré ou non. La forme du damier n'est pas importante dans ce probleme): je pense avoir montré que il y a une straegie gagnante ssi K est une puissance de 2. Par contre je suppose que le premier larron retourne obligatoirement une piece (et pas "au maximum une", qui complique les choses)

[Imod]

Quand je parlais de carré de côté puissance de 2 , je ne pensais qu'au nombre de cases mais plus je pense moins vite et moins mes explications sont claires

Il n'y a pas vraiment de difficulté supplémentaire à tolérer ou non le retournement d'une pièce car une d'entre elle joue le rôle de l'élément neutre dans la stratégie utilisée .

Pour les autres grilles , c'est bien plus intéressant

Imod

[ffback]

Modelisation: Notons l'ensemble des cases, de cardinal (on peut éventuellement identifier à ). Par une correspondance pile<->0, face<->1 et en numérotant les cases, on identifie chaque configuration de pièces sur les cases par un élèment . Notons aussi () l'élément de ayant un 1 sur la i-eme coordonnée et un 0 sur les autres. Alors retourner une pièce revient à faire une opération dans .

Durant le jeu:
-A arrive et voit une configuration . On lui désigne une case . A choisit alors et effectue la transformation
-B arrive et voit la configuration . A partir de cette info il annonce une case. Autrement dit, il annonce où est une fonction connue de B. Le but est que

Trouver une stratégie gagnante revient à trouver une bonne fonction , le but étant que pour toute configuration et pour n'importe quelle case désignée , A puisse trouver une configuration telle que . Autrement dit, on veut que pour tout , la fonction qui a associe soit surjective (donc bijective puisque l'ensemble de départ et d'arriver sont de même cardinal )

Solution au prochain post, dans la soirée.

[ffback]

Sens direct: on suppose que est une puissance de 2, disons .

L'espace est un -espace vectoriel de dimension , de base . De plus, étant de cardinal , on peut aussi munir d'une structure de -espace vectoriel (par exemple en mettant en bijection avec ), et on définit alors comme une application linéaire. On définit d'abord de maniere bijective, et ayant même cardinal, puis on étend de la base à tout l'espace par linéarité. L'application vérifie alors la propriété requise: pour tout dans , l'application est injective par construction de , donc bijective par cardinalité. Elle permet donc de définir une stratégie gagnante.

[ffback]

Sens réciproque: on suppose avoir une stratégie gagnante pour un damier à cases, et on veut montrer que est une puissance de 2.

On a donc une fonction tel que pour tout , l'application est une bijection de dans . Je dis qu'alors nécessairement, toutes les valeurs de sont prises autant de fois par . Pour le prouver, j'utilise un argument probabiliste car je suis plus à l'aise, mais en théorie ça s'adapte à un argument combinatoire. Je considére la variable aléatoire où est choisi au hasard uniformément dans , et est choisi au hasard uniformément dans de maniere indépendante. Alors
-Pour fixé, a une loi uniforme sur , donc aussi est uniforme sur .
-Pour fixé, a une loi uniforme sur (grâce à la propriété de ), donc aussi est uniforme sur .
Ces deux conclusions ensemble montrent qu'effectivement, prend autant de fois chaque valeur de . Mais alors, en notant ce nombre, on a , donc est une puissance de 2.

[Ben314]

Effectivement, c'est très joli.
J'avais trouvé facilement le sens direct (avec la même méthode), mais j'avais pas pensé à compter les orbites du bidules pour la réciproque.