312211 ?

Salut

 Cliquez pour afficher

312211
13112221
1113213211
......

Celle-ci commence un peu différemment:

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

Un lien aurait été préférable à ce copier coller, non ?

Bravo a tous vous avez tous trouvé la solution, et merci à Dani pour ces précisions sur cette énigme.

Je me disais aussi : arriver à tapper tous ça en 6 min, c'est surhumain

( :D )

Salutatous !