Forum de mathématiques - Bibm@th.net

tibo

Membre expert

Inscription : 23-01-2008

Messages : 1 097

Jeu du Croque

Voila une énigme à la fois ludique et gourmande:

Le Croque est un jeu à deux joueurs qui se joue sur une tablette de chocolat.
Le premier joueur choisi un carré et mange tous les carrés situés au dessus et à droite.
Le second joueur choisit ensuite un des carrés qui n'a pas été mangés et mange tous les carrés situés au dessus et à droite.
Puis c'est au tour du premier joueur de choisir un carré.
Le jeu continue jusqu'à ce que l'un des joueurs mange le carré tout en bas à gauche, lequel est empoisonné et ce joueur perd la partie.

Une image valant mieux qu'une longue explication:

Supposons que les case X, Y et Z soit choisies dans cet ordre, j'ai colorié en rouge, jaune puis en vert toute les cases qui sont retirées.
La case P est la case à ne pas prendre.

Le but final du problème est de trouver une stratégie gagnante pour l'un des deux joueurs quelque soit la taille de la tablette.

Une tablette de taille 1xn ne présente pas beaucoup d’intérêt.
1) Trouver une stratégie gagnante pour une tablette de taille 2xn.
2) Et pour une tablette de taille 2x infini ? (Oulala! Une infinité de carrés de chocolat...)
3) Existe-t-il une stratégie gagnante si la tablette est carrée?

Et la question finale:
Existe-t-il une stratégie gagnante pour l'un des deux joueurs s'ils jouent avec une tablette de chocolat de taille quelconque (mais finie)?

Régalez-vous !!!

---

A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Jeu du Croque

Salut,

ça me rappelle un bon souvenir avec un très bon copain aujourd'hui disparu.

▼ solution ?

Si je me souviens bien, gagne celui qui peut laisser à l'autre un carré de carrés de chocolat.
Donc si la tablette de chocolat est carrée, il faut jouer en second pour gagner.

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Jeu du Croque

Re,

un lien pour essayer ses stratégies : le Croque

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 231

Re : Jeu du Croque

Salut,

  J'espère ne pas me tromper sinon je vais encore attirer les foudres de Nerosson!

▼Le cas des tablettes 2,n

Je crois que le premier qui joue gagne à tous les coups. Voici une esquisse de preuve, par récurrence, mais par récurrence un peu compliquée.

L'hypothèse est la suivante :
"Le premier qui joue avec une tablette comportant deux lignes de n carrés a une stratégie gagnante.
Le second qui joue avec une tablette dont la première ligne comporte n-1 carrés et la seconde comporte n carrés a une stratégie gagnante".

On voit bien que ceci fonctionne lorsque n=2. Supposons que c'est vrai jusque n-1, et prouvons l'hypothèse au rang n. On regarde d'abord le cas d'une tablette comportant deux lignes de n carrés. Alors le premier joueur croque le carré en haut à droite (donc un seul carré). Si le second joueur croque un carré de la seconde ligne, alors on se ramène au cas d'une tablette de 2 lignes de k carrés, avec k<n. Donc le premier joueur va gagner.
Le second joueur doit donc croquer un carré de la première ligne (et donc tous les carrés à sa droite). Le premier joueur croque alors le carré situé en dessous juste à droite (et donc tous  les carrés à sa droite). Le joueur 2 se retrouve alors dans une situation perdante.

Considérons maintenant une tablette avec une ligne de n-1 carrés et une deuxième ligne (dessous) de n carrés, et prouvons que le joueur 1 est en situation perdante. S'il croque un carré de la première ligne, le joueur 2 croque le carré en dessous juste à droite, et le joueur 1 est en situation perdante. Si le joueur 1 croque un carré de la seconde ligne, on se retrouve avec une tablette de 2 lignes de k carrés, et on sait que c'est une solution favorable pour le joueur 2.

Bien sûr, on peut tirer de ce raisonnement une stratégie effective pour le joueur 1 : toujours croquer le carré en haut à droite si la tablette est rectangulaire, sinon croquer le carré de la deuxième ligne de sorte que la deuxième ligne comporte un carré de plus que la première.

Il reste encore tous les autres cas à traiter!

Fred.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 231

Re : Jeu du Croque

▼Un complément

  Pour une tablette 2,infini, le joueur 1 est clairement en situation perdante d'après le raisonnement fait dans mon précédent post.

Dillon

Membre

Lieu : Angers

Inscription : 27-02-2011

Messages : 72

Re : Jeu du Croque

Bonjour la compagnie

Ça faisait un bon bout de temps…
Je pense avoir la réponse pour une tablette carrée

▼Texte caché

Si on appelle (1,1) le carré en bas à gauche, celui qu'il ne faut pas prendre, alors le premier joueur prend (2,2). Il reste une configuration en L à branches égales et son adversaire ne peut que réduire l'une des deux branches du L sans toucher à l'autre. Le premier joueur peut alors prendre le même nombre de morceaux dans l'autre branche. L'égalité des branches du L va être rétablie.
Le second joueur est obligé de rompre à nouveau cette égalité.
Jusqu'à ce qu'il ne reste que le dernier carreau. C'est une configuration où les deux branches sont égales, c'est donc le premier joueur qui la présente eu second.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Jeu du Croque

Salut,

bon, alors, la bonne solution ?

---

De la considération des obstacles vient l’échec, des moyens, la réussite.