Ah oui, j'ai oublié ceci : il ne peut y avoir plus d'un jeton par case.

Salut trapangle.

 Cliquez pour afficher

On est bien d'accord que si j'ôte le jeton (0,1), il est remplacé par un jeton en (0,2) et 1 jeton en (1,1) et donc la nouvelle grille est bien :



Et si j'ai bien compris, on ne peut pas commencer par un des deux autres ...

Vous pouvez regarder le blank de jsvdb ci-dessus, c'est une question d'interprétation de l'énoncé, et comme j'essaie d'être le plus clair possible, autant que tout le monde en profite.
Si on ôte le jeton en (0,1), on le remplace par un jeton en (0,2) et un jeton en (1,1), et la nouvelle grille est bien ce que jsvdb a indiqué.
Mais on aurait aussi pu commencer par le jeton en (1,0), en le remplaçant par (2,0) et (1,1).
Par contre, on ne peut pas commencer par le jeton en (0,0), vu que les cases (0,1) et (1,0) sont occupées.

Voici le lien vers l'énigme originale (en anglais) :
Attention, si vous voulez continuer à chercher, la solution est disponible en un clic à partir de cette page

Je compte aussi traduire ici leur solution en français, je laisse encore quelques jours aux chercheurs éventuels. S'il vous faut plus de temps, prévenez-moi.

Sur la page il y a un lien vers le jeu où on peut cliquer

Sans regarder la solution, il me semble que en partant de

OO
O

O X
 OO
XO

Bonjour LittleFox,

Dans ton tableau, on dirait qu'il y a 3 états : O, X et ' ' (espace). Pour moi, il n'y en a que deux : jeton ou pas de jeton. Que représente le 3° état ?

Bon ok, non. On est pas obligé de passer par la deuxième configuration.

Mais maintenant j'ai vu la solution

J'avais déjà vu ce genre de résolution mais c'est plus dur quand on doit la sortir soit même ^^

Oui, en effet...je n'ai pas trouvé non plus, et je ne pense pas non plus que j'aurais pu penser à cette résolution.

Pour mes 3 états : O = jeton, ' ' = pas de jeton, X = un jeton ou pas on s'en fout

bonjour

Cela me semble impossible et, sauf erreur, je crois en avoir une preuve (dont je vous laisse vérifier les calculs intermédiaires )

 Cliquez pour afficher

Supposons qu'on y soit arrivé et que l'ensemble des cases occupées au final tienne dans un carré n x n. (avec n>2)

Je numérote les colonnes à partir de la gauche vers la droite par x variant de 0 à n-1
et les lignes en partant du bas par y variant de 0 à n-1

Je porte dans la case (x;y) la valeur 2^x+y

Le fait de supprimer un pion en le remplaçant par un pion à droite et un pion dessous ne change pas la somme des cases occupées

La somme de toutes les cases vaut ... (2ⁿ - 1)²

La somme des cases du carré 2x2 du haut à gauche vaut ... 2^2n-1 + 2^2n-4

La somme de toutes les cases , sauf le carré 2x2 en haut à gauche vaut ... 7.2^2n-4 - 2ⁿ⁺¹ + 1

Or la somme de la position de départ, qui restera invariante pendant tout le jeu vaut 2^2n-1

et comme 7.2^2n-4 - 2ⁿ⁺¹ + 1 < 7.2^2n-4 - 1 < 8.2^2n-4 - 1 < 2^2n-1

cela prouve qu'on ne peut vider le carré 2x2 en haut à gauche

pour dpi

 Cliquez pour afficher

Il y a de l'idée, mais...
Tu écris : "le fait de supprimer un pion en le remplaçant par un pion à droite et un pion dessous ne change pas la somme des cases occupées."
Si tu remplaces (0,0) par (1,0) et (0,1), on a 2⁰⁺⁰ 2¹⁺⁰+2⁰⁺¹

Pardon, c'était pour matheuxmatou, pas pour dpi

Bonsoir
Il s'agit d'une "fonction pagode".
3 problèmes (dont je suis l'inventeur d'un des trois) de ce genre avaient été posés dans la revue "Tangente"  N° 51-52 en 1996.

Bonjour,

Je ne trouve pas d'infos sur les fonctions pagode en français, et très peu en anglais, mais il me semble avoir compris ceci :

 Cliquez pour afficher

Une fonction pagode sert à démontrer l'infaisabilité de certains problèmes (en général, en rapport avec le déplacement des pions dans le jeu "solitaire")

trapangle

une erreur de copiage... d'ailleurs le reste du raisonnement permettait de la remarquer ... je rectifie :

 Cliquez pour afficher

