Exercice 2 — Listes — Olympiades 2012 La Réunion

Sujet

Une liste initiale contient tous les entiers de 1 à 2012 dans un ordre quelconque, écrits une seule fois.
L'opération suivante lui sera appliquée de manière répétée :
Si la première valeur de la liste est le nombre \(k\), alors les \(k\) premières valeurs sont réécrites dans l'ordre inverse de celui où elles étaient (les autres valeurs restent inchangées).
Notons que si \(k=1\), la liste n'est pas modifiée.
Exemple : Si la liste initiale est \((5 ; 29 ; 7 ; 14 ; 21 ; 10 ; \ldots\).) alors \(k=5\) (c'est le premier nombre de la liste) et on obtient donc après la première opération, la liste : ( \(21 ; 14 ; 7 ; 29 ; 5 ; 10 ; \ldots\) ).

Existe-t-il une liste initiale telle qu'après lui avoir appliqué l'opération quatre fois successivement, le nombre 1 apparaisse en première position (sans que 1 soit apparu plus tôt en première position) ?
Existe-t-il une liste initiale telle qu'après lui avoir appliqué l'opération dix-sept fois successivement, le nombre 1 apparaisse en première position (sans que 1 soit apparu plus tôt en première position) ?
Existe-t-il, pour tout entier naturel \(n\) tel que \(1 \leqslant n \leqslant 2012\), une liste initiale telle qu'après lui avoir appliqué l'opération \(n\) fois successivement, le nombre 1 apparaisse en première position (sans que 1 soit apparu plus tôt en première position)?
Pour toute liste initiale, existe-t-il nécessairement un entier naturel \(n\) tel qu'après avoir appliqué l'opération à la liste \(n\) fois successivement, le nombre 1 apparaisse en première position?

Pour tout \(k\) entier, on notera \(I_{k}\) la suite obtenue au bout de \(k\) opérations.

On prend la suite initiale \(I_{0}=\{2,3,4,5,1,5, \ldots 2012\}\).

Alors, \(I_{1}=\{3,2,4,5,1,3, \ldots 2012\}\)
\(I_{2}=\{4,2,3,5,1,6, \ldots 2012\}\)
\(I_{3}=\{5,3,2,4,1,6, \ldots 2012\}\)
\(I_{4}=\{1,4,2,3,5,6, \ldots 2012\}\)
2. On prend la suite initiale \(I_{0}=2,3, \ldots, 18,1,19, \ldots ; 2012\)

Alors, \(I_{1}=\{3,2,4, \ldots, 18,1,19, \ldots, 2012\}\)
\(I_{2}=\{4,2,3,5, \ldots, 18,1,19, \ldots, 2012\}\)
\(I_{3}=\{5,3,2,4,6, \ldots, 18,1,19, \ldots, 2012\}\)
⋯
\(I_{1} 6=\{18, \ldots, \ldots, 17,1,19, \ldots, 2012\}\)
\(I_{1} 7=\{1,17, \ldots, 18,19, \ldots, 2012\}\)
3. Soit \(n\) un entier naturel tel que \(1 \leqslant n \leqslant 2012\). On prend \(I_{0}=\{2,3, \ldots, \mathrm{n}+1,1, \mathrm{n}+2, \ldots, 2012\}\).

Alors, \(I_{n-1}=\{n+1, \ldots, n, 1, n+2, \ldots, 2012\}\)
\(I_{n}=\{1, n, \ldots, n+1, n, n+2, \ldots, 2012\}\).
Le nombre 1 ne peut pas apparaître plus tôt en première position puisque lors des \(n-1\) premières opérations, le nombre 1 reste toujours à la même position.
Il existe donc toujours une telle suite.