Shortlist 2023, C3

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Netherlands

Concepts : Récurrence et constructions récursives · Principe des tiroirs

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 38 (page 40 du PDF)

Problème 5 de l'OIM 2023

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2023, où il était le problème 5 (jour 2).

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(n\) be a positive integer. We arrange \(1 + 2 + \cdots + n\) circles in a triangle with \(n\) rows, such that the \(i\)-th row contains exactly \(i\) circles. The following figure shows the case \(n = 6\).

In this triangle, a ninja-path is a sequence of circles obtained by repeatedly going from a circle to one of the two circles directly below it. In terms of \(n\), find the largest value of \(k\) such that if one circle from every row is coloured red, we can always find a ninja-path in which at least \(k\) of the circles are red.

Indices : les idées clés

• Construction dyadique : en coloriant, sur la ligne \(2^a + b\), le cercle numéro \(2b + 1\), un ninja-chemin rencontre au plus un cercle rouge par bloc de lignes \(2^a, \ldots, 2^{a+1} - 1\).
• Programmation dynamique : on attribue à chaque cercle le nombre maximal de cercles rouges sur un ninja-chemin qui arrive à ce cercle (ou qui en part, solution 3).
• Récurrence et constructions récursives : la somme \(\sigma_{2^j}\) des nombres de la ligne \(2^j\) vérifie \(\sigma_{2^j} \geq j \cdot 2^j + 1\) (solution 1) ; \(e_i \leq 2^{i-1}\) (solution 2).
• Découpage en chemins (solutions 2 et 3) : deux cercles rouges portant le même nombre ne sont jamais reliés par un ninja-chemin ; on recouvre le triangle par \(l\) ensembles « en chaîne ».
• Principe des tiroirs : il y a \(n\) cercles rouges mais au plus \(2^N - 1 < n\) d'entre eux portent un nombre \(\leq N\).

Solutions

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

Réponse : \(k = 1 + \lfloor \log_2 n \rfloor\).

Solution 1

Posons \(N = \lfloor \log_2 n \rfloor\), de sorte que \(2^N \leq n \leq 2^{N+1} - 1\).

Construction. Donnons un coloriage où tout ninja-chemin passe par au plus \(N + 1\) cercles rouges. Pour la ligne \(i = 2^a + b\), avec \(0 \leq a \leq N\) et \(0 \leq b < 2^a\), on colorie le \((2b+1)\)-ième cercle. Dans le bloc des lignes \(2^a, 2^a + 1, \ldots, 2^{a+1} - 1\), les cercles rouges avancent de deux positions à chaque ligne, alors qu'un ninja-chemin avance d'au plus une position par ligne : tout ninja-chemin passe donc par au plus un cercle rouge dans chacun des blocs \(2^a, \ldots, 2^{a+1} - 1\), pour \(0 \leq a \leq N\). Il passe donc par au plus \(N + 1\) cercles rouges.

Il existe toujours un ninja-chemin avec au moins \(N + 1\) cercles rouges. À chaque cercle \(C\), on attribue le nombre maximal de cercles rouges sur un ninja-chemin partant du sommet du triangle et arrivant en \(C\). Remarquons que :

• si \(C\) n'est pas rouge, son nombre est le maximum des nombres du ou des deux cercles situés au-dessus de \(C\) ;
• si \(C\) est rouge, son nombre vaut un de plus que ce maximum.

Notons \(v_1, \ldots, v_i\) les nombres de la ligne \(i\), et \(v_m\) le plus grand d'entre eux. Alors les nombres de la ligne \(i + 1\) sont au moins

\[v_1, \ldots, v_{m-1}, v_m, v_m, v_{m+1}, \ldots, v_i,\]

sans même tenir compte du fait qu'un cercle de la ligne \(i + 1\) est rouge. Pour ce cercle rouge, la minoration peut être augmentée de \(1\). La somme des nombres de la ligne \(i + 1\) est donc au moins

\[(v_1 + \cdots + v_i) + v_m + 1.\]

