Exercice 1

Sujet

Les questions 1 à 5 sont à traiter par tous les candidats La question 6 ne sera traitée que par les élèves inscrits dans la série S

On part d'un entier \(n\) strictement positif :

• Si \(n\) est pair, on le transforme en \(\frac{n}{2}\).
• Si \(n\) est impair \((n>1)\), on le transforme en \(3 n+1\).
• Si \(n=1\), on s'arrête.

Exemples :

• Si \(n=6\), on obtient la suite : \(6 \rightarrow 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 9 \rightarrow 4 \rightarrow 2 \rightarrow 1\).
• Si \(n=13\), on obtient la suite : \(13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\).

Il a été observé à l'aide d'un programme sur ordinateur, que pour chaque nombre testé, la suite aboutit toujours à 1 . Mais ce résultat n'a pas été démontré à ce jour.
On peut par ailleurs, s'intéresser à la longueur de cette suite, qu'on notera \(L(n)\).
Par exemple : \(L(6)=9\) et \(L(13)=10\).

A traiter par tous les candidats

1. Déterminer \(L(n)\) pour les entiers allant de 1 à 12 .
2. Soit \(p\) un entier, on considère l'entier \(n=2^{p}\).

Exprimer \(L(n)\) en fonction de \(p\).
3. Trouver un nombre \(n\) compris entre \(2^{2008}\) et \(2^{2009}\).

Indication : On pourra chercher un nombre de la forme \(2^{p} \times q\).
4. Soit \(k\) un entier non nul
a) Montrer que \(L(8 k+4)=L(6 k+4)+3\).
b) De même, montrer que \(L(8 k+5)=L(6 k+4)+3\).
c) Montrer que \(L(16 k+2)=L(16 k+3)\).
5. A défaut de réussir à prouver que la suite aboutit toujours à 1 , on souhaite montrer que dans un grand nombre de cas, on est sûr d'aboutir à un moment à un entier inférieur à \(n\).
Par exemple : \(51 \rightarrow 154 \rightarrow 77 \rightarrow 232 \rightarrow 116 \rightarrow 58 \rightarrow 26 \ldots\)
Montrer que dans les cas suivants, où \(k\) est un entier, on aboutit bien à un moment à un nombre plus petit que celui de départ :
a) \(n=4 k\)
b) \(n=4 k+1\).
c) \(n=4 k+2\).

Quel problème rencontre-t-on pour \(n=4 k+37\) ?

A traiter par les élèves de la série \(S\) uniquement :

1. Écrire un algorithme en pseudo-langage permettant, pour un entier \(n\) quelconque, de déterminer si la longueur \(L(n)\) est inférieure ou égale à 100 et, dans ce cas, d'afficher \(L(n)\).