Une suite simple, mais la suite ne l'est peut être pas ...

Nightmare

Bonjour à tous :bye1:

Voici une question/énigme que j'avais déjà posté sur un autre forum et dont la réponse est toujours en suspent (je ne l'ai pas moi même ...).
Je vous la soumet, peut être trouverez-vous une solution :)

Vous devez surement tous connaitre la suite logique :

Code : Tout sélectionner

Chaque ligne est déduite de la précédente par simple jeux de prononciation :

Ligne 3 : 21
En lisant chaque chiffre et le nombre de chiffre à la suite, on pourrait lire : Un 2 et un 1

On obtient ainsi la ligne 4 : 1211
Pareillement cette ligne peut se lire : Un 1, un 2 et deux 1

On obtient alors la ligne 5 : 111221
etc ...

Ma question n'est pas de compléter cette suite triviale (si c'était le cas, vous vous doutez bien que je n'aurais pas donné l'astuce ;)) mais est d'exploiter cette suite.

Voici la question : Peut-on trouver, pour tout n entier, le nombre de chiffres dont sera composée la n-iéme ligne ?

En fait on recherche une formule de réccurence liant la ligne n au nombre de chiffre $\rm U_{n}$

Nous avons réussi à démontrer que la suite ne pouvait pas contenir de 4 (je vous laisse réfléchir à cette démonstration) et alors conjecturé que la suite n'était pas monotone (à démontrer). Mais la réponse à la question reste encore loin ...

A vos crayons et merci de votre participation.

:)
Jord

Message non lu par MB » mardi 14 février 2006, 14:32

Bonjour Nightmare.

En ce qui concerne ta question : cette suite semble assez difficile a modéliser mathématiquement et la réponse à ta question risque d'être assez laborieuse.

Une chose semble évidente, c'est que $U_n$ est paire pour tout $n \geq 2$.

En ce qui concerne ta conjecture visant à dire que cette suite n'est pas monotone, moi je dirais plutôt qu'elle semble croissante. Tu dis également qu'il n'y a pas de 4 : c'est vrai mais on peut dire qu'il n'y a que des 1, 2 ou 3.

On remarque donc que les nombres vont par deux, et que les seuls couples possibles sont (et il semble assez clair que le coupe 33 ne peut pas apparaître) :

$\begin{array}{|c|c|c|}
\hline
11 & 21 & 31 \\
\hline
12 & 22 & 32 \\
\hline
13 & 23 & 33 \\
\hline
\end{array}$

Il est également clair que chaque couple ne peut pas être suivi ou précédé d'un couple situé sur la même ligne que lui. En étudiant les différentes combinaisons possibles, on doit pouvoir obtenir la croissance de la suite.

Voilà pour ces quelques pistes.

Salut!

Il paraît assez clair qu'il n'y a pas de 4.
Par l'absurde on doit pouvoir montrer que le petit jeu de prononciation tomberait à l'eau ou que l'on ne pourrait pas remonter à $U_0$.

Par contre, j'aurais dit qu'elle était croissante cette suite. Sinon il n'y a qu'a programmer un algo qui calcule les 10000000 premiers termes. Ca donnera une idée de ta conjecture. Si ça reste croissant, faudra peut-être essayer de montrer que ça l'est plutôt que le contraire...

En gros, comme on est en base 3 et il est possible de faire une fonction qui à un certain nombre en base 3, renvoie un autre nombre en base 3 (suivant des règles à déterminer). Tout ça me fait penser au domaine des langages et automates finalement, plus qu'à celui des suites numériques.

Nightmare

Bonsoir et merci à vous pour vos réponses.

Oui en effet la suite semble croissante avec Maple (je le sais depuis cet aprem d'où l'erreur dans ma conjecture).

Effectivement il me semble qu'arriver à la solution (si elle existe) va être une tâche laborieuse.

:)

Message non lu par MB » mardi 14 février 2006, 23:53