Affirmation 1. Soit \(\sigma_k\) la somme des nombres de la ligne \(k\). Pour \(0 \leq j \leq N\), on a \(\sigma_{2^j} \geq j \cdot 2^j + 1\).

Preuve. Par récurrence sur \(j\). C'est clair pour \(j = 0\), car le nombre de la première ligne vaut toujours \(1\). Supposons \(\sigma_{2^j} \geq j \cdot 2^j + 1\). Comme la ligne \(2^j\) a \(2^j\) cercles, le plus grand nombre de cette ligne est au moins \(j + 1\). Par conséquent (les maxima ne décroissent pas d'une ligne à la suivante), pour tout \(k \geq 2^j\), la ligne \(k\) contient un cercle de nombre au moins \(j + 1\). L'observation ci-dessus donne alors

\[\sigma_{k+1} \geq \sigma_k + (j + 1) + 1 = \sigma_k + (j + 2).\]

On en déduit

\[\sigma_{2^{j+1}} \geq \sigma_{2^j} + 2^j(j + 2) \geq j \cdot 2^j + 1 + 2^j(j + 2) = (j + j + 2) 2^j + 1 = (j + 1) 2^{j+1} + 1,\]

ce qui achève la récurrence. \(\square\)

Pour \(j = N\), cela implique qu'un cercle de la ligne \(2^N \leq n\) porte un nombre au moins \(N + 1\) : il existe un ninja-chemin passant par au moins \(N + 1\) cercles rouges. \(\blacksquare\)

Solution 2

On donne une autre preuve de l'existence d'un ninja-chemin passant par au moins \(N + 1\) cercles rouges (la construction est celle de la solution 1). On attribue les nombres aux cercles comme dans la solution 1, mais on ne s'intéresse qu'aux cercles rouges. Pour tout entier \(i \geq 1\), notons \(e_i\) le nombre de cercles rouges portant le nombre \(i\).

Affirmation 2. Si le cercle rouge de la ligne \(l\) porte le nombre \(i\), alors \(e_i \leq l\).

