Exercice 3 — Énoncé — Olympiades 2010 Versailles

Sujet

Retour à Syracuse

Une rangée de cases supposée illimitée est numérotée par les nombres entiers successifs, en commençant par 1. Un pion peut se déplacer d'une case à l'autre en utilisant les seuls mouvements autorisés:

aller de la case numérotée \(n\) à la case numérotée \(2 n\);
aller de la case numérotée \(2 n\) à la case numérotée \(n\);
aller de la case numérotée \(n\) à la case numérotée \(3 n+1\);
aller de la case numérotée \(3 n+1\) à la case numérotée \(n\).

Montrer qu'un pion peut aller de la case 56 à la case 1 en un nombre fini d'étapes.
Montrer qu'un pion peut aller de la case 29 à la case 1 en un nombre fini d'étapes.
Montrer qu'un pion peut aller d'une case numérotée \(3 m+2\) à la case numérotée \(2 m+1\) en deux étapes.
Montrer qu'un pion peut aller d'une case numérotée \(3 m\) à la case numérotée \(2 m\), en passant par la case numérotée \(36 m+4\), en quelques étapes.
Peut-on, à partir de n'importe quelle case, rejoindre la case 1 ?

Voici des étapes possibles : 56-28 - 14-7-2 - 1 .
Voici des étapes possibles : 29-58 - 19-6-3-10-5-16-8 - 4-2 - 1 .
Voici deux étapes : on va de \(3 m+2\) à \(6 m+4\). Comme \(6 m+4=3(2 m+1)+1\), on peut aller à \(2 m+1\).
Voici des étapes possibles : on va de \(3 m\) à \(9 m+1\), de \(9 m+1\) à \(18 m+2\) puis à \(36 m+4\). Comme \(36 m+4=3(12 m+1)+1\), on peut aller à \(12 m+1\), puis à \(4 m\) et \(2 m\).
Pour tout entier naturel \(n\) strictement supérieur à 2, il existe un entier naturel \(m\) supérieur ou égal à 1 tel que \(n=3 m, n=3 m+1\) ou \(n=3 m+2\). L'hypothèse, jointe aux résultats démontrés précédemment, montre qu'on peut aller de toute case portant un numéro supérieur ou égal à 3 à une case portant un numéro inférieur strictement. En poursuivant cette descente, on parvient à 1 ou 2 , mais de 2 on peut aller à 1 . Donc on peut parvenir à 1 .