Problème n° 99, la suite de Mathilde ; le corrigé
Maths ...
Problèmes de l'année 2019-2020
Problème n ° 99
La suite de Mathilde, le corrigé
-
Enoncé du problème n° 99
Enoncé du problème n° 99
- Mathilde écrit le nombre 1.
- Ce premier nombre compte 1 chiffre 1. Mathilde écrit donc 11.
- Ce deuxième nombre s'écrit avec 2 chiffres 1. Mathilde écrit donc 21 (troisième nombre).
- Elle écrira ensuite 1211,
- puis 111221, etc $\ldots$
Si Mathilde écrivait 27 nombres, le dernier nombre écrit compterait 2012 chiffres ! Mais Mathilde s'arrête après avoir écrit le 13e nombre.
Combien ce 13ème nombre compte-t-il de chiffres ? -
Correction du problème n°99
$$\begin{array}{|c|c|} \hline n& u_n \\ \hline 1 &1 \\ 2 &11 \\ \hline 2 & 21 \\ \hline 3 & 1211 \\ \hline 4 &111221 \\ \hline 5 & 111221 \\ \hline 6 & 312211 \\ \hline 7 & 13112221 \\ \hline 8 & 1113213211 \\ \hline 8 & 31131211131221 \\ \hline 10 & 13211311123113112211 \\ \hline 11 & 11131221133112132113212221 \\ \hline 12 & 3113112221232112111312211312113211 \\ \hline 13 & 1321132132111213122112311311222113111221131221 \\ \hline \end{array} $$
Le nombre $u_n$ s'obtient en appliquant un codage des répétitions d'un même chiffre (RLE ou run-length encoding) au nombre $u_{n-1}$.
Tant que la taille d'un bloc ne dépasse pas 9, le nombre de chiffres de $u_n$ vaut 2 fois le nombre de blocs de $u_{n-1}$.\\ Ainsi dans $u_{12}$ il y a 23 blocs (3, 1, 3, 1, 2, 1, 2, 3, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 2, 1) formant les chiffres de rang pair de $u_{13}$ qui s'écrit donc avec 46 chiffres.Les 25 premiers termes!
$$\begin{array}{|c|p{0.9\linewidth}|}\hline n & u_n \\ \hline 1& 1 \\ \hline 2 &11\\\hline 3& 21\\\hline 4& 1211\\\hline 5 &111221\\\hline 6& 312211\\\hline 7& 13112221\\\hline 8 &1113213211\\\hline 9& 31131211131221\\\hline 10 &13211311123113112211\\\hline 11& 11131221133112132113212221\\\hline 12 &3113112221232112111312211312113211\\\hline 13& 1321132132111213122112311311222113111221131221\\\hline 14& 11131221131211131231121113112221121321132132211331222113112211\\\hline 15 &311311222113111231131112132112311321322112111312211312111322212311322113212221\\\hline 16& 132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211 \\ \hline 17& 111312211312111322212321121113122123211231131122211211131221131112311332211213211321322113311213212312\\ & 31121113122113322113111221131221 \\\hline 18& 3113112221131112311332111213122112311311221112131221121321132132211231131122211331121321232221121113122113121\\ &1132221232112111312111213111213211231131122212322211331222113112211 \\\hline 19& 1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121\\ &112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221\\ \\\hline 20& 111312211312111322212321121113121112131112132112311321322112111312211312112213211231132132211231131122211311123113322\\ & 112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211\\ & 21113122113121113123112112322111213211322211312113211\\ \\\hline 21& 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132\\ & 1132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311\\ & 1213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221\\ \\\hline 22& 13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113312211223113112221121113122\\ &11311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112\\ &31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211\\ &312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211\\ \hline 23& 11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111\\ &3122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132\\ &22123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113112221121321\\ &13311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121\\ &11312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221\\ \\\hline 24& 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211\\ \\\hline 25& 132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221 \\\hline \end{array} $$