Preuve. Si deux cercles rouges \(C\) et \(C'\) portent le même nombre \(i\), il ne peut pas exister de ninja-chemin les reliant (sinon le plus bas aurait un nombre au moins \(i + 1\)). On partage le triangle en un petit triangle, dont le sommet est le cercle rouge de la ligne \(l\), et \(l - 1\) « lignes » diagonales qui recouvrent tous les autres cercles ; deux cercles d'un même ensemble sont toujours reliés par un ninja-chemin. Chaque ensemble contient donc au plus un cercle rouge de nombre \(i\), d'où \(e_i \leq l\). \(\square\)

Observons que s'il existe un cercle rouge \(C\) de nombre \(i \geq 2\), alors il existe un cercle rouge de nombre \(i - 1\) sur une ligne située au-dessus de celle de \(C\) : c'est l'avant-dernier cercle rouge d'un ninja-chemin optimal arrivant en \(C\).

Affirmation 3. Pour tout entier \(i \geq 1\), \(e_i \leq 2^{i-1}\).

Preuve. Par récurrence sur \(i\). Le cas \(i = 1\) est clair : le seul cercle rouge de nombre \(1\) est celui du sommet du triangle. Supposons l'énoncé vrai pour \(1 \leq i \leq j - 1\) et montrons-le pour \(i = j\). Si \(e_j = 0\), il n'y a rien à prouver. Sinon, soit \(l\) minimal tel que le cercle rouge de la ligne \(l\) porte le nombre \(j\). Alors les cercles rouges des lignes \(1, \ldots, l - 1\) portent tous un nombre strictement inférieur à \(j\) (d'après l'observation, un nombre \(> j\) au-dessus forcerait un nombre \(j\) encore plus haut). Ainsi

\[l - 1 \leq e_1 + e_2 + \cdots + e_{j-1} \leq 1 + 2 + \cdots + 2^{j-2} = 2^{j-1} - 1.\]

Donc \(l \leq 2^{j-1}\), et par l'affirmation 2, \(e_j \leq l \leq 2^{j-1}\). \(\square\)

On en déduit

\[e_1 + e_2 + \cdots + e_N \leq 1 + \cdots + 2^{N-1} = 2^N - 1 < n.\]

Comme il y a \(n\) cercles rouges, par le principe des tiroirs l'un d'eux porte un nombre au moins \(N + 1\) : il existe un ninja-chemin passant par au moins \(N + 1\) cercles rouges. \(\blacksquare\)

Solution 3

Encore une autre preuve de l'existence d'un ninja-chemin passant par au moins \(N + 1\) cercles rouges. Cette fois, on attribue à un cercle \(C\) le nombre maximal de cercles rouges sur un ninja-chemin partant de \(C\) (en comptant \(C\) lui-même).

Notons \(f_i\) le nombre de cercles rouges portant le nombre \(i\). Si un cercle rouge \(C\) porte le nombre \(i\) et s'il existe un ninja-chemin de \(C\) vers un autre cercle rouge \(C'\), alors le nombre de \(C'\) est strictement inférieur à \(i\).

Affirmation 4. Si le cercle rouge de la ligne \(l\) porte un nombre inférieur ou égal à \(i\), alors \(f_i \leq l\).

Preuve. Comme pour l'affirmation 2. L'argument supplémentaire est que si le cercle rouge de la ligne \(l\) porte un nombre strictement inférieur à \(i\), alors le petit triangle ne peut contenir aucun cercle rouge de nombre \(i\). \(\square\)

Affirmation 5. Pour tout \(0 \leq i \leq N\),

\[f_1 + f_2 + \cdots + f_i \leq n - \left\lfloor \frac{n}{2^i} \right\rfloor.\]

Preuve. Par récurrence sur \(i\). Pour \(i = 0\), le membre de gauche est une somme vide et le membre de droite est nul. Soit \(i \geq 1\), et supposons l'énoncé vrai pour \(i - 1\). Soit \(l\) minimal tel que le cercle rouge de la ligne \(l\) porte un nombre inférieur ou égal à \(i\). Alors tous les cercles rouges de nombre \(\leq i\) sont sur les lignes \(l, l+1, \ldots, n\), d'où

\[f_1 + f_2 + \cdots + f_i \leq n - l + 1.\]

D'autre part, l'hypothèse de récurrence et \(f_i \leq l\) (affirmation 4) donnent

\[f_1 + \cdots + f_{i-1} + f_i \leq n - \left\lfloor \frac{n}{2^{i-1}} \right\rfloor + l.\]

En faisant la moyenne des deux inégalités :

\[f_1 + \cdots + f_i \leq n - \frac{1}{2}\left\lfloor \frac{n}{2^{i-1}} \right\rfloor + \frac{1}{2}.\]

Le membre de gauche étant entier, on obtient (partie entière)

\[f_1 + \cdots + f_i \leq n - \left\lfloor \frac{1}{2}\left\lfloor \frac{n}{2^{i-1}} \right\rfloor \right\rfloor = n - \left\lfloor \frac{n}{2^i} \right\rfloor.\]

Cela achève la récurrence. \(\square\)

Pour \(i = N\), on obtient

\[f_1 + f_2 + \cdots + f_N \leq n - \left\lfloor \frac{n}{2^N} \right\rfloor < n,\]

donc l'un des \(n\) cercles rouges porte un nombre au moins \(N + 1\) : il existe un ninja-chemin passant par au moins \(N + 1\) cercles rouges. \(\blacksquare\)

Remarques

Remarque 1. Par essentiellement le même argument, on peut démontrer par récurrence l'inégalité (avec les \(e_i\) de la solution 2)

\[e_a + e_{a+1} + \cdots + e_{a+i-1} \leq n - \left\lfloor \frac{n}{2^i} \right\rfloor\]

à la place. Le cas \(a = 1\), \(i = N\) donne le résultat voulu.