Aller au contenu

Shortlist 2024, A8

Domaine : Algèbre · Difficulté : ★★★★★ · Proposé par : Japan

Concepts : Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences

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

Énoncé

Soient \(p \neq q\) des entiers strictement positifs premiers entre eux. Déterminer toutes les suites infinies \(a_1, a_2, \ldots\) d'entiers strictement positifs telles que, pour tout \(n \geq 1\),

\[\max(a_n, a_{n+1}, \ldots, a_{n+p}) - \min(a_n, a_{n+1}, \ldots, a_{n+p}) = p \quad \text{et}\]
\[\max(a_n, a_{n+1}, \ldots, a_{n+q}) - \min(a_n, a_{n+1}, \ldots, a_{n+q}) = q.\]
Énoncé original (anglais)

Let \(p \neq q\) be coprime positive integers. Determine all infinite sequences \(a_1, a_2, \ldots\) of positive integers such that the following conditions hold for all \(n \geq 1\):

\[\max(a_n, a_{n+1}, \ldots, a_{n+p}) - \min(a_n, a_{n+1}, \ldots, a_{n+p}) = p \quad \text{and}\]
\[\max(a_n, a_{n+1}, \ldots, a_{n+q}) - \min(a_n, a_{n+1}, \ldots, a_{n+q}) = q.\]
Indices : les idées clés
  • Principe extrémal : regarder le minimum \(b_n\) de la queue \((a_i)_{i \geq n}\) et le maximum \(c_n\) du début \((a_i)_{i \leq n}\) (solution 1), ou le plus petit entier « bon » (solution 2).
  • Lemme de Lipschitz : si \(|i - j| \leq mp\), alors \(|a_i - a_j| \leq mp\) ; une fenêtre de longueur \(q\) autour d'un minimum ne peut donc pas avoir une amplitude \(q\) si elle est trop « centrée ».
  • Divisibilité, PGCD : \(b_n - n\) (ou \(a_n - n\)) a pour périodes \(p\) et \(q - p\) (ou \(p\) et \(q\)), premiers entre eux, donc il est constant.
  • Somme d'inégalités saturée : si \(q - p\) accroissements, chacun \(\leq p\), ont pour somme \(p(q-p)\), ils valent tous \(p\).
  • Récurrence descendante pour étendre \(a_n = n + C\) de « \(n\) grand » à tous les \(n\).
Solutions

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

Réponse. Les suites cherchées sont exactement \(a_n = n + C\), où \(C\) est un entier positif ou nul.

Remarques communes du livret. On note \(a_{[i,j]}\) la suite finie \(a_i, a_{i+1}, \ldots, a_j\). Sans perte de généralité, on suppose \(p < q\) dans chaque solution (le cas \(p = 1\) peut être traité à part). Le problème peut aussi être posé pour des suites d'entiers relatifs quelconques (voir la remarque 3).

Solution 1

Posons \(k = \lceil q/p \rceil\) ; comme \(q > p\), on a \(k \geq 2\), et \((k-1)p < q \leq kp\).

Lemme 1. Si \(i, j, m\) sont des entiers strictement positifs avec \(|i - j| \leq mp\), alors \(|a_i - a_j| \leq mp\).

Preuve. Par hypothèse, si \(|i - j| \leq p\), alors \(|a_i - a_j| \leq p\) ; le lemme s'en déduit par récurrence sur \(m\) et l'inégalité triangulaire. \(\square\)

Lemme 2. Pour \(n\) fixé, si \(a_i\) est minimal parmi les \(a_j\), \(j \geq n\), alors \(i \leq n + p - 1\).

Preuve. Supposons \(i \geq n + p\). Alors \(\min(a_{[i-p,\, i+q-p]}) = a_i\). Chaque indice de cette fenêtre est à distance au plus \(\max(p, q - p) \leq (k-1)p\) de \(i\), donc d'après le lemme 1, \(\max(a_{[i-p,\, i+q-p]}) \leq a_i + (k-1)p < a_i + q\), ce qui contredit la seconde condition. \(\square\)

Lemme 3. Pour \(n > q\) fixé, si \(a_i\) est maximal parmi les \(a_j\), \(j \leq n\), alors \(i \geq n - p + 1\).

