Shortlist 2025, N2¶

Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : India

Concepts : Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2025 (avec solutions), section N2 (livret PDF)

Énoncé¶

In an \(n \times n\) board, for each \(1 \leq i \leq n\) and \(1 \leq j \leq n\), the cell in the \(i\)-th row from the bottom and \(j\)-th column from the left contains \(\gcd(i, j)\) leaves. A koala travels from the bottom left corner to the top right corner. At each step, the koala moves up or to the right by a single cell. The koala eats the leaves in each cell it visits, including the bottom left and top right cells.

Determine the maximum number of leaves that the koala can eat.

Here \(\gcd(x, y)\) denotes the greatest common divisor of integers \(x\) and \(y\).

Indices : les idées clés

PGCD de cases voisines : \(\gcd(i, j)\) et \(\gcd(i+1, j)\) sont premiers entre eux et divisent \(j\), donc leur produit divise \(j\).
Somme sous contrainte de produit : si \(xy \leq j\), alors \(x + y \leq j + 1\), car \(x \mapsto x + \frac{j}{x}\) est maximale aux extrémités de \([1, j]\).
Somme télescopique (solution 1) : avec \(E(i,j) = ij\), la majoration de chaque paire de cases consécutives se télescope le long du chemin.
Regrouper par diagonales (solution 2) : à l'instant \(t = i + j\), le koala mange un diviseur strict de \(t\) ; on majore \(g_{2k-1} + g_{2k} \leq k + 1\).
Construction : suivre la diagonale en zigzag.

Solutions

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

Réponse : le nombre maximal de feuilles est \(\dfrac{n^2 + 3n - 2}{2}\).

Solution 1¶

Construction. En alternant pas vers le haut et pas vers la droite, le koala visite les \(n\) cases diagonales, où il mange \(1 + 2 + \cdots + n\) feuilles, et \(n - 1\) cases juste au-dessus de la diagonale (cases \((i+1, i)\)), où il mange une feuille chacune. Il mange au total

\[(1 + 2 + \cdots + n) + (n - 1) = \frac{n(n+1)}{2} + n - 1 = \frac{n^2 + 3n - 2}{2}\]

feuilles.

Majoration. Considérons \(\gcd(i, j)\) et \(\gcd(i+1, j)\). Ils divisent respectivement \(i\) et \(i+1\), qui sont premiers entre eux, donc ils sont premiers entre eux. Comme ils divisent tous deux \(j\), leur produit divise \(j\) (divisibilité et PGCD), donc

\[\gcd(i+1, j) \cdot \gcd(i, j) \leq j.\]

La fonction \(f(x) = x + \frac{j}{x}\) sur \([1, j]\) est maximale pour \(x = 1\) ou \(x = j\). En effet,

\[f(x) - (j+1) = (x - 1) + \left( \frac{j}{x} - j \right) = (x - 1) - \frac{j}{x}(x - 1) = \frac{(x-1)(x-j)}{x} \leq 0,\]

avec égalité si et seulement si \(x = 1\) ou \(x = j\). On a donc

\[\gcd(i, j) + \gcd(i+1, j) \leq \gcd(i, j) + \frac{j}{\gcd(i, j)} \leq j + 1.\]

De même, \(\gcd(i, j) + \gcd(i, j+1) \leq i + 1\). En posant \(E(i, j) = ij\), ces inégalités s'écrivent

\[\gcd(i, j) + \gcd(i+1, j) \leq E(i+1, j) - E(i, j) + 1, \qquad \gcd(i, j) + \gcd(i, j+1) \leq E(i, j+1) - E(i, j) + 1.\]

Supposons que le koala visite, dans l'ordre, les cases \((1,1) = (i_1, j_1), (i_2, j_2), \ldots, (i_{2n-1}, j_{2n-1}) = (n, n)\). Dans la case \((i_t, j_t)\), il mange \(\gcd(i_t, j_t)\) feuilles. Les inégalités ci-dessus donnent

\[\gcd(i_t, j_t) + \gcd(i_{t+1}, j_{t+1}) \leq E(i_{t+1}, j_{t+1}) - E(i_t, j_t) + 1,\]

d'où, par télescopage,

\[\begin{aligned} \sum_{t=1}^{2n-1} \gcd(i_t, j_t) &= \frac{\gcd(1,1) + \gcd(n,n)}{2} + \frac{1}{2} \sum_{t=1}^{2n-2} \big( \gcd(i_t, j_t) + \gcd(i_{t+1}, j_{t+1}) \big) \\ &\leq \frac{n+1}{2} + \frac{1}{2} \sum_{t=1}^{2n-2} \big( E(i_{t+1}, j_{t+1}) - E(i_t, j_t) + 1 \big) \\ &= \frac{n+1}{2} + \frac{2n-2}{2} + \frac{E(n,n) - E(1,1)}{2} = \frac{n^2 + 3n - 2}{2}, \end{aligned}\]

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

