Olympiades · Épreuve nationale · 9 mars 2022
On part de 4. À chaque étape, on peut : multiplier par 3 ; ou multiplier par 3 puis ajouter 2 ; ou (si le nombre est pair) diviser par 2. Un nombre \(N\) est atteignable s'il apparaît dans une suite construite ainsi (ex. \(11\) est atteignable : \(4\to12\to6\to3\to3\times3+2=11\)).
1. Montrer que tous les entiers de 1 à 12 sont atteignables.
2. Montrer que 2022 est atteignable.
3. On suppose qu'il existe des entiers non atteignables ; soit \(m\) le plus petit.
a) Montrer que \(m\) n'est pas multiple de 3.
b) Montrer que \(m-2\) n'est pas multiple de 3.
c) Montrer que \(m-1\) n'est pas non plus multiple de 3.
d) Conclure.
1-2. Travailler « à l'envers » : partir du nombre cible et lui appliquer les opérations inverses (diviser par 3 si multiple de 3, ou soustraire 2 puis diviser par 3, ou multiplier par 2) jusqu'à atteindre 4.
3. Tout entier est multiple de 3, ou de la forme \(3k+1\), ou \(3k+2\). Pour chacun des trois cas, chercher comment l'atteindre à partir d'un nombre strictement plus petit (donc atteignable par minimalité de \(m\)) via l'une des trois opérations autorisées (ou leur inverse) — cela contredit la définition de \(m\) comme plus petit non-atteignable dans chacun des trois cas, épuisant ainsi toutes les possibilités.
1. Tous les entiers de 1 à 12 sont atteignables
Chemins explicites depuis 4 (chaque flèche : ×3, ×3+2, ou ÷2 si pair) :
• 1 : 4→2→1
• 2 : 4→2
• 3 : 4→12→6→3
• 5 : 4→2→1→5 (dernière étape ×3+2)
• 6 : 4→12→6
• 7 : 4→14→7 (première étape ×3+2)
• 8 : 4→2→8 (dernière étape ×3+2)
• 9 : 4→12→36→18→9
• 10 : 4→12→6→20→10 (étape ×3+2 puis ÷2)
• 11 : 4→14→44→22→11
• 12 : 4→12
2. 2022 est atteignable
Chemin explicite : 4→2→8→24→74→224→674→2022, où chaque étape est ÷2, ×3+2, ×3, ×3+2, ×3+2, ×3+2, ×3 respectivement. Vérification : 4÷2=2 ; 2×3+2=8 ; 8×3=24 ; 24×3+2=74 ; 74×3+2=224 ; 224×3+2=674 ; 674×3=2022.
3. Existence d'un plus petit non-atteignable m : contradiction
On suppose qu'il existe des entiers non atteignables, et on note m le plus petit.
a. m n'est pas multiple de 3. Si m=3q avec q b. m-2 n'est pas multiple de 3 (c'est-à-dire m n'est pas de la forme 3q+2). Si m=3q+2 avec q c. m-1 n'est pas multiple de 3 (c'est-à-dire \(m\not\equiv1\pmod3\)). Des deux points précédents, il reste à exclure \(m\equiv1\pmod3\). Posons \(n=\dfrac{2m-2}3\) : comme \(m\equiv1\pmod3\), \(2m-2\equiv0\pmod3\), donc \(n\) est un entier, et \(n d. Conclusion. Aucun des trois cas (m multiple de 3, m≡2 mod 3, m≡1 mod 3) ne peut correspondre à un plus petit entier non atteignable : l'hypothèse de départ est absurde. Tout entier naturel est donc atteignable.