Preuve. Soit \(a_j\) minimal parmi les termes d'indice \(\geq n - q\). D'après le lemme 2, \(j \leq n - q + p - 1\), donc \(\min(a_{[n-q,\, n]}) = a_j\) et \(a_i \geq \max(a_{[n-q,\, n]}) = a_j + q\).

Le lemme 2 entraîne aussi que, pour tout \(m\), le minimum de la queue \((a_l)_{l \geq m}\) est atteint dans \([m, m+p-1]\), donc vaut au moins \(a_m - p\). Si l'on avait \(i < j\), on aurait donc \(a_j \geq a_i - p\), ce qui contredit \(a_i \geq a_j + q\). Ainsi \(i > j\).

L'inégalité \(a_i - a_j \geq q > (k-1)p\) et le lemme 1 donnent \(i - j > (k-1)p\), d'où

\[i \geq j + (k-1)p + 1 \geq n - q + kp - p + 1 \geq n - p + 1. \qquad \square\]

Les suites \(b\) et \(c\). Soit \(b_n = \min_{i \geq n} a_i\). D'après le lemme 2, \(b_{n+p} > b_n\) pour tout \(n\), donc

\[b_n = \min(a_{[n,\, n+p]}) = \min(a_{[n,\, n+q]}).\]

Soit \(c_n = \max_{i \leq n} a_i\). D'après le lemme 3, \(c_{n-p} < c_n\) pour tout \(n > q\) (le livret écrit \(c_{n-p} > c_n\), coquille), donc

\[c_n = \max(a_{[n-p,\, n]}) = \max(a_{[n-q,\, n]}) \quad \text{pour } n > q.\]

Pour \(n > q\), les deux conditions appliquées aux fenêtres \([n, n+p]\) et \([n, n+q]\) donnent donc \(b_n = c_{n+p} - p = c_{n+q} - q\). En remplaçant \(n\) par \(n + q - p\) dans la première égalité : \(b_{n+q-p} + p = c_{n+q} = b_n + q\), donc

\[b_{n+q-p} = b_n + (q - p) \quad \text{pour } n > q.\]

Les accroissements de pas \(p\). On a \(b_{n+p} \leq a_{n+p} \leq \max(a_{[n,\, n+p]}) = b_n + p\), donc \(b_{n+p} - b_n \leq p\) pour tout \(n > q\). En itérant \(q - p\) fois, \(b_{n + p(q-p)} - b_n \leq p(q-p)\). Mais en itérant \(p\) fois la relation \(b_{n+q-p} = b_n + (q-p)\), on obtient \(b_{n+p(q-p)} - b_n = p(q-p)\). Il y a donc égalité partout, et \(b_{n+p} = b_n + p\).

Conclusion pour \(n\) grand. Pour \(n > q\), on a \(b_{n+p} = b_n + p\) et \(b_{n+q-p} = b_n + (q - p)\). Comme \(p\) et \(q - p\) sont premiers entre eux, la suite \(b_n - n\) a pour périodes \(p\) et \(q - p\), donc pour période \(1\) : \(b_{n+1} = b_n + 1\) pour tout \(n > q\). Or \(b_n \neq b_{n+1}\) n'est possible que si \(b_n = a_n\) ; donc \(a_n = b_n\) et \(a_{n+1} = a_n + 1\) pour \(n > q\) : il existe une constante \(C\) telle que \(a_n = n + C\) pour tout \(n > q\).

Récurrence descendante. Supposons \(a_n = n + C\) pour tout \(n \geq N\), avec \(N \geq 2\). La fenêtre \([N-1, N-1+p]\) donne

\[p = \max(a_{N-1},\, N + C + p - 1) - \min(a_{N-1},\, N + C),\]

donc \(a_{N-1} = N + C + p\) ou \(a_{N-1} = N + C - 1\). De même, avec \(q\), \(a_{N-1} = N + C + q\) ou \(N + C - 1\). Comme \(p \neq q\), \(a_{N-1} = N + C - 1\). Par récurrence, \(a_n = n + C\) pour tout \(n \geq 1\), et \(a_1 \geq 1\) impose \(C \geq 0\).

Réciproquement, \(a_n = n + C\) vérifie trivialement les conditions. \(\blacksquare\)

Solution 2

