Soldats de Conway ----------------- Démonstration détaillée I Présentation du problème /_/_/_/_/_/_/_/_/_/_/_/_/_/ Exemple de jeu : ---------------- +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | | | ============================= | | | | X | X | X | | +---+---+---+---+---+---+---+ | | | | | X | X | | +---+---+---+---+---+---+---+ Les pions marqués X sur le schéma ci-dessus permettent avec les règles du solitaire d'obtenir successivement les configurations ci-dessous : +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | Y | Y | | ============================= | | | | X | ^ | ^ | | +---+---+---+---+---+---+---+ | | | | | ^ | ^ | | +---+---+---+---+---+---+---+ puis +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | Z | < | < | | ============================= | | | | X | | | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ et pour terminer +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | A | | | | +---+---+---+---+---+---+---+ | | | | ^ | | | | ============================= | | | | ^ | | | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ (où ^ et < indiquent les pions déplacés ou éliminés) Cet exemple est une solution pour n=2 du problème suivant : Quelles configurations de pions situés au-dessous de la frontière (notée ============================= sur les figures) permettent t-elles d'obtenir un pion final unique situé au-dessus de la frontière, à la distance n de celle-ci ? On connaît des solutions de ce problème pour n=1, n=2, n=3 et n=4. Le but des lignes suivantes est de montrer qu'il n'y a pas de solution pour une distance n supérieure ou égale à 5 II Quelques considérations préliminaires /_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/ Solitaire inverse ----------------- Le mathématicien et philosophe Leibniz (1646 - 1716) s'était intéressé au jeu du solitaire et avait remarqué que l'on pouvait étudier le jeu inverse : remplacer un pion par deux pions (retrouver les deux pions initiaux à partir du pion final). Pour simplifier l'exposé, on va montrer que si un pion est à la distance n=5 au-dessus de la frontière, alors on ne peut pas le décomposer (suivant le solitaire inverse) en une confuguration finie de points situés tous au-dessous de la frontière. Dans le solitaire inverse, le pion O . . est remplacé par les deux pions X Y vers la droite, la gauche, le bas ou le haut, au choix haut Y (Au choix) X gauche Y X O X Y droite X Y bas Distance parcourue ------------------ supposons par exemple que 0 se décompose en deux pions X et Y comme ci-dessous 0 X Y X s'est placé à une distance 1 et Y à une distance 2 du pion O initial Dans le cours du jeu, X et Y vont peut-être se décomposer à nouveau en pions fils qui auront, si on veut bien leur accorder cette possibilité, la mémoire des déplacements de leurs ancêtres. Après un certain temps de jeu, un pion situé à (h, v) cases horizontalement et verticalement du pion initial 0, aura été obtenu après un déplacement au moins égal à h+v. +---+---+---+---+---+---+---+ en indiquant les distances parcourues | | | |(0)| | | | les pions (n) ont disparu +---+---+---+---+---+---+---+ il ne reste que cinq pions | | | |(1)|(2)|(3)| | 2, 3, 4, 4, 5 ============================= Les déplacements sont supérieurs ou égaux | | | | 2 | 3 | 4 | | aux distances h+v au pion initial (0) +---+---+---+---+---+---+---+ (ici égaux) | | | | | 4 | 5 | | +---+---+---+---+---+---+---+ Masses ----------- Affectons la valeur 1 (masse) au pion initial et, à chaque étape du jeu, en décomposant un pion de masse A>0, donnons les masses B>0 et C>0, de somme B+C = A aux deux pions produits. À chaque étape du solitaire inverse, la somme des masses de tous les pions restera 1. Il y a conservation de la masse totale 1. Quelques résultats sur des sommes de suites (géométriques) ---------------------------------------------------------- 1) L'équation du second degré t^2+t-1=0 a deux racines, la racine positive x vaut x = (-1+sqrt 5)/2. L'autre racine est (-1 -sqrt 5)/2 On a donc x^2 + x - 1 =0 et aussi 1 = x + x^2 et encore 1-x = x^2 On en déduit en multipliant par x ou x^2 ou ... x = x^2 + x^3, x^2 = x^3 + x^4, ... 2) la somme s = 1 + x + x^2 + x^3 + ... est le développement en série de s = 1/(1-x) et pour la valeur particulière donnée à x on a s = 1/x^2 3) Pour t variable, la série 1 + t + t^2 + ... a pour rayon de convergence 1 et sa somme est 1/(1-t) S = t^5 + 3t^6 + 5t^7 + 7t^8 + ... en multipliant par t tS = t^6 + 3t^7 + 5t^8 + ... en soustrayant mbre à mbre ------------------------------------- S-tS = t^5 + 2t^6 + 2t^7 + 2t^8 + ... S(1-t)= t^5 +2t^6(1+t+t^2+...) S (1-t)= t^5 + 2t^6/(1-t) En particulier avec t=x tel que 1 = x+ x^2 et 1-x = x^2 S x^2 = x^5 + 2x^4 S = x^3 + 2x^2 = x^3 + x^2 + x^2 = x + x^2 = 1 4) Distance (taxidistance) M(x, y) et M'(x', y') d(M, M') = |x'-x| + |y'-y| est bien une distance et satisfait à l'égalité triangulaire d(A, B) + d(B, C) >= d(A, C) en particulier pour A B C .. D, d(A, D) est inf. ou égal à la somme des distances d(A, B) + d(B, C) + d(C, .)+ ... + d(., D) III Méthode de Conway /_/_/_/_/_/_/_/_/_/_/ 1) Principe ------------- On suppose que l'on sait décomposer progressivement le pion initial puis ses descendants en un ensemble fini de pions tous disposés sur le demi-plan inférieur, (avec conservation des masses). On montre que la somme des masses ne peut être égale à la masse initiale 1 et donc qu'il y a contradiction. 2) Décomposition des masses ---------------------------- a) masse et écart le pion initial de masse 1 est décomposé en deux pions de masses x (le plus près) et de masse x^2 (le plus éloigné) (1) -> x x^2 où x = (-1+sqrt 5)/2 et 1 = x + x^2 comme expliqué plus haut Ensuite un pion x est décomposé en x^2 + x^3, un pion x^2 en x^3 + x^4 et ainsi de suite, x^n est décomposé en x^(n+1) (le plus près de x^n) et en x^(n+2) (à la distance 2 de x^n) Une fois la décomposition terminée, chaque pion marqué x^n a pour masse x^n et son trajet (cumulé à celui de ses ancêtres, depuis le pion initial) est n, sa distance au pion initial (somme de l'écart horizontal et de l'écart vertical au pion origine) est inférieure ou égale à n, d'après l'inégalité triangulaire +------+------+-------+-------+-------+ | | | 0 | 1 | 2 | distance au pion (x) éliminé | | | (x) | x^1 | x^2 | monôme associé au pion, au début | | | (x^n) | x^n+1 | x^n+2 | ou dans le cas général +------+------+-------+-------+-------+- b) retour à l'exemple Sur le schéma ci-dessous, le pion initial est marqué 1 +---+---+---+---+---+---+---+ monômes et pions | | | |(1)| | | | +---+---+---+---+---+---+---+ Voici ce que l'on obtient en | | | | | | | | partant du 1 placé sur la deuxième ligne ============================= au-dessus de la frontière. | | | |x^2|x^3|x^4| | Vous pouvez vérifier que +---+---+---+---+---+---+---+ 1 = x^2 + x^3 + 2x^4 + x^5 | | | | |x^4|x^5| | les autres cases sont vides +---+---+---+---+---+---+---+ c) majoration des masses ------------------------ Dans les cases sous la frontière sont préalablement placées les distances au pion origine Après décomposition, sur une case à la distance n du pion initial, se trouve un pion de masse x^n' avec n'>=n et donc de masse x^n' <= x^n (car 0 x^6 > x^7 ...) Les jetons qui seront placés sur ces cases auront effectué un trajet au moins égal à celui indiqué (par l'exposant) et leurs masses seront inférieures ou égales aux masses indiquées sur la figure (le pion sur une case marquée x^5 sera en réalité x^5 ou x^6 ou x^7 ... avec x^5 > x^6 > x^7 ...) Les valeurs n indiquées sur le schéma ci-dessous donnent bien bien des majorants x^n des masses des jetons qui se trouveront placés sur ces cases. En outre ces cases seront la plupart vides de pions et la masse sera évidemment 0 et non la valeur x^n. La majoration sera donc stricte dans la plupart des cas (l'infinité des cases vides en particulier) +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | 0 | | | | <-- pion initial au niveau 5 +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | | | ============================= | 8 | 7 | 6 | 5 | 6 | 7 | 8 | distance h+v au pion +---+---+---+---+---+---+---+ initial | 9 | 8 | 7 | 6 | 7 | 8 | 9 | La somme +---+---+---+---+---+---+---+ S = x^5 + 3x^6 + 5x^7 + ... | 10| 9 | 8 | 7 | 8 | 9 | 10| = 1 +---+---+---+---+---+---+---+ (démonstration préalable) | 11| 10| 9 | 8 | 9 | 10| 11| +---+---+---+---+---+---+---+ | 12| 11| 10| 9 | 10| 11| 12| La somme des masses des jetons (en nombre fini) est donc strictement inférieure à S = 1 d'où la contradiction annoncée. IV Conclusion /_/_/_/_/_/_/_/ Il est impossible d'accéder au niveau 5 à l'aide d'un nombre fini de pions placés sous la frontière. Et donc aussi, (sans avoir besoin de refaire un calcul), l'impossibilité d'obtenir un pion à un niveau supérieur à 5.