Supposons qu'on y soit arrivé et que l'ensemble des cases occupées au final tienne dans un carré n x n. (avec n>2)

Je numérote les colonnes à partir de la droite vers la gauche par x variant de 0 à n-1
et les lignes en partant du bas par y variant de 0 à n-1

Je porte dans la case (x;y) la valeur 2^x+y

Le fait de supprimer un pion en le remplaçant par un pion à droite et un pion dessous ne change pas la somme des cases occupées

La somme de toutes les cases vaut ... (2ⁿ - 1)²

La somme des cases du carré 2x2 du haut à gauche vaut ... 2^2n-1 + 2^2n-4

La somme de toutes les cases , sauf le carré 2x2 en haut à gauche vaut ... 7.2^2n-4 - 2ⁿ⁺¹ + 1

Or la somme de la position de départ, qui restera invariante pendant tout le jeu vaut 2^2n-1

et comme 7.2^2n-4 - 2ⁿ⁺¹ + 1 < 7.2^2n-4 - 1 < 8.2^2n-4 - 1 < 2^2n-1

cela prouve qu'on ne peut vider le carré 2x2 en haut à gauche

matheuxmatou

 Cliquez pour afficher

L'erreur précédente m'empêchait de comprendre ton raisonnement, je n'aurais pas pu rectifier tout seul, merci.

C'est à peu près le même raisonnement que la solution proposée par l'auteur original, sinon que lui avait numéroté les cases en partant du coin supérieur gauche et qu'il raisonnait en puissances de 1/2, ce qui lui permettait d'ailleurs d'aller jusqu'à l'infini et de ne pas devoir faire l'hypothèse du carré n.n comme toi.
Je trouve cette démonstration élégante, elle fait appel à un invariant auquel je n'aurais jamais pu penser tout seul, bravo à toi.

trapangle

je ne connais pas la démo de l'auteur mais je comprends ce que tu veux dire... c'est pas mal aussi. Personnellement je préfère travailler avec des entiers plutôt que des fractions quand je peux.

Dans ce genre de truc, il faut essayer de trouver un invariant de situation. Mais pas toujours facile !

au début j'étais parti sur des combinaisons mais c'était horriblement compliqué... avant de trouver cette méthode beaucoup plus simple.

Pardon pour l'erreur stupide de confusion droite/gauche de mon premier post qui t'a fait perdre du temps

Traduction en français de la solution d'Alex Bellos (), qui n'est pas très différente de celle de matheuxmatou :

 Cliquez pour afficher

On soupçonne assez vite qu'il n'est pas possible de vider le carré orange de ses jetons. Une façon de le prouver est la suivante :
On remplit la grille avec un 1 dans la case en haut à gauche, puis 1/2 dans les deux cases adjacentes, 1/4 sur la diagonale suivante, etc. On arrive à un remplissage comme sur l'image ci-dessous.

Si les nombres remplis dans les cases représentent les poids de leurs cases respectives, on constate alors que la somme des poids sous les jetons est un invariant. Peu importe le nombre de fois où on remplace un jeton par deux jetons dans les cases à droite et sous le jeton original, la somme des poids des cases qui ont des jetons ne change pas.

Par exemple, s'il n'y avait qu'un jeton dans la grille, sur la case en haut à gauche, son poids serait de 1, puis en le remplaçant par deux jetons à sa droite et sous lui, le poids cumulé deviendrait 1/2 + 1/2 = 1, puis en remplaçant un de ces deux jetons par deux autres, le poids deviendrait 1/2 + 1/4 + 1/4 = 1, etc. Donc le poids total cumulé des jetons ne varie pas.

On calcule à présent le total des poids de la première ligne, c'est :

Pour la deuxième ligne :

Pour la troisième ligne :


Pour calculer le poids total de la grille, on fait la somme du poids des lignes :


Le poids des jetons dans les quatre cases oranges vaut


Donc le poids total qui peut-être placé dans la grille infinie dont on a retiré les quatre cases oranges vaut


Or le poids des trois jetons du départ vaut


Le poids des cases qui contiennent des jetons au départ est supérieur au poids des cases où les jetons peuvent être placés, il est donc impossible de vider le carré orange.

Bonjour
La démo (présentée par trapangle ci-dessus) est la plus élégante à mon avis. Fallait déjà l'imaginer.

salut

D'ailleurs ce n'est pas celle de trapangle puisque trapangle n'a rien trouvé du tout.
Ce n'est que la traduction de la démonstration présentée par l'auteur original, Alex Bellos, que j'avais promise précédemment (le 21/10), donc je l'ai ajoutée.

carpediem merci à toi