Un jeu, des pièces et une table

titoufred · August 2011

Voici un problème que l'on m'a soumis récemment :

"C'est un jeu qui se joue à 2 joueurs avec des pièces de 1€ sur une table rectangulaire.
La règle du jeu est extrêmement simple : chacun des 2 joueurs doit poser à tour de rôle une pièce à plat sur la table (la pièce ne doit pas chevaucher une pièce posée préalablement). Le premier des 2 joueurs qui ne peut plus poser de pièce sur la table (sans la faire tomber) a perdu.
Sauriez-vous trouver une stratégie permettant de gagner à tous les coups pour l'un des 2 joueurs ?"Pour ceux qui veulent chercher la solution, ne lisez pas la suite...
J'ai donc cherché puis trouvé une stratégie gagnante pour le premier joueur, qui consiste à jouer au centre de la table puis à jouer de façon symétrique à l'autre joueur. Je me suis alors dit que cette stratégie devait également fonctionner pour n'importe quelle pièce ayant un centre de symétrie et pour n'importe quelle table ayant un centre de symétrie [edit: sur lequel on peut poser une pièce]. La démonstration est assez facile pour une pièce convexe. Cependant, dans le cas d'une pièce quelconque (pas nécessairement convexe), je n'arrive pas à trouver de démonstration ou de contre-exemple.

Est-ce que quelqu'un aurait une idée ?

Domi · August 2011

Bonjour Titoufred

Un "contre-exemple" simple , tu considères une table constituée de deux disques tangents de rayon R et des pièces de rayon R , le deuxième joueur gagne de façon évidente .

Pour le cas général , bon courage !!!

Domi

christophe c · August 2011

Peut-on trouver une stratégie permettant de gagner à tous les coups pour l'un des 2 joueurs ?"

Attention: il y a un théorème qui dit que la réponse est oui (pour tous les jeux qui se terminent en temps fini à information parfaite, pas seulement celui-là) donc je suppose que ton "peut-on trouver" renvoie plutôt à une demande de stratégie "simple à décrire"

Matsaya · August 2011

Heu, saur erreur le morpion (ou XO, ou tic-tac-toe, bref le jeu ou le premier à aligner 3 croix (ou rond) sur une grille de 3x3 gagne) se termine en temps fini et est à information parfaite. Pourtant il n'existe pas de stratégie permettant de gagner à tous les coups pour l'un des 2 joueurs (on a match nul).

christophe c · August 2011

je parlais des jeux où la règle du jeu désigne toujours un gagant à la fin. Par exemple au tic tac toe, tu peux décréter que s'il n'y a pas d'alignement à la fin alors, le second à jouer est le gagnant.

De même aux échecs, tu peux décréter que si au bout de 10000 coups personne n'a fait mat alors les noirs ont gagné.

Matsaya · August 2011

Ok, voilà qui clarifie tout. Merci.

youplaboum · August 2011

domi,

je ne suis pas d'accord : le premier joueur gagne également dans ton cas si on suit la méthode de titoufred:
le second joueur pourra mettre une pièce (d'un côté ou de l'autre de la première pièce) et le donc premier joueur tout autant (du côté opposé)..du coup le second joueur perd
on fait l'hypothèse que les 2 pièces des côtés auront un diamètre sur la tranche de la table et seront donc en équilibre.

titoufred,
je n'ai aucun courage pour chercher de solutions pour tes tables quelconques !

ccnc · August 2011

tu n'as pas mis de smiley pour dire que tu plaisantais, du coup on se demande si tu crois à ton truc?

domi parlait éventuellement d'un rayon R-epsilon pour les pièces

titoufred · August 2011

Domi écrivait:

> Bonjour Titoufred
>
> Un "contre-exemple" simple , tu considères une
> table constituée de deux disques tangents de rayon
> R et des pièces de rayon R , le deuxième joueur
> gagne de façon évidente .
>
> Pour le cas général , bon courage !!!
>
> Domi

Je ne suis pas d'accord avec toi Domi. Si le premier joueur joue au point de tangence, il gagne.

Bu · August 2011

Si la table est un anneau de rayon intérieur R et si les pièces ont un rayon < R, alors c'est le deuxième joueur qui a une stratégie gagnante. (:D

titoufred · August 2011

christophe chalons écrivait:

> Attention: il y a un théorème qui dit que la
> réponse est oui (pour tous les jeux qui se
> terminent en temps fini à information parfaite,
> pas seulement celui-là) donc je suppose que ton
> "peut-on trouver" renvoie plutôt à une demande de
> stratégie "simple à décrire"

Oui, tu as raison : j'ai légèrement modifié l'énoncé en remplaçant "Peut-on trouver" par "Sauriez-vous trouver".
Un théorème, c'est un bien grand mot pour un résultat presque évident.
Pour les jeux où il peut y avoir nulle (comme les échecs), il existe forcément une stratégie non perdante pour l'un des 2 joueurs.

titoufred · August 2011

Bu écrivait:

> Si la table est un anneau de rayon intérieur R et
> si les pièces ont un rayon < R, alors c'est le
> deuxième joueur qui a une stratégie gagnante. (:D

Oui, tu as raison, pour un anneau tel que tu le décris, le premier joueur ne peut pas jouer au centre et donc c'est le deuxième qui va adopter la stratégie de jouer symétrique pour gagner. Je dois donc compléter l'énoncé en "une table ayant un centre de symétrie où il est possible de placer une pièce".

Bu · August 2011

Il faut aussi compléter l'énoncé en précisant que les pièces sont connexes. (:D(:D

titoufred · August 2011

Oui, les pièces sont connexes, c'est clair.
On peut les considérer simplement connexes, car on ne pourra jamais jouer dans un trou de pièce.
Donc le centre de symétrie d'une pièce fait partie de cette pièce.
Ca peut peut-être servir pour la démo...

Bu · August 2011

Le problème est donc, il me semble :
Soit $F$ un compact connexe du plan, ayant un centre de symétrie $C$. Soit $d$ un déplacement. S'il existe deux points $M$ et $N$ de $F$ tels que $d(M)$ et $d(N)$ sont symétriques par rapport à $C$, alors $F\cap d(F)\neq \emptyset$.