Voici un jeu auquel on m'a proposé de jouer cet été. Il se joue avec des pièces de monnaie (admettons 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.
Peut-on trouver une stratégie permettant de gagner à tous les coups pour l'un des 2 joueurs ?
Oulà, heu...
Ce n'est pas précisé, mais j'imagine que l'on ne peut pas pousser les pièces.
Pour donner une piste de réflexion : ce problème marche t-il avec une table ronde ?
C'est une variante de l'oeuf de colomb ? Une stratégie gagnante consiste pour le premier joueur à jouer au milieu de la table, puis exactement à la symétrie de son adversaire (si la forme de la table le permet).
Effectivement, il me semble que ça marche. Flute, maintenant je l'ai lu. 
Bien vu Benj2, cette stratégie est gagnante pour le premier joueur.
En poussant un peu la question posée par Simboubou :
Sur quels types de tables et avec quels types de pièces cette stratégie est-elle valable ?
Celles qui ont un centre de symétrie.
Oui, table et pièces avec centre de symétries, je pense que ce sont des conditions suffisantes.
Avec des pièces convexes, la démonstration est assez simple.
Avec des pièces non convexes, j'arrive pas à le formaliser, mais ça doit être bon quand même non ?
Je ne pense pas qu'avec des pièces concaves, ça puisse fonctionner, car du coup, une pièce pourrait occuper plus de 180° autour du centre, rendant la symétrie impossible.
La non convexité d'une pièce pourrait lui faire occuper deux points symétriques par rapport au centre de la table, sans que la pièce elle même n'occupe le centre, ça c'est sûr. Mais, il ne faut pas oublier que le premier coup consiste à placer une pièce au centre. Du coup, je ne vois pas comment c'est possible d'arriver à le faire lors du deuxième coup. Avec une pièce du genre un x ou un >-<, je ne vois pas comment on peut y arriver, mais je ne trouve pas vraiment d'argument...
Tu as un exemple ?
Si les pièces, sont en forme de demi arc, et que la deuxième pièce posée est "encastrée" dans la pièce centrale, on est pas bloqué ?
Ben imaginons un disque placé au centre en première pièce, puis un 3/4 de couronne en deuxième pièce, dont le rayon extérieur soit supérieur à celui du disque initial, dans ce cas, tu es bloqué.
Ah ok avec des pièces différentes. Et avec des pièces identiques ?
Quand on dit que l'on place la pièce au centre de la table, il faut aussi définir le centre de la pièce...
Si elle est concave, on prend quoi ? Le centre de gravité ? Le centre du cercle circonscrit ?
Simboubou dit:Quand on dit que l'on place la pièce au centre de la table, il faut aussi définir le centre de la pièce...
Si elle est concave, on prend quoi ? Le centre de gravité ? Le centre du cercle circonscrit ?
Mouais, dans ce cas, je dirai alors que l'on prend des pièces concaves avec centre de symétrie.
Et là, il est probable que la technique proposée fonctionne
Oui je parlais de pièces non convexes qui ont un centre de symétrie. Je suis à peu près sûr que la stratégie marche toujours, mais je n'arrive pas à expliquer pourquoi.
D'abord le problème peut se ramener au cas des pièces sans trous à l'intérieur car toutes les pièces étant identiques il est impossible de placer une pièce dans un trou sans faire de chevauchement. (On remarque ici que l'on pourra ensuite placer des trous ou on veut dans la pièce sans changer le résultat et donc étendre le résultat à des pièces non symétriques à cause de trous.)
Le seul problème pour le joueur 1 est le cas ou la table ne peut plus être rendue symétrique par son coup. (D'ailleurs si la pièce n'a pas une symétrie joueur 1 est bien embêté pour la placer de manière symétrique au centre).
La seule chance de joueur 2 c'est de placer une pièces dont le symétrique par le centre de la table possède un recouvrement non nul avec elle même (sinon joueur 1 peut rendre à nouveau la figure symétrique vu que tout l'emplacement du symétrique est libre et le centre de gravité inclus sur la table par symétrie de la table).
On note S() la symétrie centrale de centre le centre de la table (noté O)
En notant P la pièce que vient de jouer j2, il existerait un point A tel que
A \in P
S(A) \in P
Soit O' le centre de symétrie de P. La pièce étant sans trou :
[O' A] \in P
[O' S(A)] \in P
[S(O') S(A)] \in S(P)
[S(O') A] \in S(P)
O' A S(O') S(A') est un parallélogramme de centre le centre de de symétrie de la table O' dont les cotés sont inclus dans P union S(P).
Comme il est de centre O il soit aussi contenir une pièce de même forme de P. Notons dmax la distance d'un point le plus éloigné de O contenu dans la pièce au centre de la table. Remarquons qu'un plus grand segment inclus dans cette pièce est donc de taille 2*dmax (symétrie de la pièce et pas de trou).
Or
[O' A] <= dmax (car dans P et O' centre de P)
[O' S(A)] <= dmax (idem)
[S(O') S(A)] <= dmax (car dans P' et S(O') centre de S(P) identique à P)
[S(O') A] <= dmax (idem)
Donc O'AS(O')S(A') est un parallélogramme qui a tous ses cotés <= dmax mais qui doit contenir un segment de taille 2*dmax. Donc il est plat.
Donc soit O' soit A est confondu avec O, mais c'est impossible car O est déjà recouvert par la pièce centrale.
Donc joueur 2 ne peut pas empêcher joueur 1 de reconstruire la symétrie
CQFD (si je me suis pas gouré).
On peu gratter un peu avec les pièces trouées (comme remarqué au début) et en autorisant des changements de pièces tant qu'il est impossible de placer 50% de la pièce centrale dans l'enveloppe convexe de la pièce à jouer.
Jeremie dit:
En notant P la pièce que vient de jouer j2, il existerait un point A tel que
A \in P
S(A) \in P
Soit O' le centre de symétrie de P. La pièce étant sans trou :
[O' A] \in P
Pourquoi [O'A] inclus dans P ? La pièce n'est pas convexe non ?
Heu oui j'aurais du me relire au moment ou j'écrivais cela j'avais un X en tête alors qu'avec un H cela ne colle pas...
Mais en fait je ne me sert pas de l'inclusion complète dans la suite.
O' A S(O') S(A') est un parallélogramme dont les sommets sont inclus dans P union S(P) (et non l'intégralité des cotés).
Les inégalités restent vraies et le parallélogramme doit toujours contenir la pièce centrale et donc contenir un segment de taille 2*dmax (à cause de la symétrie). Par contre l'intégralité de ce segment n'est pas forcément inclus dans la pièce.
Jeremie dit:
O' A S(O') S(A') est un parallélogramme de centre le centre de de symétrie de la table O dont les sommets sont inclus dans P union S(P).
Comme il est de centre O il soit aussi contenir une pièce de même forme de P.
(j'ai corrigé)
Je ne comprends pas pourquoi ce parallélogramme doit contenir la pièce posée par le premier joueur.
Parceque S() est une symétrie de centre O (le centre de la table)
Edit pour préciser : [A S(A)] est une diagonale de ce parallélogramme de centre O. Or la première pièce est posée au centre de la table.
Edit 2 : bordel en fait ca colle pas. L'inclusion de la pièce centrale doit juste être dans un contour fermé symétrique inclus dans P union S(P).
On peut quand même choisir A de manière à minimiser l'aire de ce contour (la pièce est compacte).
Bon il manque un argument alors. Pas trop le temps de le chercher ce soir mais je suis presque sur qu'il est lié au fait l'on ne doit pas pouvoir emboiter deux pièces identiques symétriques avec leurs enveloppes convexes incluant plus de 50% l'aire de l'autre pièce.
Bon au moins la démo avec le parallélogramme marche déjà pour les pièces symétriques dont la topologie est en étoile.