IV-3. Quel est le nombre qui continue
cette suite : 2, 12, 1112...
FOIRE AUX QUESTIONS DE fr.sci.maths CHAPITRE IV: ENIGMES
IV-3. Quel est le nombre qui continue
cette suite : 2, 12, 1112...
SUJET PRECEDENT - INDEX - SUJET SUIVANTLa construction de la suite se fait comme suit : il faut lire à haute voix les chiffres qui la composent. On part de " 2 ", on lit un " 2 ", on écrit 12. Puis, on lit un " 1 ", un " 2 " on écrit 1112. On lit trois " 1 ", un " 2 ", on écrit 3112. On peut montrer par l'absurde que le nombre de signes distincts qui composent cette suite se limite aux chiffres 1, 2 et 3. En effet, supposons qu'à une ligne on trouve le chiffre 4, suivi par exemple du chiffre 1. Cela signifie qu'à la ligne précédente, on avait la suite ...1111... C'est à dire à la ligne d'avant ...11..., que l'on aurait dû traduire par 21 et non 1111 comme cela a été fait. D'où contradiction. Il ne peut donc pas y avoir de chiffre supérieur strictement à 3. Dans la suite, on prendra la convention : u(0)=2 u(1)=12 u(2)=1112 etc. Nous nommerons u(n) la valeur trouvée à l'étape n Cette suite ne peut pas se stabiliser, et même elle tend vers l'infini. nous savons calculer u(n+1) en fonction de u(n) mais aussi, en toute logique, u(n-1) en fonction de u(n) (cela paraît évident) qui n'a qu'une seule valeur possible en fonction de u(n). Ainsi, supposons qu'il existe m>n tels que u(m) = u(n) alors, d'après l'observation précédente, u(m-1) = u(n-1) et finalement par une récurrence évidente, u(m-n) = u(0) = 2. Or m-n>0 donc d'après la méthode de construction de la liste, u(m-n) a un nombre pair de chiffres d'où une contradiction. Donc quels que soient m et n, u(m)<>u(n) ; soit v(n) la suite définie de la façon suivante : si il existe k tel que u(k)=n alors v(n)=k. Sinon, v(n)=0 Quel que soit A de N, N=max(v(0)...v(N)) => (n>N => u(n)>A). Donc u(n) tend vers l'infini. On peut même montrer que le nombre de 1 diverge : Je nomme groupe une suite de chiffres faisant partie d'une autre suite: non décalé (gn) si il commence par un chiffre de rang impair groupe décalé (gd) si il commence par un chiffre de rang pair (1232 est un gn de 221232 et un gd de 2221232). Si X et Y sont deux groupes, je note X -> Y si une partie de X engendre Y en remontant dans les termes de la suite (engendrer sera toujours employé dans ce sens). ex : 1112 (gn) -> 12 2322 (gn) -> 3322 2322 (gd) -> 222 (en effet, les chiffres peuvent être groupés par deux lorsque l'on remonte dans la suite). On appellera un doublet, une gn de deux chiffres. Deux doublets consécutifs ne peuvent pas se terminer par le même chiffre (on appellera cela une incompatibilité de répétition ir) le groupe 333 ne peut pas exister car il contient forcément un doublet 33 et donc engendrera forcément 333 ce qui par récurrence arrive à une contradiction évidente. le doublet 33 ne peut donc pas exister. Un groupe contenant un doublet 33 provoquera une incompatibilité 3 (i3). Cherchons les gn de quatre chiffres ne contenant pas de 1 et ne provoquant pas d'incompatibilité (ie: pouvant exister dans la suite): je ne regarde pas les ir et les i3 triviales : 2223 -> 2233 supposé compatible 2322 -> 3322 supposé compatible 2332 -> 33222 i3 si gn et ir si gd incompatible 3223 -> 22233 supposé compatible tous les autres sont incompatibles. Cherchons les gn de huit chiffres ne contenant pas de 1 et ne provoquant pas d'incompatibilité (il sont constitués des gn de quatre chiffres compatibles): 22232223 -> 22332233 i3 si gn donc gd -> 3322233 i3 dans tous les cas 22232322 ir 22233223 -> 223322233 i3 dans tous les cas 23222223 ir 23222322 -> 33223322 i3 si gn donc gd -> 22233222 i3 si gd et ir si gn 23223223 ir 32232223 -> 222332233 i3 si gd donc gn -> 223322233 i3 dans tous les cas 32232322 ir 32233223 -> 2223322233 i3 dans tous les cas Donc tout gn de 8 chiffres contient au moins un 1. Cette suite tendant vers l'infini, le nombre de gn de 8 chiffres (même sans recouvrement) tend vers l'infini. Donc le nombre de 1 aussi. On constate que la fin du code est stabilisée dès la 6ème itération pour ses signes finaux. On note D la transformation telle que u(n+1)=D(u(n)). On note |X| le nombre de chiffres du groupe X. Lemme 1 : pour n>=6, u(n) se termine par 222112 si n est pair, et par 322112 si n est impair. par récurrence. C'est vrai pour n = 6. Soit n > 6, supposons la propriété vérifiée pour n et montrons la pour n+1. Si n est pair, u(n) se termine par 222112. Le chiffre précédent, s'il existe, n'est pas un 2 (puisqu'on n'a pas 4 chiffres identiques consécutifs). Donc u(n) se termine par un bloc de trois 2, puis un bloc de deux 1, puis un 2, et donc u(n+1) se termine par 322112 ; n+1 étant impair, c'est précisément ce qu'on attendait. Si n est impair, u(n) se termine par 322112. Peu importe si le chiffre précédent est un 3 ou non, seuls les trois derniers blocs nous intéressent, et u(n+1) se termine donc par 222112 ; n+1 étant pair, c'est ce qu'on attendait. Lemme 2 : soit x(n) la suite définie pour n>=6 par x(6)=222112, x(7)=322112, x(8)=3222112, x(9)=3322112, x(10)=23222112, et pour n>=10, x(n+1) est égal à D(x(n)) privé de son premier chiffre. 1. Pour tout n>=6, x(n) est un suffixe de u(n). 2. Pour tout n>=6, x(n) est un suffixe de x(n+2). 3. Pour n>=11, |x(n)| est impair et |x(n+2)| >= |x(n)|+2. 4. Pour tout n, |x(n)| >= n-2. Preuve : 1. Par récurrence sur n, d'après la définition de u(n). Noter qu'il est important d'enlever le premier chiffre de D(x(n)) pour construire x(n+1), car le chiffre précédant x(n) dans u(n) peut être identique au premier chiffre de x(n), ce qui modifie la longueur du premier bloc ; en revanche, le second chiffre de D(x(n)), qui indique la nature du premier bloc de x(n), peut être conservé car il apparaît bien à cet endroit dans u(n+1). Au passage, on peut noter que ce chiffre est toujours un 2. 2. Par récurrence sur n. On le vérifie à la main pour n < 10. Pour n>=10, si x(n) est un suffixe de x(n+2), alors x(n+1) est un suffixe strict de D(x(n+2)), donc c'est un suffixe de x(n+3). 3. Pour n>=11, la longueur de x(n) est impaire par construction. On montre |x(n+2)| >= |x(n)|+2 par récurrence. C'est vrai pour n=11 (et même n=9 et n=10). Supposons que |x(n+2)| >= |x(n)|+2 pour un certain n>=11. Comme x(n) est un suffixe de x(n+2), on peut écrire x(n+2) = wx(n), avec |w| >= 2. L'avant dernier chiffre de w ne peut être égal au premier chiffre de x(n), car il s'agit de deux chiffres consécutifs en position impaire qui sont toujours distincts dans une image par D. Par conséquent D(x(n+2)) contient au moins un bloc de plus que D(x(n)) et donc |D(x(n+2))| >= |D(x(n))|+2, d'où |x(n+3)| >= |x(n+1)|+2. 4. Se déduit facilement des valeurs initiales et de 3. Théorème : pour tout l>=0, il existe un entier n0 tel que pour tout n > n0, le suffixe de longueur l de u(n) coïncide avec le suffixe de longueur l de u(n+2). C'est vrai d'après le lemme 1 pour l <= 6, en prenant n0 = 6. Pour l supérieur à 6, on prend n0 = l+2. Alors pour n > n0, le suffixe de longueur l de u(n) est un suffixe de x(n), puisque |x(n)| >= n-2 >= l d'après le 4. du lemme 2. Il coïncide donc avec le suffixe de longueur l de u(n+2), puisque x(n) est un suffixe de x(n+2) qui est un suffixe de u(n+2). ( d'après les 2. et 1. du lemme 2. ) On peut formaliser ce résultat en définissant une topologie convenable sur l'ensemble des mots finis et infinis sur l'alphabet {1,2,3}. On peut alors montrer que la suite u(n) a deux valeurs d'adhérence, qui sont deux mots infinis à gauche : ...131221121321131112111322311211132132212312211322212221121123222112 et ...211331123113221321123113121322111213112221133211322112211213322112 Exercice : faire la même chose en regardant cette fois le début des mots (ce qui est plus habituel que de regarder la fin, d'ailleurs !). Cette fois, il y a 3 valeurs d'adhérence. Enfin, on peut montrer que la proportion de 1 a une limite finie, qui est un nombre algébrique de degré 71. L'idée de Conway est d'identifier un certain ensemble fini de blocs (qu'il nomme selon les éléments chimiques), de sorte que si x est l'un de ces blocs, D(x) s'exprime comme concaténation de plusieurs blocs élémentaires, et de plus qu'il n'y ait jamais d'interaction entre blocs consécutifs, de sorte que D(xy) = D(x)D(y). D agit alors comme une substitution (i.e. un morphisme de monoïde) sur les mots formés de symboles de blocs élémentaires, et le nombre d'occurrences de chacun des blocs élémentaires peut être exprimé à l'aide de puissances de la matrice de la substitution. D'où finalement une densité qui s'exprime en fonction des valeurs propres de cette matrice et est donc un nombre algébrique. Lire à ce sujet: -- J.H. Conway "The weird and Wonderful Chemistry of Audioactive Decay" in "Open Problems in Communications and Computation" T.M. Cover and B. Gopinath eds., Springer 1987 -- Shalosh B. Ekhad and Doron Zeilberger "Proof of Conway's Lost Cosmological Theorem" Voir, entre autres (Warning, in english) : http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/SEQUENCES/series000 http://www.univie.ac.at/EMIS/journals/ERA-AMS/1997-01-011/1997-01-011.html http://www.math.temple.edu/~zeilberg/mamarim/mamarimhtml/horton.html