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)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
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\):
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ù
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
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
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
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
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
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'\))
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.