Forum de mathématiques - Bibm@th.net

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 353

Empilement de jetons

Bonjour,

  On considère un damier 5x5. Sur chaque case de ce damier on a disposé un jeton. On peut déplacer le contenu d'une case sur une case adjacente à condition de disposer une pile de jetons sur une pile de taille supérieure ou égale.
  Quel est le nombre minimum de piles que vous pouvez espérer obtenir à la fin ?

F.

(d'après le magazine Tangente)

Glozi

Invité

Re : Empilement de jetons

Bonjour,
Merci pour l'énigme !

▼je trouve...

Il n'est pas trop dur d'arriver à faire 3 piles à la fin (par exemple une pile de 16, une pile de 8 et une pile de 1 (est-ce que cela a un rapport avec le développement en base 2 de 25 ?)
En raisonnant en sens inverse (au lieu de fusionner les piles on fait le jeu en sens inverse et on cherche a diviser des grosses piles en plus petites), on peut montrer qu'a un emplacement du damier avec $n$ cases voisines on ne peut pas mettre une pile plus grande que $2^n$. Ainsi la taille maximum d'une pile est de 16. Idée de démonstration : si on suppose qu'à la fin on a une pile de 17, alors cette pile provient de la fusion de deux piles (disons une de 9 et une de 8) celle de 9 provient de la fusion de deux piles (disons une de 5 et une de 4). Celle de 5 provient de la fusion de deux piles (une de 3 et une de 2). Celle de 3 provient de la fusion d'une pile de 2 et d'une pile de 1. Ainsi on se trouve avec une pile de 2 avec aucune case voisine disponible ce qui est absurde...

Ceci montre qu'on a au moins deux piles à la fin.

Je n'ai pas de preuve très rigoureuse qu'il n'est pas possible de faire deux piles exactement, j'ai écrit un petit code qui me montre que ce n'est pas possible (sauf erreur). Du coup, je dirais que le nombre minimum de piles qu'on peut obtenir est de trois.

Bonne journée

Ernst

Membre

Inscription : 30-01-2024

Messages : 356

Re : Empilement de jetons

Bonjour,

Intéressant.

▼réponse

J'ai programmé le truc et je suis arrivé à 3.

- progression ascendante avec choix du meilleur mouvement à partir d'une case au hasard par une méthode de Monte-Carlo, à savoir on fait des milliers de 'parties' aléatoires jusqu'au blocage et on choisit le mouvement qui a permis le meilleur score, ici le nombre minimum de piles (pour voir si on pouvait faire mieux, j'ai ajouté une distance Manhattan entre les piles restantes, cela n'a rien changé)

Pour écarter une erreur algorithmique j'ai essayé sur un damier 4 fois 4 et le programme arrivait instantanément à une pile.

Et je découvre ce matin la réponse de Glozi, ce qui renforce ma conviction. C'est la magie des casse-têtes.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Empilement de jetons

Bonjour,

▼voici

Si on avait deux tas au final:
- on peut voir qu.'avec un minimum obligé de 9 chacun, aucun n'est sur le pourtour, donc est sur le damier central 3x3.
- ces deux tas n'ont pas de case adjacente commune,
Sinon une case ne pouvant se vider que sur une case,
l'un des tas n'ayant que 3 cases voisines utiles, celui-ci n'aurait que 8 jetons max.
- on examine alors les dispositions relatives de ces deux tas ( à symétries près).
On s'aperçoit que l'un en aura 16 et l'autre 9, que les cases devenues vides devant se retrouver dans un des deux, avec au plus 4 déplacements ( forcément au cours de vidages successifs, certaines avec 4 exactement), on aboutit à chaque disposition d'essai une impossibilité numérique.
- on réalise 3 tas sans grosse difficulté par ailleurs.

3 est donc le min réalisable .

Bon 9 de Pâques.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 481

Re : Empilement de jetons

Bonjour,
Je ne comprends pas grand chose à l'argument de bridgslam pour l'impossibilité de deux tas.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Empilement de jetons

Bonjour,

▼Boileau?

Une case donnée évolue à partir de 1 jeton initial au plus  1 fois avec  chacune des cases qui lui sont voisines, à savoir au plus double à partir de 1 :
- 2 fois en coin
- 3 fois en pleine bande
- 4 fois ailleurs.
( au plus 1 fois, car en se vidant, ne pourra plus resservir).
Donc un angle obtiendra au maximum 4 jetons, un bord au plus 8, et une case du sous-damier central 3x3 au plus 16.

Déjà obtenir un seul tas (de 25) est donc impossible.
En tâtonnant on peut arriver à en obtenir 3.

Reste la question de 2 tas. Si on montre que c'est irréalisable, on aura prouvé que le minimum de piles est 3.
Supposons qu'on arrive à modifier le plateau en  deux cases dont le total est 25.
Si l'une en a moins de 9, l'autre en aurait 17, contradictoire. Donc toutes deux ayant au moins 9 jetons, elles sont sur le damier 3x3 central.
En fait leur emplacement possible est assez réduit ( à symétries près de leur positions relatives), comme on va le voir, et les options restantes seront même impossibles.
Déjà ces deux piles ( non voisines sinon on aurait aboutit à une seule...) ne peuvent avoir une case voisine commune, car cette case-là n'ayant pu  se vider que dans une seule des deux, l'une des piles aurait au plus 8 jetons, contradiction.
Il reste peu de dispositions relatives potentiellement valable ( la case centrale par exemple est vide),
il reste soit deux cases diagonalement occupées, soit deux cases espacées d'un saut de cavalier ( du jeu échecs).
On examine chacun de ces cas séparément.
Dans la première configuration, comme un jeton de coin du damier 5x5 a fini sa vie sur un des piles en 4 déplacements, donc en contribuant à une pile de 16, l'autre pile en a donc 9. Mais un autre jeton de  coin symétrique  a fini aussi son périple de même longueur, forcément sur l'autre pile*. On aurait deux piles de 16, impossible .
L'autre cas ( distance de cavalier) s'avère aussi impossible avec des arguments voisins ( considérer où les jetons des cases vidées ont pu atterrir en fonction de leur trajet obligé).
Le cas de deux piles finales est donc impossible.

(*) remarque: le déplacement au cours du jeu d'un jeton donné étant solidaire du vidage de la case où il est au cours de son mouvement, sa case d'arrivée comporte au moins deux fois le nombre de jetons de l'avant-dernière case, etc à rebours, donc n'importe quel jeton ne peut se déplacer plus de 4 fois en tout. Ainsi dans le cas de la disposition des deux tas en diagonale sur le mini-damier 3x3, les trajets de jeton de coins éloignés de 4 d'une pile sur le damier 5x5 ne pourraient se rejoindre à moment donné sur une case intermédiaire ( s'amalgamant en un seul tas) avant de poursuivre conjointement ensuite qu'en rallongeant encore leur parcours pour l'un d'eux,  impossible. L'un
des deux jetons devient donc alors surnuméraire par rapport au tas de destination de l'autre, déjà au max...
Cette remarque simple simplifie les raisonnements ultérieurs.

Bonne journée

Dernière modification par bridgslam (06-04-2026 08:55:42)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 481

Re : Empilement de jetons

Là, je comprends. Bien joué !

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Empilement de jetons

On peut s'intéresser à rechercher une expression ( si elle existe)  pour  le min( Nb(piles)) , leur(s) distribution(s) possible(s)    dans le cas d'un damier mxn général,
voire regarder en 3D pour des parallélépipèdes.
On distinguera je pense les cases de coins, d'arêtes, de faces, d'intérieur...
Par exemple on obtiendrait quoi avec un 5x5x5 ?

Merci Fred pour ce sujet très ludique.

Albertdu64

Membre

Inscription : 21-05-2026

Messages : 4

Re : Empilement de jetons

hello, à première vue, on pourrait penser qu'on peut tout fusionner en une seule pile, mais la contrainte "on ne pose que sur une pile de taille supérieure ou égale" bloque rapidement certaines configurations.
Ça ressemble à un invariant ou à un argument de coloration du damier. J'aurais tendance à chercher une borne inférieure en attribuant un poids aux cases (ou via un coloriage noir/blanc), puis à construire une stratégie qui atteint cette borne.