Aller au contenu

Shortlist 2025, N5

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : India

Concepts : Invariants et monovariants · Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2025 (avec solutions), section N5 (livret PDF)

Énoncé

The sequence of triples of positive integers \((a_0, b_0, c_0), (a_1, b_1, c_1), \ldots, (a_{2025}, b_{2025}, c_{2025})\) satisfies

\[(a_{i+1}, b_{i+1}, c_{i+1}) = \big(a_i + \gcd(b_i, c_i),\ b_i + \gcd(c_i, a_i),\ c_i + \gcd(a_i, b_i)\big)\]

for \(0 \leq i \leq 2024\).

Determine the smallest possible value of \(a_{2025}\).

Here \(\gcd(x, y)\) denotes the greatest common divisor of integers \(x\) and \(y\).

Indices : les idées clés
  • Homogénéité : \(F(ka, kb, kc) = kF(a, b, c)\), car \(\gcd(kb, kc) = k\gcd(b, c)\).
  • Invariants et monovariants : selon le nombre de termes pairs du triplet, le triplet devient entièrement pair au bout d'au plus trois étapes ; la valuation \(w_i\) croît d'au moins \(1\) toutes les trois étapes.
  • Valuations p-adiques : \(w_i = \nu_2(\gcd(a_i, b_i, c_i))\) et \(2^{w_{2025}} \mid a_{2025}\).
  • Divisibilité et PGCD : \(\gcd(b_i, c_i) \geq \gcd(a_i, b_i, c_i) \geq 2^{w_i}\) minore chaque accroissement \(a_{i+1} - a_i\) ; on somme ces minorations.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2025 (une solution et une remarque).

Réponse : la plus petite valeur possible de \(a_{2025}\) est \(3 \cdot 2^{2025/3} = 3 \cdot 2^{675}\).

Solution

Construction. Prenons \((a_0, b_0, c_0) = (3, 5, 6)\). Une récurrence immédiate montre que, pour tout entier \(0 \leq k \leq 674\),

\[\begin{aligned} (a_{3k}, b_{3k}, c_{3k}) &= (3 \cdot 2^k,\ 5 \cdot 2^k,\ 6 \cdot 2^k), \\ (a_{3k+1}, b_{3k+1}, c_{3k+1}) &= (4 \cdot 2^k,\ 8 \cdot 2^k,\ 7 \cdot 2^k), \\ (a_{3k+2}, b_{3k+2}, c_{3k+2}) &= (5 \cdot 2^k,\ 9 \cdot 2^k,\ 11 \cdot 2^k), \end{aligned}\]

de sorte que \(a_{2025} = 3 \cdot 2^{675}\). Il reste à montrer que tout triplet initial donne \(a_{2025} \geq 3 \cdot 2^{675}\).

Notations. Pour des entiers strictement positifs \(a, b, c\), posons

\[f(a, b, c) = a + \gcd(b, c) \quad \text{et} \quad F(a, b, c) = \big(f(a, b, c),\ f(b, c, a),\ f(c, a, b)\big),\]

de sorte que \((a_{i+1}, b_{i+1}, c_{i+1}) = F(a_i, b_i, c_i)\) pour \(0 \leq i \leq 2024\).

Pour tous entiers strictement positifs \(b, c, k\), on a \(\gcd(kb, kc) = k \gcd(b, c)\). Donc \(f(ka, kb, kc) = kf(a, b, c)\) et \(F(ka, kb, kc) = kF(a, b, c)\).

Parité. Disons qu'un triplet d'entiers strictement positifs est \(m\)-pair s'il contient exactement \(m\) nombres pairs. Comme \(F(2a, 2b, 2c) = 2F(a, b, c)\), si \((a, b, c)\) est \(3\)-pair, alors \(F(a, b, c)\) l'est aussi. On vérifie aussi directement que :

  • si \((a, b, c)\) est \(0\)-pair, alors \(F(a, b, c)\) est \(3\)-pair ;
  • si \((a, b, c)\) est \(1\)-pair, alors \(F(a, b, c)\) est \(2\)-pair ;
  • si \((a, b, c)\) est \(2\)-pair, alors \(F(a, b, c)\) est \(0\)-pair.

Ainsi, pour tous \(a, b, c\), le triplet \(F^{(3)}(a, b, c) = F(F(F(a, b, c)))\) est \(3\)-pair (invariant de parité).

Une valuation qui croît. Soit \(w_i\) le plus grand entier \(n\) tel que \(2^n \mid \gcd(a_i, b_i, c_i)\), c'est-à-dire \(w_i = \nu_2(\gcd(a_i, b_i, c_i))\) (valuation 2-adique). En particulier \(\gcd(a_i, b_i, c_i) \geq 2^{w_i}\). Écrivons \((a_i, b_i, c_i) = 2^{w_i}(a_i', b_i', c_i')\) avec \(a_i', b_i', c_i'\) entiers strictement positifs. Alors \((a_{i+1}, b_{i+1}, c_{i+1}) = 2^{w_i} F(a_i', b_i', c_i')\), donc \(w_{i+1} \geq w_i\) pour tout \(i\). De plus \(w_{i+3} > w_i\), car \((a_{i+3}, b_{i+3}, c_{i+3}) = 2^{w_i} F^{(3)}(a_i', b_i', c_i')\) et \(F^{(3)}(a_i', b_i', c_i')\) est \(3\)-pair.

Comme \(w_{i+1} \geq w_i\), \(w_{i+3} > w_i\) et \(w_0 \geq 0\), les entiers \(w_0, w_1, w_2\) sont au moins \(0\), puis \(w_3, w_4, w_5\) au moins \(1\), et en général \(w_{3k}, w_{3k+1}, w_{3k+2}\) sont tous au moins \(k\).

Minoration. On a alors

\[\begin{aligned} a_{2025} &= a_0 + \sum_{i=0}^{2024} \gcd(b_i, c_i) \geq a_0 + \sum_{i=0}^{2024} \gcd(a_i, b_i, c_i) \geq a_0 + \sum_{i=0}^{2024} 2^{w_i} \\ &= a_0 + \sum_{k=0}^{674} \left(2^{w_{3k}} + 2^{w_{3k+1}} + 2^{w_{3k+2}}\right) \geq a_0 + \sum_{k=0}^{674} 3 \cdot 2^k = a_0 + 3\left(2^{675} - 1\right). \end{aligned}\]

Comme \(2^{w_{2025}} \mid a_{2025}\) et \(w_{2025} \geq 675\), on a \(2^{675} \mid a_{2025}\). Avec \(a_{2025} \geq a_0 + 3 \cdot 2^{675} - 3 > 2 \cdot 2^{675}\), cela donne \(a_{2025} \geq 3 \cdot 2^{675}\), comme annoncé. \(\blacksquare\)

Remarques

Remarque 1 (trouver la construction). La minoration aide à deviner la construction : on veut que \(a_0 = 3\) soit le plus petit terme, avec exactement un nombre pair parmi \(b_0\) et \(c_0\). Le triplet de départ \((3, 4, 9)\) convient aussi.