Shortlist 2022, A8¶

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

Concepts : Suites et récurrences · Principe des tiroirs · Bijections et dénombrement

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 21 (page 23 du PDF)

Pas encore relu

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

Énoncé¶

For a positive integer \(n\), an \(n\)-sequence is a sequence \((a_0, \ldots, a_n)\) of non-negative integers satisfying the following condition: if \(i\) and \(j\) are non-negative integers with \(i + j \leq n\), then \(a_i + a_j \leq n\) and \(a_{a_i + a_j} = a_{i+j}\).

Let \(f(n)\) be the number of \(n\)-sequences. Prove that there exist positive real numbers \(c_1\), \(c_2\) and \(\lambda\) such that

\[c_1 \lambda^n < f(n) < c_2 \lambda^n\]

for all positive integers \(n\).

Indices : les idées clés

Classifier complètement les \(n\)-suites, puis les compter : la réponse est \(\lambda = 3^{1/6}\).
Suites et récurrences : \(a_{r+1} = a_{a_r + a_1}\) ne dépend que de \(a_r\), donc dès qu'une valeur se répète la suite devient périodique (période \(d\), décalage \(r\)).
Principe des tiroirs : une suite « petite » prend \(k+2\) valeurs \(a_0, \ldots, a_{k+1}\) dans \(\{0, \ldots, k\}\), donc répète une valeur tôt (lemme 7).
Bijections et dénombrement : chaque classe de suites se compte par un produit \(g(x, d) = (p+1)^q p^{d-q}\), nombre de choix d'une période.
Produit maximal à somme fixée : \(g(x,d)\) est le plus grand produit de \(d\) entiers de somme \(x\), et il est d'ordre \(3^{x/3}\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2022 (une solution, accompagnée de remarques communes).

Remarques communes du livret. La meilleure valeur possible de \(c_1\) est contrainte par \(n = 1\) : comme \(f(1) = 2\), il faut \(c_1 < 2 \cdot 3^{-1/6} \approx 1{,}66537\) (le livret écrit \(c_1 > 2 \cdot 3^{-1/6}\) ; il faut lire \(c_1 < 2 \cdot 3^{-1/6}\), puisque \(c_1 \lambda < f(1) = 2\)). Une analyse fine montre que la meilleure valeur de \(c_2\) est \(\frac{236567}{4930} \cdot 3^{1/3} \approx 69{,}20662\).

Réponse : de telles constantes existent avec \(\lambda = 3^{1/6}\).

Solution¶

On va classifier complètement les \(n\)-suites. Soit \(k = \lfloor n/2 \rfloor\). Une \(n\)-suite est dite grande si \(a_i > k\) pour un certain \(i\), et petite sinon. Pour l'instant, on suppose que \((a_i)\) n'est pas la suite identité (il existe \(i\) avec \(a_i \neq i\)).

Lemme 1. Si \(a_r = a_s\) avec \(r, s < n\), alors \(a_{r+1} = a_{s+1}\).

Preuve. \(a_{r+1} = a_{a_r + a_1} = a_{a_s + a_1} = a_{s+1}\).

Lemme 2. Si \(i \leq k\), alors \(a_i \leq k\).

Preuve. \(i + i \leq n\), donc \(a_i + a_i \leq n\), d'où \(a_i \leq k\).

Lemme 3. Il existe \(r \neq s\) tels que \(a_r = a_s\).

Preuve. Si \(a_0 \neq 0\), alors \(a_{2a_0} = a_{a_0 + a_0} = a_0\) avec \(2a_0 \neq 0\). Sinon, \(a_{a_i} = a_{a_i + a_0} = a_i\) pour tout \(i\) ; on prend \(i\) tel que \(a_i \neq i\), et alors \(a_{a_i} = a_i\).

Lemme 4. Soit \(r\) le plus petit indice tel que \(a_s = a_r\) pour un certain \(s > r\), et soit \(d\) le plus petit entier \(d \geq 1\) tel que \(a_{r+d} = a_r\). Alors :

