énigme solitaire

[matthias]

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 :
-----

[invite35452583]

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

[martini_bird]

Salut,

au premier ordinal transfini ? Tu fais comment?

[invite986312212]

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.

[A voir en vidéo sur Futura]

[matthias]

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

[invite986312212]

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]

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]

Salut,

Intuitivement, je dirais 5 cases maximum.

[matthias]

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]

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]

On peut aller plus loin que 5 ?

Non.

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

Normal, ce n'est pas possible
Le max est bien 4.

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]

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...

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]

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.

[invite35452583]

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]

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...

[invite986312212]

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]

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]

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 (solution de x²+x=1).

On associe à l'emplacement (x;y) la valeur , 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)

[Evil.Saien]

Suis-je le seul a n'avoir rien compris ???

[yat]

Suis-je le seul a n'avoir rien compris ???

Non, rassure-toi

[matthias]

C'est plus facile à expliquer avec les mains

Bon, vous avez compris comment on évalue une situation ?
Imaginons que je n'ai que deux pions, un en (1;2) et un en (0;5), la fonction d'évaluation vaut :



Ce qu'il faut commencer par montrer, c'est que la fonction d'évaluation ne peut que décroître à chaque coup joué. Ce n'est pas difficile, chaque coup ne modifiant que trois cases contigues.

[matthias]

Bon j'ai fait un petit effort pour que les valeurs affectées à chaque emplacement soient un peu plus claires :



La valeur 1 est sur l'emplacement (0;5).
Les valeurs pour y > 5 n'ont pas d'importance car on n'a pas besoin d'évaluer de situation où un pion serait au delà de la 5ème ligne.

Toutes les séries de trois cases consécutives (en horizontal ou vertical) étant de la forme ou , il est facile de démontrer que la fonction d'évaluation ne peut pas augmenter quand on joue un coup, puisque :







(car )

C'est plus clair ?

[Evil.Saien]

Superbe schema explicatif matthias !

T'as eu bien du courage de le faire !

Mais a part ca, j'ai toujours du mal a comprendre, sans doute a cause de mes capacites limites, t'en fait pas !

[matthias]

Mais a part ca, j'ai toujours du mal a comprendre

Dis moi où tu coinces, ça m'obligera à être plus clair.
Tu as compris comment on calcule l'évaluation d'une situation ?
On fait simplement la somme des valeurs associées aux "cases" sur lesquelles il y a un pion.

Si tu as compris ça, as-tu compris pourquoi la valeur diminue, ou reste stable, à chaque fois que l'on joue un coup ?

[yat]

Bon, en ce qui me concerne, maintenant j'ai compris pourquoi on prend la solution de x²+x=1... ( )
Ce qui me perturbe un peu, c'est que la solution est déjà dans la fonction de départ... En gros, il faut déjà savoir que la hauteur maximale est 5 pour choisir la fonction de sorte que la somme des valeurs des cases sous la ligne soit strictement inférieure à 1...

Ca n'aurait pas marché en virant ce 5 ? La décroissance reste valable, et il suffit ensuite de calculer la somme des cases sous la ligne et de regarder quelle est la case la plus haute qui ait une valeur inférieure ou égale à cette somme, non ?

[invite6b1e2c2e]

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).

Bonjour,

Je comprends pas pourquoi ça empêche la configuration x=0, y >=5.
Y a quelque chose que j'ai du rater
En tout cas, c'est un très joli problème, et plutot contre-intuitif.

__
rvz, qui adore ces petits problèmes apparemment tout simples

[matthias]

Ce qui me perturbe un peu, c'est que la solution est déjà dans la fonction de départ... En gros, il faut déjà savoir que la hauteur maximale est 5 pour choisir la fonction de sorte que la somme des valeurs des cases sous la ligne soit strictement inférieure à 1...

Oui, c'est un peu parachuté (doux euphémisme)

Ca n'aurait pas marché en virant ce 5 ? La décroissance reste valable, et il suffit ensuite de calculer la somme des cases sous la ligne et de regarder quelle est la case la plus haute qui ait une valeur inférieure ou égale à cette somme, non ?

Pourquoi pas en effet.

[yat]

Je comprends pas pourquoi ça empêche la configuration x=0, y >=5.

-On a une fonction qui associe une valeur réelle à une situation donnée.
-On montre facilement que la valeur de cette fonction décroit à chaque fois que l'on joue un coup
-On constate que la valeur de la fonction est plus grande quand on a juste une bille en (0;5) que quand on a des billes sur toutes les cases d'ordonnée négative ou nulle.

Donc quand on ne commence la partie avec que des billes sous la ligne, la valeur de la fonction est déjà inférieure à celle qu'elle aurait si on avait une bille sur la cinquième ligne. Or, il est impossible de jouer un coup qui fasse augmenter cette valeur, donc on ne peut pas placer une bille sur la cinquième ligne.

[invite6b1e2c2e]

Ah oui !
Tout s'éclaire. C'est vraiment très très beau.
Même si je trouve ça beau parce que je n'aurai jamais pu trouver cela seul. Y a quand même des gens qui ont de ces intuitions...

__
rvz

[matthias]

Bonjour,

Je comprends pas pourquoi ça empêche la configuration x=0, y >=5.
Y a quelque chose que j'ai du rater
En tout cas, c'est un très joli problème, et plutot contre-intuitif.

En faisant le calcul, tu vois que si ta situation initiale est le demi-plan inférieur rempli, la fonction d'évaluation vaut 1 (moins si le demi-plan n'est pas rempli).
Si tu as un pion en (0;5) la fonction d'évaluation vaut au moins 1.
On pourrait dire que ce n'est pas décisif puisque la fonction n'est pas strictement décroissante, mais si on peut atteindre la cinquième ligne, on peut le faire en un nombre fini de coups, donc si on est parti avec le demi-plan rempli, il reste des pions dedans, et donc la valeur finale est strictement supérieure à 1 (ou autre manière de voir, si on peut atteindre la cinquième ligne en un nombre fini de coups, on peut le faire avec une situation initiale où le demi-plan n'est pas rempli).

[EDIT: désolé, j'ai été un peu lent ]