Solution 2¶

On montre la construction comme dans la solution 1 ; il reste à prouver que le koala ne peut pas manger davantage.

Disons que le koala part au temps \(t = 2\) de la case \((i_2, j_2) = (1, 1)\) et arrive au temps \(t\) dans la case \((i_t, j_t)\). Chaque pas augmente \(i\) ou \(j\) de \(1\), donc \(i_t + j_t = t\) pour tout \(2 \leq t \leq 2n\). Notons \(g_t = \gcd(i_t, j_t)\) le nombre de feuilles mangées au temps \(t\).

Comme \(i_t + j_t = t\), on a \(g_t = \gcd(t, j_t)\). Ainsi \(g_t\) est un diviseur de \(t\), et comme \(j_t < t\), c'est un diviseur strict de \(t\) ; donc \(g_t \leq t/2\).

Montrons que, pour tout entier \(2 \leq k \leq n\),

\[g_{2k-1} + g_{2k} \leq k + 1. \tag{1}\]

Supposons par l'absurde que \(g_{2k-1} + g_{2k} \geq k + 2\). Comme \(g_t \leq t/2\), on a \(g_{2k} \leq k\) et \(g_{2k-1} \leq k\), donc \(g_{2k-1} \geq 2\) et \(g_{2k} \geq 2\).

Sans perte de généralité, le pas au temps \(2k\) est vers le haut, donc \(i_{2k} = i_{2k-1} + 1\) et \(j_{2k-1} = j_{2k}\). Comme dans la solution 1, \(\gcd(i, j) \gcd(i+1, j) \leq j\), donc \(g_{2k-1} g_{2k} \leq j_{2k}\). En développant \((g_{2k-1} - 2)(g_{2k} - 2) \geq 0\), on obtient

\[g_{2k-1} g_{2k} \geq 2(g_{2k-1} + g_{2k}) - 4.\]

Avec \(g_{2k-1} g_{2k} \leq j_{2k}\) et l'hypothèse \(g_{2k-1} + g_{2k} \geq k + 2\), on obtient \(j_{2k} \geq 2k\). C'est absurde puisque \(j_t < t\) pour tout \(t\). Cela prouve (1).

On obtient alors, en regroupant les cases par paires de diagonales :

\[\sum_{t=2}^{2n} g_t = g_2 + \sum_{k=2}^{n} (g_{2k-1} + g_{2k}) \leq 1 + \sum_{k=2}^{n} (k + 1) = \frac{n^2 + 3n - 2}{2}. \qquad \blacksquare\]

Remarques¶

Remarque 1 (solution 1 sans la fonction \(E\)). On peut obtenir la majoration avec seulement \(\gcd(i, j) + \gcd(i+1, j) \leq j + 1\) et \(\gcd(i, j) + \gcd(i, j+1) \leq i + 1\). Attribuons au koala un score de \(i + 1\) quand il se déplace vers la droite dans la ligne \(i\), et de \(j + 1\) quand il monte dans la colonne \(j\). Si \(S\) est le score total, le nombre de feuilles mangées est au plus \(\frac{S + n + 1}{2}\), car chaque case est comptée deux fois, sauf la première et la dernière (comptées une fois). Depuis \((i, j)\), un pas vers le haut suivi d'un pas vers la droite donne le même score \(i + j + 2\) qu'un pas vers la droite suivi d'un pas vers le haut. Tous les chemins se déduisent les uns des autres par de tels échanges, donc le score total ne dépend pas du chemin : il vaut \(n^2 + 2n - 3\).

Remarque 2. L'inégalité (1) s'applique aussi à chaque paire \(g_{2k}, g_{2k+1}\) : un argument analogue donne \(g_{2k} + g_{2k+1} \leq k + 1\). Plus généralement, on peut montrer de la même façon que

\[\gcd(i, j) + \gcd(i+1, j) \leq \left\lceil \frac{i+j}{2} \right\rceil + 1.\]

Cette inégalité se démontre aussi par des arguments proches de la solution 1 : si l'un des deux PGCD vaut \(1\), on utilise \(\gcd(a, b) \leq \frac{a+b}{2}\) ; sinon, on utilise que \(x + \frac{j}{x}\) est maximal pour \(x = 2\) ou \(x = \frac{j}{2}\) (sur \([2, j/2]\)), ce qui donne \(\gcd(i, j) + \gcd(i+1, j) \leq \frac{j}{2} + 2\).