Nightmare a écrit :Oui en effet la suite semble croissante avec Maple (je le sais depuis cet aprem d'où l'erreur dans ma conjecture).

Tu peux copier les 25 premières lignes (ou valeurs de $U_n$) ?

Sinon, pour prouver la croissance, ça doit pas être trop difficile (mais il faut étudier tous les cas par contre) ...

Nightmare

Numéro de la ligne, nombre d'éléments

Code : Tout sélectionner

[Edit: MB] Utilisation de la balise code.

linfir

C'est la suite A005150. Il me semble que Conway a montré que cette suite vérifie une récurrence linéaire d'ordre 72 (de mémoire), ce qui (en théorie) fournit une réponse à ta question.

Message non lu par MB » mercredi 15 février 2006, 02:44

En effet, ce lien est fort instructif. Le sujet a donc déjà été bien travaillé !
Vous pouvez également regarder ici pour d'autres informations. (Je déplace ce message dans la section Mathématiques.)

Nightmare

Merci pour ces liens et de votre participation :)

Message non lu par MB » mercredi 15 février 2006, 19:27

De rien, par contre, j'ai toujours la cette fameuse relation de récurrence !

Endymion

Bonjour,
il me semble avoir lu pas mal de choses dans un dossier de La Recherche ou de Pour la science ily a 4 ou 5 ans. Conway a effectivement montré qu'il n'y a pas de 4 et que cette suite a une croissance exponentielle. Il y avait autre chose de surprenant. Je deteste quand le "mystique" se mêle aux maths (cf Da Vinci Code...). Voilà ce que disait l'article :

On dit qu'on passe d'un terme au suivant en faisant son "commentaire" (noté C).

En suite, Conway cherche quels sont les séquences $a_1\dots a_n $telles que
$C(a_1\dots a_n )=C(a_1\dots a_j) C(a_{j+1} \dots a_n)$ (je ne suis plus très sur...). Il les appelle atomes.
Il démontre qu'il y en a exactement 92. Premiere coïncidence, avec les atomes, qui sont au nombre de 92 si on ne tient pas compte des transuranides (ceux dans les cases en bas rajoutées;) )

Il appelle Univers la suite présentée. Il calcule ensuite la proportion de chaque atome parmis les atomes de la suite "Univers".
Seconde coïncidence, d'après lui, chaque atome a une fréquence d'apparition proche qui correspond à la proportion des vrais atomes dans le vrai univers (exemple au pif: il y a 50% d'hydrogène "en vrai" et l'atome "1" est représenté 50% des fois parmis les atomes présents dans les termes de la suite, chaque terme étant constituée de 0,1,2,et de concaténations d'atomes). Ce procédé lui permet d'appeler "22" hydrogène, etc...

Pour que ce soit vraiment bluffant, voici la dernière coïncidence, dans la nature, il me semble que les atomes peuvent naturellement se décomposer, ainsi le carbone peut devenir de l'azote (là, j'ai oublié ce qu'on m'avait appris en terminale;( ) Je ne me rappelle plus du nom de ce procédé. En fait Conway affirme que si on prend l'atome qu'il a nommé carbone, on peut l'écrire qomme la concténation de deux séquences, et que si on fait le commentaire d'une de ces séquences, on va tomber sur...l'azote!

Voilà ce que je peux réstituer de mémoire de ce que j'ai lu il y a déjà 4 ans au moins. Essayez de retrouver l'article, ça devrait être intéressant de l'examiner en détail pour voir jusqu'où va le "mysticisme" de Conway!

Dernier point, toujours d'après Conway, si on commence par 2 au lieu de 1, la suite qu'on obtiendra donnera par l'étude des proportions des séquences autocommentées des atomes qui correspondent aux "transuranides", les atomes "manquant"...mais là encore ma mémoire me fait défaut!

Quand à savoir si ce "modèle" peut avoir une quelconque application...

A bientôt!