la suite \((a_r, a_{r+1}, \ldots, a_n)\) est périodique de période minimale \(d\) ; plus précisément, pour \(u < v\), on a \(a_u = a_v\) si et seulement si \(u, v \geq r\) et \(d \mid v - u\) ;
\(a_i = i\) pour \(i < r\), et \(a_i \geq r\) pour \(i \geq r\).

On dit alors que \((a_i)\) a pour période \(d\) et pour décalage \(r\).

Preuve. 1. Le sens « si » découle du lemme 1 (récurrence). Réciproquement, supposons \(a_u = a_v\). Il existe \(u_0, v_0 \in [r, r+d[\) avec \(d \mid u - u_0\) et \(d \mid v - v_0\), donc \(a_{u_0} = a_u = a_v = a_{v_0}\). Si \(u_0 < v_0\), alors (lemme 1) \(a_{r+d+u_0-v_0} = a_{r+d} = a_r\), ce qui contredit la minimalité de \(d\) ; de même si \(u_0 > v_0\). Donc \(u_0 = v_0\) et \(d \mid u - v\).

Si \(r = 0\), il n'y a rien à montrer. Sinon, \(a_0 = a_{2a_0}\) impose \(2a_0 = 0\) (par minimalité de \(r\)). Alors \(a_{a_i} = a_i\) pour tout \(i\), d'où \(a_i = i\) pour \(i < r\) (et, de même, \(a_i \geq r\) pour \(i \geq r\)).

Lemme 5. On est dans l'un des deux cas suivants :

\(d \mid a_i - i\) pour tout \(i\) ;
\(r = 0\) et \(d \mid a_i - i - d/2\) pour tout \(i\).

Preuve. D'après le lemme 4, si \(a_u = a_v\) alors \(d \mid u - v\). Comme \(a_{a_i + a_0} = a_i\) pour tout \(i\), on a \(d \mid a_i - i + a_0\). Pour \(i = 0\), cela donne \(d \mid 2a_0\). Si \(d \mid a_0\), alors \(d \mid a_i - i\) pour tout \(i\). Sinon \(d \nmid a_0\), donc \(d \mid a_0 - d/2\) et \(d \mid a_i - i - d/2\) pour tout \(i\). Dans ce cas \(a_0 \neq 0\), donc la partie 2 du lemme 4 impose \(r = 0\).

Lemme 6. Si \(d\) est pair et \(d \mid a_0 - d/2\), alors \((a_i)\) est petite. (Dans ce cas, \(r = 0\).)

Preuve. Si \(d \leq k + 1\), d'après le lemme 2, la période \((a_0, \ldots, a_{d-1})\) n'est formée que de termes \(\leq k\), donc \((a_i)\) est petite. Supposons \(d > k + 1\) et montrons \(a_i \leq k\) pour tout \(i\) par récurrence. Le lemme 2 le donne pour \(i \leq k\). On a \(d \mid a_{d/2}\) et \(a_{d/2} \leq k < d\), donc \(a_{d/2} = 0\). Ainsi, pour \(i > k\), si \(a_j \leq k\) pour tout \(j < i\), alors \(a_{i-d/2} \leq k\), donc

\[a_i = a_{(i-d/2)+d/2} = a_{a_{i-d/2} + a_{d/2}} = a_{a_{i-d/2}} \leq k.\]

Lemme 7. Si \((a_i)\) est petite, alors \(r + d \leq k + 1\).

Preuve. Les \(k+2\) termes \(a_0, \ldots, a_{k+1}\) sont dans \(\{0, \ldots, k\}\) ; par le principe des tiroirs, il existe \(u < v \leq k+1\) avec \(a_u = a_v\). Alors \(r \leq u\) et \(d \mid v - u\), donc \(r + d \leq v \leq k + 1\). (Le livret écrit « \(u \leq r\) » ; il faut lire \(r \leq u\). L'argument des tiroirs est implicite dans le livret.)

Lemme 8. Si \((a_i)\) est grande, alors \(r + d > k + 1\) et \(a_i = i\) pour tout \(0 \leq i < r + d\).

Preuve. Comme \((a_i)\) est grande, de période \(d\) et de décalage \(r\), la période \((a_r, \ldots, a_{r+d-1})\) contient un terme \(> k\) ; par le lemme 2, \(r + d - 1 > k\).

On sait déjà que \(a_i = i\) pour \(i < r\). Montrons \(a_i = i\) pour \(r \leq i \leq k\). Par le lemme 6 (et le lemme 5), on a \(d \mid a_i - i\) ; or \(r \leq a_i \leq k\) et \(r \leq i \leq k\), et \(k - r + 1 < d\). Donc \(a_i = i\) pour \(i \leq k\). (Le livret écrit « \(k - r + 1 > d\) » ; il faut lire \(k - r + 1 < d\), ce qui découle de \(r + d > k + 1\).)

Enfin, on montre par récurrence que \(a_i = i\) pour \(k < i < r + d\). Si \(a_j = j\) pour tout \(j < i\), alors \(a_i \geq i\) (sinon \(a_i = a_j\) avec \(j = a_i < i\), donc \(r \leq j\), mais \(i < r + d\) entraîne \(d \nmid i - j\)). Par ailleurs \(a_i + (n - i) = a_i + a_{n-i} \leq n\) (car \(n - i \leq k\)), donc \(a_i = i\).

Comptage. Les suites grandes sont donc déterminées par \(r\) et \(d\). On vérifie sans difficulté que toutes les suites telles que \(a_i = i\) pour \(i < r + d\), de période \(d\) et de décalage \(r\), sont des \(n\)-suites. Il y a \(\frac{(n-k-1)(n+k+2)}{2}\) choix de \((r, d)\) avec \(0 \leq r < n\), \(d \geq 1\) et \(k + 1 < r + d \leq n\).

Pour les suites petites, à période \(d\) et décalage \(r\) fixés, il faut choisir la période \((a_r, \ldots, a_{r+d-1})\) avec \(r \leq a_j \leq k\) et \(d \mid a_j - j\) pour \(r \leq j < r + d\). Il y a \(g(k+1-r, d)\) tels choix (dénombrement), où l'on définit

\[g(x, d) = (p+1)^q p^{d-q}, \qquad p = \lfloor x/d \rfloor, \quad q = x - dp.\]

De plus, si \(d\) est pair, il y a \(g(k+1, d)\) choix de la période \((a_0, \ldots, a_{d-1})\) avec \(d \mid a_j - j - d/2\) pour \(j < d\). Là encore, on vérifie que ces choix donnent bien des \(n\)-suites.

En comptant aussi la suite identité, le nombre total de \(n\)-suites est

\[f(n) = 1 + \frac{(n-k-1)(n+k+2)}{2} + \sum_{d'=1}^{\lfloor (k+1)/2 \rfloor} g(k+1, 2d') + \sum_{r=0}^{k} \sum_{d=1}^{k+1-r} g(k+1-r, d). \tag{1}\]

Minoration. On a

\[f(n) > g\left(k+1, \left\lfloor \frac{k+1}{3} \right\rfloor\right) \geq 3^{\lfloor (k+1)/3 \rfloor} > 3^{n/6 - 1}.\]

Précision ajoutée : le livret écrit \(3^{n/6} - 1\) ; il faut lire \(3^{n/6-1}\). Pour \(k \geq 2\), la deuxième inégalité vient de \(\lfloor (k+1)/\lfloor (k+1)/3 \rfloor \rfloor \geq 3\), et \(\lfloor (k+1)/3 \rfloor \geq \frac{k-1}{3} \geq \frac{n-3}{6}\) ; pour \(n < 6\), on a simplement \(f(n) \geq 1 > 3^{n/6-1}\). On peut donc prendre \(c_1 = 1/3\) et \(\lambda = 3^{1/6}\).

Majoration. Pour montrer \(f(n) < c_2 \lambda^n\), il suffit de trouver un réel \(c_3 > 0\) tel que, pour tout entier \(x \geq 1\),

\[\sum_{d=1}^{x} g(x, d) \leq c_3 3^{x/3}.\]

(Précision ajoutée : les autres termes de (1) sont polynomiaux en \(n\), et la double somme est alors majorée par une série géométrique en \(3^{(k+1-r)/3}\), avec \(3^{(k+1)/3} \leq 3^{1/3} \lambda^n\).) Le lemme suivant suffit, car il majore le membre de gauche par deux séries géométriques de premier terme \(3^{x/3}\).

Lemme. Pour \(d, x \geq 1\) :

\[g(x, d) \leq \begin{cases} 3^{x/3} \left(\frac{64}{81}\right)^{x/3 - d} & \text{si } d \leq x/3, \\[1mm] 3^{x/3} \left(\frac{8}{9}\right)^{d - x/3} & \text{si } d \geq x/3. \end{cases}\]

Preuve. Quelques observations immédiates à partir de la définition :

\(g(x, d)\) est le plus grand produit de \(d\) entiers (positifs) de somme \(x\) (le livret écrit « \((x,d)\) » ; il faut lire \(g(x,d)\)) ;
pour tout entier \(m \geq 1\), \(g(mx, md) = g(x, d)^m\) ;
si \(2d \leq x \leq 3d\), alors \(g(x, d) = 2^{3d-x} 3^{x-2d}\) ; si \(3d \leq x \leq 4d\), alors \(g(x, d) = 3^{4d-x} 4^{x-3d}\).

Cas \(d \leq x/3\). En ajoutant \(4(x-3d)\) facteurs égaux à \(3\),

\[3^{4(x-3d)} g(3x, 3d) \leq g(3x + 12(x-3d),\ 3d + 4(x-3d)) = g(15x - 36d,\ 4x - 9d).\]

Comme \(3(4x - 9d) = 12x - 27d \leq 15x - 36d\) et \(4(4x - 9d) = 16x - 36d \geq 15x - 36d\),

\[g(15x - 36d, 4x - 9d) = 3^{4(4x-9d) - (15x-36d)} 4^{(15x-36d) - 3(4x-9d)} = 3^x 4^{3(x-3d)}.\]

Donc

\[g(x, d)^3 = g(3x, 3d) \leq \frac{3^x 4^{3(x-3d)}}{3^{4(x-3d)}} = 3^x \left(\frac{64}{81}\right)^{x-3d},\]

ce qui donne la première inégalité.

Cas \(d \geq x/3\). En ajoutant \(2(3d - x)\) facteurs égaux à \(3\),

\[3^{2(3d-x)} g(3x, 3d) \leq g(3x + 6(3d-x),\ 3d + 2(3d-x)) = g(18d - 3x,\ 9d - 2x).\]

Comme \(2(9d - 2x) \leq 18d - 3x \leq 18d - 3x + 3(3d - x) = 3(9d - 2x)\),

\[g(18d - 3x, 9d - 2x) = 2^{3(9d-2x) - (18d-3x)} 3^{(18d-3x) - 2(9d-2x)} = 2^{3(3d-x)} 3^x.\]

Donc

\[g(x, d)^3 = g(3x, 3d) \leq \frac{2^{3(3d-x)} 3^x}{3^{2(3d-x)}} = 3^x \left(\frac{8}{9}\right)^{3d-x},\]

d'où la seconde inégalité. (Le livret contient ici deux coquilles : un facteur « \(3\) » parasite après \(g(3x,3d)\) et « \(18 - 3x\) » pour \(18d - 3x\).) \(\blacksquare\)