Solitaire infini et fonction Pagode

[Juzo]

Bonjour,

Après un problème d'introduction, voici le sujet principal que je trouve très joli sur le jeu du solitaire et la fonction Pagode.
J'ai vu que ce sujet a été posé dans le forum il y a longtemps, donc je poserai un défi préliminaire, la question principale, puis je renverrai au fil ancien pour la solution.

On dispose maintenant d'un damier infini, une ligne droite que nous appellerons frontière sépare le damier en deux demi-plans.
Des pions sont disposés dans le premier demi-plan, l'autre demi-plan est vide.
Le but du jeu est d'utiliser les déplacements du jeu du solitaire, pour envoyer un pion du demi-plan occupé le plus loin possible de la frontière à l'intérieur du demi-plan vide.

Défi préliminaire :
En disposant 20 pions comme vous le souhaitez dans le demi-plan occupé, à combien de cases de la frontière pouvez-vous envoyer un pion à l'intérieur de l'autre demi-plan ?

Question principale :
Le demi-plan occupé contient une infinité de pions occupant toutes ses cases. A combien de cases de la frontière est-il possible d'envoyer un pion à l'intérieur de l'autre demi-plan ?


Je serais intéressé par vos réponses intuitives. Par ailleurs quelques essais permettent d'avoir une bonne idée des solutions.
-----

[MissJenny]

intuitivement je dirais qu'on ne peut pas aller très loin, parce que quand un pion saute par-dessus un autre pion, il gagne une case mais il crée un trou de deux cases. Ce trou ne peut être comblé qu'en créant d'autres trous, et finalement on crée plus de trous qu'on ne progresse jusqu'au moment où on ne peut plus combler les trous. Mais bon, c'est du pur pifomètre...

[Liet Kynes]

"20 pions comme vous le souhaitez dans le demi-plan occupé": intuitivement cela laisse présager un algorithme utilisable dans le plan infini -> un truc du genre la fourmi de Langton qui trace son autoroute

[Resartus]

Bonjour,
il me semblait avoir lu (mais il y a longtemps) que la démonstration que 5 est impossible était très difficile.
Si une fonction pagode pas trop compliquée permet cela sans ordinateur, c'est génial..

[A voir en vidéo sur Futura]

[Juzo]

Bonjour, des éléments de réponse en spoiler au cas où vous voulez continuer à chercher sans les regarder.

Intuitivement je dirais qu'on ne peut pas aller très loin, parce que quand un pion saute par-dessus un autre pion, il gagne une case mais il crée un trou de deux cases. Ce trou ne peut être comblé qu'en créant d'autres trous, et finalement on crée plus de trous qu'on ne progresse jusqu'au moment où on ne peut plus combler les trous. Mais bon, c'est du pur pifomètre...

L'intuition est bonne. Le nombre de cases maximum dont on peut s'éloigner de la frontière avec 20 pions est...

 Cliquez pour afficher

4

Il y a seulement 2 configurations qui permettent cela (sans compter leurs symétriques), et 20 est le nombre minimum de pions nécessaires pour s'éloigner de 4 cases.
Sur l'image la frontière est appelé "grande muraille".

Solutions pour s'éloigner de 4 cases.png

"20 pions comme vous le souhaitez dans le demi-plan occupé": intuitivement cela laisse présager un algorithme utilisable dans le plan infini -> un truc du genre la fourmi de Langton qui trace son autoroute

Merci pour cette source intéressante, par contre la solution que je propose n'est pas en lien avec un automate cellulaire.

Bonjour,
il me semblait avoir lu (mais il y a longtemps) que la démonstration que 5 est impossible était très difficile.
Si une fonction pagode pas trop compliquée permet cela sans ordinateur, c'est génial..

 Cliquez pour afficher

Effectivement la case 5ème case ne pourra jamais être atteinte même avec une infinité de pions, ce que je trouve étonnant quand on s'est intéressé au défi préliminaire...

Une fonction Pagode permet bien de démontrer ce résultat avec très peu de raisonnement.
Celle-ci n'est ni trop simple ni trop compliquée, je pense qu'il est possible de la trouver avec 2 indices dont voici le premier :

On attribue à la 5ème case (celle qui ne peut pas être atteinte), la valeur 1. Avec une fonction Pagode adaptée, on montrera ensuite qu'il est impossible qu'un pion termine sur cette case.

[Juzo]

J'ai peut-être un peu exagéré en disant qu'il est possible de trouver la fonction Pagode. En fait je n'en sait rien.

Je donne directement le 2ème indice : la fonction Pagode utilise le nombre d'or.
Comme il faut démontrer qu'il est impossible d'arriver sur la case de valeur 1, vous devriez pouvoir en déduire la somme de toutes les cases du demi-plan entièrement occupé par des pions. Sinon ça pourra faire l'objet d'un 3ème indice.

[Juzo]

Bonsoir,
j'ai mis du temps à revenir sur ce sujet désolé, voici donc la solution.

Le problème est de démontrer que sur un damier infini séparé en deux demi-plans dont l'un est a toutes ses cases occupées par des pions, il est impossible d'envoyer un pion à plus de 4 cases de l'autre côté de la frontière séparant les demi-plans, en utilisant les règles de déplacement du jeu du solitaire.
Pour 4 cases, on a vu que c'était possible avec 21 pions (2 solutions).

Pour cela on suppose qu'il est possible d'envoyer un pion à 5 cases de la frontière. La 5ème case que le pion est supposé atteindre se voit attribuer la valeur 1.

Les autres cases sont définies avec le nombre d'or selon le schéma ci-dessous :

Fonction Pagode solitaire.png

La ligne noire est la frontière, la partie inférieure est le demi-plan occupé par des pions au départ.

On utilise deux formules du nombre d'or :
(1) = 1
(2) (on sait que )


Situation initiale :

On multiplie la formule (2) par :

Si on multiplie par pour n supérieur ou égal à 2 :

D'où la valeur de la 1ère ligne :

De même on montre que la 2ème ligne vaut , la 3ème ligne vaut , etc.

D'après la formule (2), la somme de toutes les lignes du demi-plan sous la frontière vaut 1.

Dans la situation initiale la fonction Pagode vaut donc 1.

Situation finale :

Il y a un pion sur la case de valeur 1, de plus cette position est atteinte en un nombre fini de coups, donc il reste nécessairement d'autres pions sur le plateau qui en contenait une infinité.

Dans la situation finale, la fonction Pagode est donc supérieure à 1.

Conclusion : La fonction Pagode ne pouvant que baisser ou rester constante, il est impossible d'envoyer un pion à 5 cases de la frontière.

Qu'en pensez-vous ? Je trouve cette résolution très élégante.

Bonne soirée

Source : Pour la Science n°207 janvier 1995