Pour \(n, x \geq 1\), on appelle \(x\)-amplitude de \(n\) la quantité \(\max(a_{[n,\, n+x]}) - \min(a_{[n,\, n+x]})\). Un entier \(x \geq 1\) est dit bon si la \(x\)-amplitude de \(n\) est \(\leq x\) pour tout \(n\) assez grand, et très bon si elle est égale à \(x\) pour tout \(n\) assez grand. Ainsi \(p\) et \(q\) sont très bons.

Lemme 1. Si \(p'\) est bon, \(q'\) très bon et \(p' < q' < 2p'\), alors \(2p' - q'\) est bon.

Preuve. On a \(0 < q' - p' < p' < q'\). Soit \(n\) assez grand. Pour \(k \in [n + q' - p',\, n + p']\), l'indice \(k\) appartient aux fenêtres \([n, n+p']\) et \([n + q' - p', n + q']\) ; comme \(p'\) est bon, \(a_k \geq \max(a_{[n,\, n+p']}) - p'\) et \(a_k \geq \max(a_{[n+q'-p',\, n+q']}) - p'\). Ces deux fenêtres recouvrent \([n, n+q']\), donc \(a_k \geq \max(a_{[n,\, n+q']}) - p'\). De même, \(a_k \leq \min(a_{[n,\, n+q']}) + p'\). Ainsi la \((2p' - q')\)-amplitude de \(n + q' - p'\) est au plus

\[\big(\min(a_{[n,\, n+q']}) + p'\big) - \big(\max(a_{[n,\, n+q']}) - p'\big) = 2p' - q',\]

puisque la \(q'\)-amplitude de \(n\) vaut \(q'\). \(\square\)

Lemme 2. Soient \(p'\) bon et \(q'\) très bon avec \(p' < q'\). Pour \(n\) assez grand, soient \(s, t \in [n, n+q']\) tels que \(\min(a_{[n,\, n+q']}) = a_s\) et \(\max(a_{[n,\, n+q']}) = a_t\). Alors \(s \in [n, n+p']\) et \(t \in [n + q' - p', n + q']\).

Preuve. Les lemmes 2 et 3 de la solution 1 restent valables (pour \(n\) assez grand) en remplaçant \(p\) et \(q\) par \(p'\) et \(q'\), par des arguments analogues. L'assertion sur \(s\) découle du lemme 2 de la solution 1, celle sur \(t\) du lemme 3. \(\square\)

Lemme 3. Si \(p'\) est bon, \(q'\) très bon et \(2p' < q'\), il existe un entier \(r > 0\) tel que \(a_{n+r} - a_n \geq r\) pour tout \(n\) assez grand.

Preuve. Soit \(r = q' - 2p'\), et \(s, t\) comme dans le lemme 2. On a l'identité (avec \(n + p' + r = n + q' - p'\))

\[\big(a_t - a_{n+q'-p'}\big) + \big(a_{n+p'+r} - a_{n+p'}\big) + \big(a_{n+p'} - a_s\big) = a_t - a_s = q'.\]

D'après le lemme 2, \(s \in [n, n+p']\) et \(t \in [n + q' - p', n + q']\), donc, \(p'\) étant bon, \(a_{n+p'} - a_s \leq p'\) et \(a_t - a_{n+q'-p'} \leq p'\). On en déduit \(a_{n+p'+r} - a_{n+p'} \geq q' - 2p' = r\), ce qui prouve le lemme. \(\square\)

Lemme 4. Si \((p, q) \neq (1, 2)\), il existe un bon entier \(p'\) tel que \(2p' < q\).

Preuve. Soit \(p'\) le plus petit bon entier (principe extrémal) ; il existe car \(p\) est bon, et \(p' \leq p < q\). Supposons par l'absurde \(2p' \geq q\). Si \(2p' > q\), le lemme 1 (avec \(q' = q\)) montre que \(2p' - q\) est un bon entier strictement inférieur à \(p'\) : contradiction. Si \(2p' = q\), alors \(p' < p < 2p'\) (on ne peut pas avoir \(p' = p\), sinon \(q = 2p\) avec \(p, q\) premiers entre eux, soit \((p, q) = (1, 2)\)) ; le lemme 1 avec \(q' = p\) montre que \(2p' - p\) est un bon entier strictement inférieur à \(p'\) : contradiction. \(\square\)

Conclusion. Le livret indique que le cas \((p, q) = (1, 2)\) se résout facilement. (Précision ajoutée : dans ce cas \(|a_{n+1} - a_n| = 1\), et une fenêtre de trois termes d'amplitude \(2\) impose \(a_{n+2} - a_{n+1} = a_{n+1} - a_n\) ; la suite est donc \(n + C\) ou \(-n + C\), et la seconde forme est exclue pour une suite d'entiers strictement positifs.) Sinon, les lemmes 3 et 4 donnent un \(r > 0\) tel que \(a_{n+r} - a_n \geq r\) pour tout \(n\) assez grand. En itérant, \(a_{n+pr} - a_n \geq pr\). Or \(a_{n+pr} - a_n\) est la somme des \(r\) accroissements \(a_{n+(j+1)p} - a_{n+jp}\), chacun \(\leq p\) ; ils valent donc tous \(p\), et \(a_{n+p} - a_n = p\) pour tout \(n\) assez grand. De même, \(a_{n+q} - a_n = q\). Comme \(p\) et \(q\) sont premiers entre eux, \(a_{n+1} - a_n = 1\) pour \(n\) assez grand, donc \(a_n = n + C\) pour \(n\) assez grand, et l'on conclut par la même récurrence descendante que dans la solution 1. \(\blacksquare\)

Remarques

Remarque 1 (variante de la solution 1). On procède jusqu'à montrer que \(b_n - n\) est périodique de période \(q - p\) à partir d'un certain rang. Cette suite atteint alors un minimum ; si \(n\) l'atteint, comme \(b_{n+p} - (n+p) \leq b_n - n\), l'indice \(n + p\) l'atteint aussi. Comme \(p\) et \(q - p\) sont premiers entre eux, tous les \(n \geq q\) l'atteignent, donc \(b_{n+1} = b_n + 1\) pour \(n \geq q\), et l'on termine comme ci-dessus.

Remarque 2. On peut aussi résoudre le problème avec une version plus faible du lemme 2 et sans le lemme 3 ; par exemple, le lemme suivant joue un rôle similaire. Lemme 2' : si \(b'_n = \min(a_{[n,\, n+p]})\), alors \(b'_n < b'_{n+p}\).

Remarque 3 (suites d'entiers relatifs). Pour des suites d'entiers quelconques, on utilise le lemme suivant. Lemme 4 : la suite \((a_n)\) est majorée ou minorée. En effet, supposons-la ni majorée ni minorée. Il existe \(i\) avec \(a_i < a_1 - p\), puis \(j\) avec \(a_j > \max(a_{[1,\, i]}) + q\). Soit \(a_l\) minimal parmi \(a_{[1,\, j]}\) ; alors \(a_l \leq a_i < a_1 - p\) et \(a_l < a_j - q\). Par le lemme 1, \(l > 1 + p\) et \(j - l > (k-1)p \geq q - p\). Donc \([l - p, l + q - p] \subset [1, j]\) et \(\min(a_{[l-p,\, l+q-p]}) = a_l\), alors que, toujours par le lemme 1, \(\max(a_{[l-p,\, l+q-p]}) \leq a_l + (k-1)p < a_l + q\) : contradiction. (Le livret écrit \(a_l < a_j - kp\) et \(l < j - kp\) ; les inégalités ci-dessus sont celles qui découlent réellement des hypothèses et suffisent.) On adapte ensuite la solution 1 pour montrer que \(a_n = n + C\) pour tout \(n\), ou \(a_n = -n + C\) pour tout \(n\), avec \(C\) entier quelconque.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2016 C2 ★☆☆☆☆ : Pour quels \(n\) peut-on ranger tous les diviseurs dans un tableau dont les lignes ont même somme et les colonnes aussi ?
  • 2007 A1 ★★☆☆☆ · OIM P1 : Approcher une suite quelconque par une suite croissante : l'écart minimal vaut exactement \(d/2\).
  • 2023 N5 ★★★☆☆ : Une suite croissante dont chaque terme divise le double de la somme des précédents : si elle fait intervenir une infinité de premiers, tout entier divise l'un de ses termes.
  • 2021 N7 ★★★★☆ : Si \(a_{n+2m}\) divise \(a_n + a_{n+m}\), la suite finit par être périodique.