énigme solitaire

**matthias** · 15/03/2006, 22h00

Vous connaissez tous le jeu du solitaire (pas celui avec les cartes, celui-là).
On garde les mêmes règles mais on prend comme plateau le plan entier (disons ZxZ) et comme situation initiale toute situation telle qu'un demi-plan (disons y > 0) soit vide. Dans l'autre demi-plan (y <=0) on dispose d'autant de pions que l'on veut (même une infinité, le choix est libre, le placement des pions aussi, on peut remplir le demi-plan si on veut).
La question est : jusqu'où peut-on amener un pion (ordonnée maximale atteignable, si elle existe) ?

Illustration d'une situation initiale :

**homotopie** · 16/03/2006, 09h45

Salut,
au bout d'un nombre dénombrable de coups (c'est long surtout vers la fin) le plan est rempli.

martini_bird · 16/03/2006, 09h57

Salut,

au premier ordinal transfini $\omega$ ?

Tu fais comment?

ambrosio · 16/03/2006, 10h21

Citation:

Posté par homotopie

Salut,
au bout d'un nombre dénombrable de coups (c'est long surtout vers la fin) le plan est rempli.

donc c'est encore plus fort que l'hôtel infini de Hilbert?
puisqu'au solitaire à chaque fois qu'on saute on enlève un pion. Donc si je te suis bien, on part d'un demi-plan rempli, on enlève une infinité de pions et on finit avec tout le plan rempli... pas mal.

**matthias** · 16/03/2006, 10h54

Avant d'essayer de remplir le plan, il faudrait déjà pouvoir amener un pion aussi loin que l'on veut. Or contrairement à ce que pourrait suggérer l'intuition, ce n'est pas évident. Pas évident du tout même

ambrosio · 16/03/2006, 11h28

Citation:

Posté par matthias

Avant d'essayer de remplir le plan, il faudrait déjà pouvoir amener un pion aussi loin que l'on veut

intuitivement, pour amener un pion aussi loin qu'on veut, il faut faire progresser une sorte de triangle et si ce triangle n'a pas de trous, ce qui reste à prouver, il va bien "finir" par remplir le plan.

**matthias** · 16/03/2006, 11h45

Vous êtes bien ambitieux.
Je vous propose de commencer de manière plus modeste. Auriez-vous une solution explicite pour pouvoir amener un pion en y=1, 2, 3, 4, 5 ?
Vous allez voir que ça se complique vite.

Evil.Saien · 16/03/2006, 15h55

Salut,

Intuitivement, je dirais 5 cases maximum.

**matthias** · 16/03/2006, 16h02

Citation:

Posté par Evil.Saien

Intuitivement, je dirais 5 cases maximum.

Ton intuition vient-elle d'essais que tu as faits, de ma proposition de tester pour y allant de 1 à 5, ou juste comme ça ?
En tout cas ce n'est pas ça, mais ce n'est vraiment pas loin

yat · 16/03/2006, 16h11

Citation:

Posté par matthias

Ton intuition vient-elle d'essais que tu as faits, de ma proposition de tester pour y allant de 1 à 5, ou juste comme ça ?
En tout cas ce n'est pas ça, mais ce n'est vraiment pas loin

On peut aller plus loin que 5 ?
Moi je n'arrive pas à dépasser le 4

...

J'espère qu'il y aura une petite démo à la clé

**matthias** · 16/03/2006, 16h19

Citation:

Posté par yat

On peut aller plus loin que 5 ?

Non.

Citation:

Posté par yat

Moi je n'arrive pas à dépasser le 4

...

Normal, ce n'est pas possible

Le max est bien 4.

Citation:

Posté par yat

J'espère qu'il y aura une petite démo à la clé

Oui, n'aies pas peur. Il y a une très jolie démonstration de ce résultat.

yat · 16/03/2006, 16h58

Citation:

Posté par matthias

Normal, ce n'est pas possible

Le max est bien 4.

Ah... je pensais qu'Evil.Saien supposait que le max était 5 parce que c'était le maximum qu'il arrivait à atteindre...

Citation:

Posté par matthias

Oui, n'aies pas peur. Il y a une très jolie démonstration de ce résultat.

Alors la....

J'ai pas l'ombre d'un début de raisonnement qui pourrait démontrer un truc pareil. Je suis curieux de voir la solution

martini_bird · 16/03/2006, 16h59

Salut,

m'est avis qu'il y un invariant bien choisi derrière tout ça, mais lequel?

Mais bon, je fais peut-être fausse route...

Cordialement.

**homotopie** · 16/03/2006, 17h10

Il n'y a pas de génération spontanée de pions?

J'oubliais que le pion qui vient de sauter laissait un vide à son ancienne place.

D'où guère de difficultés pour "remplir" le plan.

martini_bird · 16/03/2006, 17h14

Citation:

Posté par homotopie

J'oubliais que le pion qui vient de sauter laissait un vide à son ancienne place.

Si ça peut te rassurer, j'ai commis la même erreur au début : ah quand on ne lit pas les énoncés...

ambrosio · 16/03/2006, 17h37

Citation:

Posté par martini_bird

m'est avis qu'il y un invariant bien choisi derrière tout ça, mais lequel?

il suffit de trouver une équation algébrique de degré la position extrême du pion et qui doit être résolue "par radicaux", mais je ne vois pas

Evil.Saien · 16/03/2006, 17h51

Citation:

Posté par Evil.Saien

Salut,

Intuitivement, je dirais 5 cases maximum.

Argh... En fait je suis alle jusqu'a 4, et j'ai eu la flemme de tenter le 5 parce que je me suis dit qu'il fallait trop de manip, j'ai suppose que ca passait !

**matthias** · 16/03/2006, 18h08

Bon, en fait la solution consiste à créer une fonction qui associe une valeur à chaque situation et qui décroisse à chaque coup joué. Si on dispose d'une telle fonction, il est clair qu'à partir d'une situation de valeur A, on ne pourra jamais aboutir à une situation de valeur B > A.

Jusque là, c'est très théorique.

Commençons par associer une valeur à chaque emplacement, et on prendra comme fonction la somme des valeurs des emplacements non vides.

Posons $\psi = \frac{\sqrt{5}-1}{2}$ (solution de x²+x=1).

On associe à l'emplacement (x;y) la valeur $\psi^{|x|+5-y}$ , et on a donc notre fonction d'évaluation d'une situation.

Il ne reste plus qu'à démontrer que la fonction que l'on a créée décroit à chaque coup joué, puis que l'on ne peut pas passer de la situation demi-plan inférieur rempli à une situation où l'on aurait un pion en (0;5).

Oui je sais, c'est pas super intuitif mais bon, ça passe un peu mieux avec un dessin (que je n'ai pas fait)