Shortlist 2013, A4

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

Concepts : Double comptage · Graphes : degrés, chemins, arbres · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 13 (page 13 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(n\) be a positive integer, and consider a sequence \(a_1, a_2, \ldots, a_n\) of positive integers. Extend it periodically to an infinite sequence \(a_1, a_2, \ldots\) by defining \(a_{n+i} = a_i\) for all \(i \geq 1\). If

\[a_1 \leq a_2 \leq \cdots \leq a_n \leq a_1 + n \tag{1}\]

and

\[a_{a_i} \leq n + i - 1 \quad \text{for } i = 1, 2, \ldots, n, \tag{2}\]

prove that

\[a_1 + \cdots + a_n \leq n^2.\]

Indices : les idées clés

• Premier pas : \(a_i \leq n + i - 1\) pour tout \(i\) (par l'absurde avec le plus petit contre-exemple et la périodicité), donc \(a_1 \leq n\).
• Double comptage (solution 1) : avec \(b_i\) le nombre d'indices \(j > t\) tels que \(a_j \geq n + i\), on a \(a_{t+1} + \cdots + a_n \leq n(n - t) + b_1 + \cdots + b_t\) et \(a_i + b_i \leq n\).
• Escaliers (solution 2) : les cases sous l'escalier des \(a_i\), et leur symétrique translaté, ne se chevauchent pas dans le carré \(n \times n\) ; ou des flèches sur un cercle (graphes, solution 3), jamais dans les deux sens, donc au plus \(\binom{n}{2}\).

Solutions

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

Solution 1

Montrons d'abord que

\[a_i \leq n + i - 1 \quad \text{pour } i = 1, 2, \ldots, n. \tag{3}\]

Supposons au contraire que \(i\) soit le plus petit contre-exemple. De \(a_n \geq a_{n-1} \geq \cdots \geq a_i \geq n + i\) et \(a_{a_i} \leq n + i - 1\), et compte tenu de la périodicité de la suite, il s'ensuit que

\[a_i \text{ n'est congru ni à } i, \; i + 1, \; \ldots, \; n - 1, \text{ ni à } n \pmod n. \tag{4}\]

L'hypothèse \(a_i \geq n + i\) entraîne donc l'énoncé plus fort \(a_i \geq 2n + 1\), ce qui, avec \(a_1 + n \geq a_n \geq a_i\), donne \(a_1 \geq n + 1\). La minimalité de \(i\) donne alors \(i = 1\), et (4) devient contradictoire. Cela établit la première affirmation.

En particulier, \(a_1 \leq n\). Si \(a_n \leq n\), alors \(a_1 \leq \cdots \leq a_n \leq n\) et l'inégalité voulue est évidente. Sinon, soit \(t\) avec \(1 \leq t \leq n - 1\) tel que

\[a_1 \leq a_2 \leq \cdots \leq a_t \leq n < a_{t+1} \leq \cdots \leq a_n. \tag{5}\]

Comme \(1 \leq a_1 \leq n\) et \(a_{a_1} \leq n\) par (2), on a \(a_1 \leq t\), donc \(a_n \leq n + t\). Ainsi, si pour tout entier \(i \geq 1\) on note \(b_i\) le nombre d'indices \(j \in \{t + 1, \ldots, n\}\) tels que \(a_j \geq n + i\), on a

\[b_1 \geq b_2 \geq \cdots \geq b_t \geq b_{t+1} = 0.\]

Montrons que \(a_i + b_i \leq n\) pour \(1 \leq i \leq t\). En effet, par \(n + i - 1 \geq a_{a_i}\) et \(a_i \leq n\), tout \(j\) avec \(a_j \geq n + i\) (donc \(a_j > a_{a_i}\)) appartient à \(\{a_i + 1, \ldots, n\}\), et pour cette raison \(b_i \leq n - a_i\).

D'après la définition des \(b_i\) et (5),

\[a_{t+1} + \cdots + a_n \leq n(n - t) + b_1 + \cdots + b_t.\]

En ajoutant \(a_1 + \cdots + a_t\) aux deux membres et en utilisant \(a_i + b_i \leq n\) pour \(1 \leq i \leq t\), on obtient

\[a_1 + a_2 + \cdots + a_n \leq n(n - t) + nt = n^2,\]

ce qu'il fallait démontrer. \(\blacksquare\)

Solution 2

Dans le premier quadrant d'une grille infinie, considérons l'« escalier » croissant obtenu en coloriant en foncé les \(a_i\) cases du bas de la \(i\)-ème colonne, pour \(1 \leq i \leq n\). On va montrer qu'il y a au plus \(n^2\) cases foncées.

Pour cela, considérons le carré \(S\) de taille \(n \times n\) du premier quadrant ayant un sommet à l'origine, ainsi que le carré \(n \times n\) situé juste à sa gauche. En partant du coin inférieur gauche de ce dernier, colorions en clair les \(a_j\) cases les plus à gauche de la \(j\)-ème ligne, pour \(1 \leq j \leq n\). Autrement dit, le coloriage clair s'obtient en symétrisant le coloriage foncé par rapport à la droite \(x = y\) et en le translatant de \(n\) unités vers la gauche. La figure illustre cette construction pour la suite \(6, 6, 6, 7, 7, 7, 8, 12, 12, 14\).

Montrons qu'aucune case de \(S\) n'est à la fois foncée et claire. Supposons le contraire, pour une case de la colonne \(i\). Considérons la plus haute case foncée de la colonne \(i\) qui soit dans \(S\). Comme elle est au-dessus d'une case claire et dans \(S\), elle est claire elle aussi. Il y a deux cas.

Cas 1 : \(a_i \leq n\). Cette case foncée et claire est alors \((i, a_i)\), comme sur la figure. Or c'est la \((n + i)\)-ème case de la ligne \(a_i\), et l'on n'a colorié en clair que \(a_{a_i} < n + i\) cases de cette ligne, une contradiction.

Cas 2 : \(a_i \geq n + 1\). Cette case foncée et claire est alors \((i, n)\). C'est la \((n + i)\)-ème case de la ligne \(n\), et l'on a colorié en clair \(a_n \leq a_1 + n\) cases de cette ligne, donc \(i \leq a_1\). Mais \(a_1 \leq a_{a_1} \leq n\) par (1) et (2), donc \(i \leq a_1\) implique \(a_i \leq a_{a_1} \leq n\), ce qui contredit l'hypothèse.

Aucune case de \(S\) n'est donc à la fois foncée et claire. Le nombre de cases coloriées dans \(S\) est donc au plus \(n^2\).

Enfin, s'il y avait une case claire à droite de \(S\), il y aurait par symétrie une case foncée au-dessus de \(S\), et la case \((n, n)\) serait alors foncée et claire. Il s'ensuit que le nombre de cases claires dans \(S\) est égal au nombre de cases foncées hors de \(S\) ; le nombre de cases coloriées dans \(S\) est donc égal à \(a_1 + \cdots + a_n\). Le résultat suit. \(\blacksquare\)

Solution 3

Comme dans la solution 1, on établit d'abord que \(a_i \leq n + i - 1\) pour \(1 \leq i \leq n\). Définissons \(c_i = \max(a_i, i)\) pour \(1 \leq i \leq n\) et prolongeons la suite \(c_1, c_2, \ldots\) par périodicité modulo \(n\). Cette suite vérifie encore les conditions du problème.

Pour \(1 \leq i < j \leq n\), on a \(a_i \leq a_j\) et \(i < j\), donc \(c_i \leq c_j\). De plus, \(a_n \leq a_1 + n\) et \(n < 1 + n\) impliquent \(c_n \leq c_1 + n\). Enfin, les définitions donnent \(c_{c_i} \in \{a_{a_i}, a_i, a_i - n, i\}\), donc \(c_{c_i} \leq n + i - 1\) par (2) et (3). Cela établit (1) et (2) pour \(c_1, c_2, \ldots\)

La nouvelle suite a la propriété supplémentaire

\[c_i \geq i \quad \text{pour } i = 1, 2, \ldots, n, \tag{6}\]

ce qui permet la représentation suivante. Plaçons \(n\) points régulièrement espacés sur un cercle, numérotés \(1, 2, \ldots, n \pmod n\), de sorte que le point \(k\) porte aussi le numéro \(n + k\). Traçons des flèches du sommet \(i\) vers les sommets \(i + 1, \ldots, c_i\), pour \(1 \leq i \leq n\) (on a \(c_i \geq i\) par (6)). Comme \(c_i \leq n + i - 1\) par (3), aucune flèche n'est tracée deux fois, et il n'y a pas de flèche d'un sommet vers lui-même. Le nombre total de flèches est

\[\sum_{i=1}^{n} (c_i - i) = \sum_{i=1}^{n} c_i - \binom{n+1}{2}.\]

Montrons qu'on ne trace jamais les deux flèches \(i \to j\) et \(j \to i\) pour \(1 \leq i < j \leq n\). Supposons le contraire ; cela signifie respectivement que

\[i < j \leq c_i \quad \text{et} \quad j < n + i \leq c_j.\]

On a \(n + i \leq c_j \leq c_1 + n\) par (1), donc \(i \leq c_1\). Comme \(c_1 \leq n\) par (3), cela implique \(c_i \leq c_{c_1} \leq n\) par (1) et (3). Mais alors, par (1) à nouveau, \(j \leq c_i \leq n\) implique \(c_j \leq c_{c_i}\), ce qui, avec \(n + i \leq c_j\), donne \(n + i \leq c_{c_i}\). Cela contredit (2).

Le nombre de flèches est donc au plus \(\binom{n}{2}\), ce qui donne

\[\sum_{i=1}^{n} c_i \leq \binom{n}{2} + \binom{n+1}{2} = n^2.\]

Comme \(a_i \leq c_i\) pour \(1 \leq i \leq n\), l'inégalité voulue suit. \(\blacksquare\)

Remarques

Remarque 1. Esquissons une autre preuve, par récurrence. On vérifie d'abord le cas \(n = 1\) et les cas simples \(a_1 = 1\), \(a_1 = n\) ou \(a_n \leq n\). Puis, comme dans la solution 1, on considère l'indice \(t\) tel que \(a_1 \leq \cdots \leq a_t \leq n < a_{t+1} \leq \cdots \leq a_n\) ; on a encore \(a_1 \leq t\). On définit la suite \(d_1, \ldots, d_{n-1}\) par

\[d_i = \begin{cases} a_{i+1} - 1 & \text{si } i \leq t - 1, \\ a_{i+1} - 2 & \text{si } i \geq t, \end{cases}\]

prolongée par périodicité modulo \(n - 1\). On vérifie que cette suite satisfait encore les hypothèses du problème. L'hypothèse de récurrence donne alors \(d_1 + \cdots + d_{n-1} \leq (n - 1)^2\), d'où

\[\sum_{i=1}^{n} a_i = a_1 + \sum_{i=2}^{t} (d_{i-1} + 1) + \sum_{i=t+1}^{n} (d_{i-1} + 2) \leq t + (t - 1) + 2(n - t) + (n - 1)^2 = n^2.\]

Remarque 2. Une particularité de ce problème est qu'il y a beaucoup de suites pour lesquelles l'égalité a lieu. Il n'est pas difficile d'en trouver, et c'est utile pour guider une preuve. En fait, la solution 2 décrit complètement les suites optimales. On part d'un chemin \(P\) du réseau allant du coin inférieur gauche au coin supérieur droit du carré \(S\) avec des pas vers le haut et vers la droite, tel que le nombre total de pas le long des bords gauche et haut de \(S\) soit au moins \(n\). On colorie en foncé les cases de \(S\) sous \(P\) et en clair celles au-dessus. On symétrise la forme claire par rapport à la droite \(x = y\), on la translate de \(n\) unités vers le haut, et on la colorie en foncé. Comme le montre la solution 2, la région foncée correspond alors à une suite optimale, et toute suite optimale s'obtient ainsi.