Aller au contenu

Shortlist 2024, A6

Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Czech Republic

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Invariants et monovariants

Solution officielle : Shortlist officielle 2024 (avec solutions), section A6 (livret PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(a_0, a_1, a_2, \ldots\) be an infinite strictly increasing sequence of positive integers such that for each \(n \geq 1\) we have

\[a_n \in \left\{\frac{a_{n-1} + a_{n+1}}{2},\ \sqrt{a_{n-1} \cdot a_{n+1}}\right\}.\]

Let \(b_1, b_2, \ldots\) be an infinite sequence of letters defined as

\[b_n = \begin{cases} A, & \text{if } a_n = \frac{1}{2}(a_{n-1} + a_{n+1}); \\ G, & \text{otherwise.} \end{cases}\]

Prove that there exist positive integers \(n_0\) and \(d\) such that for all \(n \geq n_0\) we have \(b_{n+d} = b_n\).

Indices : les idées clés
  • Regarder les quotients \(a_n / a_{n-1}\) : une lettre G conserve le quotient, une lettre A le fait passer de \(\frac{C + kD}{C + (k-1)D}\) à \(\frac{C + (k+1)D}{C + kD}\) ; les quotients successifs suivent une progression arithmétique.
  • Divisibilité, PGCD : deux termes consécutifs \(C + qD\) et \(C + (q+1)D\) (ou \(p_i\) et \(p_{i+1}\)) sont premiers entre eux, ce qui force certaines quantités rationnelles à être entières.
  • Monovariant : une suite d'entiers positifs décroissante (au sens large) est stationnaire ; on l'applique à \(s^{(T')}_q\) (solution 1) et à \(u_{r_i}\) (solution 2).
  • Comparer le nombre de G entre deux A à un seuil \(t\) (solution 1) : le signe de \(m_{q+1} - m_q - t\) dit si \(s^{(t)}_q\) monte ou descend.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (deux solutions et une remarque).

Remarques communes du livret. Toutes les preuves connues montrent en fait que la période finale de \((b_n)\) est formée d'un certain nombre (éventuellement nul) de lettres G suivi d'un A. De telles suites existent pour toute période \(p \geq 1\) : par exemple

\[\ldots,\ k^p,\ k^{p-1}(k+1),\ \ldots,\ k(k+1)^{p-1},\ (k+1)^p,\ (k+1)^{p-1}(k+2),\ \ldots\]

Le Tournoi des Villes (printemps 2009, niveau junior A, problème 4) étudiait déjà ces suites, mais demandait seulement si \((b_n)\) est toujours constante à partir d'un certain rang ; la réponse est non, comme le suggère le présent énoncé.

Solution 1

On montre que la période finale de \((b_n)\) est formée d'un nombre fixé de G (éventuellement zéro) suivi d'un seul A.

Les quotients. Soient \(C\) et \(D\) des entiers strictement positifs premiers entre eux tels que \(\frac{a_1}{a_0} = \frac{C + D}{C}\). Si \(b_n = G\), alors \(\frac{a_n}{a_{n-1}} = \frac{a_{n+1}}{a_n}\). Si \(b_n = A\) et \(\frac{a_n}{a_{n-1}} = \frac{C + kD}{C + (k-1)D}\) pour un entier \(k \geq 1\), alors

\[\frac{a_{n+1}}{a_n} = \frac{2a_n - a_{n-1}}{a_n} = 2 - \frac{C + (k-1)D}{C + kD} = \frac{C + (k+1)D}{C + kD}.\]

Par récurrence, il existe donc une suite d'entiers \((k_n)_{n \geq 1}\) telle que

\[\frac{a_n}{a_{n-1}} = \frac{C + k_n D}{C + (k_n - 1)D} \quad \text{pour tout } n \geq 1, \qquad k_1 = 1, \qquad k_{n+1} = \begin{cases} k_n & \text{si } b_n = G, \\ k_n + 1 & \text{si } b_n = A. \end{cases}\]

S'il n'y a qu'un nombre fini de \(n\) avec \(b_n = A\), l'énoncé est évident (\(d = 1\)). On suppose donc \(b_n = A\) pour une infinité de \(n\) : la suite \((k_n)\) prend alors toutes les valeurs entières \(\geq 1\). Pour \(q \geq 1\), notons \(m_q\) le dernier indice où la valeur \(q\) est prise, c'est-à-dire l'indice tel que \(k_{m_q} = q\) et \(k_{m_q + 1} = q + 1\). Ainsi \(b_n = A\) si et seulement si \(n\) est l'un des \(m_q\), et il suffit de montrer que la suite des écarts \((m_{q+1} - m_q)\) est constante à partir d'un certain rang.

La suite \(s^{(t)}\). Fixons \(t \geq 1\) et posons, pour \(q \geq 1\),

\[s^{(t)}_q = \frac{a_{m_q}}{(C + qD)^t}.\]

Première propriété. Entre les indices \(m_q\) et \(m_{q+1}\), tous les quotients valent \(\frac{C + (q+1)D}{C + qD}\), donc

\[s^{(t)}_{q+1} = \frac{a_{m_q}}{(C + (q+1)D)^t} \left( \frac{C + (q+1)D}{C + qD} \right)^{m_{q+1} - m_q} = s^{(t)}_q \left( \frac{C + (q+1)D}{C + qD} \right)^{m_{q+1} - m_q - t}.\]

Par conséquent \(s^{(t)}_q >, =, < s^{(t)}_{q+1}\) selon que \(m_{q+1} - m_q <, =, > t\).

Seconde propriété. Si \(m_{q+1} - m_q \geq t\), alors \(s^{(t)}_q\) est un entier strictement positif. En effet, \(k_{m_q + 1} = \cdots = k_{m_q + t} = q + 1\), donc

\[a_{m_q + t} = a_{m_q} \left( \frac{C + (q+1)D}{C + qD} \right)^t\]

est un entier ; comme \(C + (q+1)D\) et \(C + qD\) sont premiers entre eux (leur PGCD divise \(D\) et \(C\)), \((C + qD)^t\) divise \(a_{m_q}\).

Majoration des écarts. Choisissons \(T \geq 1\) tel que \(s^{(T)}_1 < 1\) (possible car \(C + D > 1\)). Par récurrence, \(s^{(T)}_q < 1\) pour tout \(q\) : si \(s^{(T)}_q < 1\), ce n'est pas un entier strictement positif, donc \(m_{q+1} - m_q < T\) par la seconde propriété, puis \(s^{(T)}_{q+1} < s^{(T)}_q < 1\) par la première. Ainsi \(m_{q+1} - m_q < T\) pour tout \(q\).

Conclusion. Il existe donc un plus grand entier \(T' \leq T\) tel que l'égalité \(m_{q+1} - m_q = T'\) ait lieu pour une infinité de \(q\). Pour \(q\) assez grand, \(m_{q+1} - m_q \leq T'\), donc, par la première propriété, la suite \(s^{(T')}\) est décroissante (au sens large) à partir d'un certain rang. De plus, par la seconde propriété, elle prend une infinité de valeurs entières strictement positives (pour chaque \(q\) tel que \(m_{q+1} - m_q = T'\)). Une suite décroissante qui prend une infinité de valeurs entières positives est constante à partir d'un certain rang \(Q\) (monovariant). Par la première propriété, \(m_{q+1} - m_q = T'\) pour tout \(q \geq Q\). Comme \(b_n = A\) exactement lorsque \(n\) est l'un des \(m_q\), la suite \((b_n)\) est périodique de période \(T'\) à partir du rang \(m_Q\). \(\blacksquare\)

Solution 2

Si \(b_n = G\) pour tout \(n\), il n'y a rien à montrer. Sinon, il existe \(n\) avec \(b_n = A\) ; quitte à décaler la suite, on peut supposer \(b_1 = A\).

Notations. Soit \(g = \operatorname{pgcd}(a_0, a_1)\). On définit la progression arithmétique \((p_n)\) par \(p_0 = a_0 / g\) et \(p_1 = a_1 / g\). Comme \(p_0 < p_1\), c'est une suite croissante d'entiers strictement positifs, et \(p_2 = a_2 / g\) (car \(a_2 = 2a_1 - a_0\)). On pose aussi \(d_n = a_n - a_{n-1}\) (entiers strictement positifs) et \(q_n = a_n / a_{n-1}\) (rationnels strictement positifs). Les définitions donnent immédiatement :

  • si \(b_n = G\), alors \(q_{n+1} = q_n\) et \(d_{n+1} = d_n q_n\) ;
  • si \(b_n = A\), alors \(d_{n+1} = d_n\) ;
  • \(q_1 = p_1 / p_0\) ;
  • si \(b_n = A\) et \(q_n = p_i / p_{i-1}\), alors \(q_{n+1} = p_{i+1} / p_i\).

Soit \(k_i\) le nombre d'entiers \(n\) tels que \(b_n = G\) et \(q_n = p_i / p_{i-1}\). Si l'un des \(k_i\) est infini, \((b_n)\) vaut G à partir d'un certain rang ; sinon tous les \(k_i\) sont des entiers positifs ou nuls. Les valeurs successives de \(d_n\) sont alors (en notant \(d_0\) la première d'entre elles)

\[d_0,\ d_0 \frac{p_1}{p_0},\ \ldots,\ d_0 \left(\frac{p_1}{p_0}\right)^{k_1},\ d_0 \left(\frac{p_1}{p_0}\right)^{k_1} \frac{p_2}{p_1},\ \ldots,\ d_0 \left(\frac{p_1}{p_0}\right)^{k_1} \left(\frac{p_2}{p_1}\right)^{k_2},\ \ldots\]

et ce sont tous des entiers strictement positifs. Posons

\[u_1 = d_0\, p_0^{-k_1}, \qquad u_{r+1} = u_r\, p_r^{\,k_r - k_{r+1}}, \quad \text{c'est-à-dire} \quad u_r = d_0\, p_0^{-k_1} p_1^{k_1 - k_2} \cdots p_{r-1}^{k_{r-1} - k_r}.\]

Ce sont des entiers strictement positifs : la valeur \(X = u_r\, p_{r-1}^{k_r}\) apparaît dans la liste ci-dessus, ainsi que \(X (p_r / p_{r-1})^{k_r}\), donc \(p_{r-1}^{k_r}\) divise \(X p_r^{k_r}\), et comme \(p_{r-1}\) et \(p_r\) sont premiers entre eux (deux termes consécutifs d'une progression arithmétique de raison \(p_1 - p_0\), avec \(\operatorname{pgcd}(p_0, p_1) = 1\)), \(p_{r-1}^{k_r}\) divise \(X\), c'est-à-dire que \(u_r\) est entier.

Le livret note \(u_0 = d_0 p_0^{-k_1}\), \(u_1 = d_0 p_0^{-k_1} p_1^{k_1 - k_2}, \ldots\) mais utilise ensuite la relation \(u_{r+1} = u_r p_r^{k_r - k_{r+1}}\) ; on a décalé les indices d'un rang pour que les formules soient cohérentes.

Il suffit de montrer que \((k_i)\) est constante à partir d'un certain rang, égale à \(k\) : la période finale de \((b_n)\) est alors formée de \(k\) lettres G suivies d'un A.

Une sous-suite d'indices. Ou bien \((k_i)\) n'est pas bornée, et l'on pose \(r_0 = 1\) ; ou bien elle est bornée, de plus grande valeur prise une infinité de fois égale à \(k\), et l'on choisit \(r_0\) tel que \(k_{r_0} = k\) et \(k_j \leq k\) pour tout \(j \geq r_0\) (précision ajoutée : le livret dit « \(r_0\) minimal tel que \(k_{r_0} = k\) » ; il faut aussi que \(k_j \leq k\) au-delà de \(r_0\)). On construit ensuite :

  • si \(k_{r_i + 1} \geq k_{r_i}\), alors \(r_{i+1} = r_i + 1\) ;
  • si \(k_{r_i + 1} < k_{r_i}\), alors \(r_{i+1}\) est le plus petit entier \(> r_i\) tel que \(k_{r_{i+1}} \geq k_{r_i}\) (il existe grâce au choix de \(r_0\)).

Affirmation. \(u_{r_{i+1}} \leq u_{r_i}\), avec égalité seulement si \(k_{r_{i+1}} = k_{r_i}\) et \(r_{i+1} = r_i + 1\).

Preuve. Notons \(r = r_i\) et \(R = r_{i+1}\). Si \(k_{r+1} \geq k_r\), alors \(u_R = u_{r+1} = u_r\, p_r^{k_r - k_{r+1}} \leq u_r\), avec égalité si et seulement si \(k_r = k_{r+1}\). Sinon,

\[\frac{u_R}{u_r} = p_r^{k_r - k_{r+1}}\, p_{r+1}^{k_{r+1} - k_{r+2}} \cdots p_{R-1}^{k_{R-1} - k_R},\]

et il suffit de montrer que ce produit est strictement inférieur à \(1\). Or, comme \(p_j < p_{j+1}\) et \(k_r > k_j\) pour \(r < j < R\),

\[\begin{aligned} p_r^{k_r - k_{r+1}}\, p_{r+1}^{k_{r+1} - k_{r+2}} \cdots p_{R-1}^{k_{R-1} - k_R} &< p_{r+1}^{k_r - k_{r+2}}\, p_{r+2}^{k_{r+2} - k_{r+3}} \cdots p_{R-1}^{k_{R-1} - k_R} \\ &< p_{r+2}^{k_r - k_{r+3}}\, p_{r+3}^{k_{r+3} - k_{r+4}} \cdots p_{R-1}^{k_{R-1} - k_R} \\ &\;\;\vdots \\ &< p_{R-1}^{k_r - k_R} \leq 1, \end{aligned}\]

la dernière inégalité venant de \(k_r \leq k_R\). \(\square\)

Conclusion. La suite \((u_{r_i})\) est une suite décroissante (au sens large) d'entiers strictement positifs, donc constante à partir d'un certain rang (monovariant). D'après l'affirmation, on a alors \(r_{i+1} = r_i + 1\) et \(k_{r_{i+1}} = k_{r_i}\) pour tout \(i\) assez grand : la suite \((k_j)\) est constante à partir d'un certain rang, ce qui conclut. \(\blacksquare\)

Remarques

Remarque 1. Les deux solutions ont des approches différentes mais révèlent la même structure : le \(C + nD\) de la solution 1 est le \(p_n\) de la solution 2, et l'écart \(m_{r+1} - m_r\) de la solution 1 est égal au \(k_r\) de la solution 2.