Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 06-11-2013 21:29:58

tibo
Membre actif
Inscription : 23-01-2008
Messages : 946

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:
691760Croque.png
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 !

Hors ligne

#2 07-11-2013 15:04:49

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

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.


Memento Mori ! ...

Hors ligne

#3 07-11-2013 17:15:14

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Jeu du Croque

Re,

un lien pour essayer ses stratégies : le Croque


Memento Mori ! ...

Hors ligne

#4 07-11-2013 21:13:57

Fred
Administrateur
Inscription : 26-09-2005
Messages : 4 704

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.

Hors ligne

#5 07-11-2013 21:16:33

Fred
Administrateur
Inscription : 26-09-2005
Messages : 4 704

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.

Hors ligne

#6 19-11-2013 20:53:43

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.

Hors ligne

#7 20-11-2013 11:40:23

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 6 141

Re : Jeu du Croque

Salut,

bon, alors, la bonne solution ?


Memento Mori ! ...

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quelles sont les lettres manquantes? Etes-vous un humain ou un roxxx?

Pied de page des forums