Shortlist 2021, G3

Domaine : Géométrie · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

Concepts : AM-GM et moyennes · Géométrie combinatoire : enveloppe convexe, points du réseau

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 46 (page 46 du PDF)

Énoncé

Version 1. Let \(n\) be a fixed positive integer, and let \(S\) be the set of points \((x, y)\) on the Cartesian plane such that both coordinates \(x\) and \(y\) are nonnegative integers smaller than \(2n\) (thus \(|S| = 4n^2\)). Assume that \(\mathcal{F}\) is a set consisting of \(n^2\) quadrilaterals such that all their vertices lie in \(S\), and each point in \(S\) is a vertex of exactly one of the quadrilaterals in \(\mathcal{F}\). Determine the largest possible sum of areas of all \(n^2\) quadrilaterals in \(\mathcal{F}\).

Version 2. Let \(n\) be a fixed positive integer, and let \(S\) be the set of points \((x, y)\) on the Cartesian plane such that both coordinates \(x\) and \(y\) are nonnegative integers smaller than \(2n\) (thus \(|S| = 4n^2\)). Assume that \(\mathcal{F}\) is a set of polygons such that all vertices of polygons in \(\mathcal{F}\) lie in \(S\), and each point in \(S\) is a vertex of exactly one of the polygons in \(\mathcal{F}\). Determine the largest possible sum of areas of all polygons in \(\mathcal{F}\).

Indices : les idées clés

• Carrés centraux : chaque point de \(S\) est sommet d'un unique carré centré au centre \(O\) de \(S\) ; ces carrés forment une configuration admissible optimale.
• AM-GM et moyennes (solution 1) : en découpant le polygone en triangles de sommet \(O\), \([P] \leq \frac{1}{2} \sum OA_i^2\), avec égalité pour un carré centré en \(O\).
• Diagonales d'un quadrilatère (solution 2) : \([ABCD] \leq \frac{AC^2 + BD^2}{4}\), puis on maximise \(\sum A_iB_i^2\) sur les appariements des points de \(S\) grâce à l'inégalité entre moyennes quadratique et arithmétique.
• Géométrie combinatoire : points du réseau : calcul exact de \(\sum_{A \in S} OA^2\) par des sommes de carrés.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (deux solutions, la première valable pour les deux versions, la seconde pour la version 1 seulement, et trois remarques).

Réponse (pour les deux versions) : la plus grande somme possible des aires est

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

Conventions communes. Dans toutes les solutions, l'aire d'un polygone \(P\) est notée \([P]\). Un polygone est légal si tous ses sommets sont dans \(S\). Soit \(O = \left(n - \frac{1}{2}, n - \frac{1}{2}\right)\) le centre de \(S\). Un carré légal est central si son centre est \(O\). Un ensemble \(\mathcal{F}\) de polygones est admissible s'il vérifie les conditions de l'énoncé (polygones légaux, chaque point de \(S\) sommet d'exactement un polygone de \(\mathcal{F}\)). Pour \(\mathcal{F}\) admissible, on note \(\Sigma(\mathcal{F})\) la somme des aires de ses polygones.

Solution 1 (pour les deux versions)

Chaque point de \(S\) est sommet d'un unique carré central (on l'obtient par les rotations de \(90^\circ\) de centre \(O\)). Ainsi l'ensemble \(\mathcal{G}\) des carrés centraux est admissible. Nous allons montrer que

\[\Sigma(\mathcal{F}) \leq \Sigma(\mathcal{G}) = \Sigma(n), \tag{1}\]

ce qui établira la réponse.

Lemme 1. Soit \(P = A_1 A_2 \ldots A_m\) un polygone et \(O\) un point quelconque du plan. Alors

\[[P] \leq \frac{1}{2} \sum_{i=1}^{m} OA_i^2 ; \tag{2}\]

de plus, si \(P\) est un carré de centre \(O\), (2) est une égalité.

Preuve. Posons \(A_{m+1} = A_1\). Pour tout \(i\), par AM-GM,

\[[OA_iA_{i+1}] \leq \frac{OA_i \cdot OA_{i+1}}{2} \leq \frac{OA_i^2 + OA_{i+1}^2}{4}.\]

Donc

\[[P] \leq \sum_{i=1}^{m} [OA_iA_{i+1}] \leq \frac{1}{4} \sum_{i=1}^{m} \left(OA_i^2 + OA_{i+1}^2\right) = \frac{1}{2} \sum_{i=1}^{m} OA_i^2,\]

ce qui prouve (2). Toutes ces inégalités sont des égalités quand \(P\) est un carré de centre \(O\). \(\square\)

Soit \(\mathcal{F}\) un ensemble admissible quelconque. En appliquant le lemme 1 à chaque polygone de \(\mathcal{F}\), puis à chaque polygone de \(\mathcal{G}\) (avec égalité), et comme chaque point de \(S\) est sommet d'exactement un polygone dans chacun des deux ensembles, on obtient

\[\Sigma(\mathcal{F}) \leq \frac{1}{2} \sum_{A \in S} OA^2 = \Sigma(\mathcal{G}),\]

ce qui est l'inégalité de gauche de (1).

Il reste à calculer \(\Sigma(\mathcal{G})\) :

\[\begin{aligned} \Sigma(\mathcal{G}) &= \frac{1}{2} \sum_{A \in S} OA^2 = \frac{1}{2} \sum_{i=0}^{2n-1} \sum_{j=0}^{2n-1} \left( \left(n - \tfrac{1}{2} - i\right)^2 + \left(n - \tfrac{1}{2} - j\right)^2 \right) \\ &= \frac{1}{8} \cdot 4 \cdot 2n \sum_{i=0}^{n-1} (2n - 2i - 1)^2 = n \sum_{j=0}^{n-1} (2j+1)^2 = n \left( \sum_{j=1}^{2n} j^2 - \sum_{j=1}^{n} (2j)^2 \right) \\ &= n \left( \frac{2n(2n+1)(4n+1)}{6} - 4 \cdot \frac{n(n+1)(2n+1)}{6} \right) = \frac{n^2 (2n+1)(2n-1)}{3} = \Sigma(n). \end{aligned}\]

\(\blacksquare\)

Solution 2 (pour la version 1)

Soit \(\mathcal{F}\) un ensemble admissible de quadrilatères. Pour tout quadrilatère \(ABCD\) de \(\mathcal{F}\), on écrit

\[[ABCD] = \frac{AC \cdot BD}{2} \sin\varphi \leq \frac{AC^2 + BD^2}{4}, \tag{3}\]

où \(\varphi\) est l'angle entre \(AC\) et \(BD\). En appliquant cette majoration à tous les éléments de \(\mathcal{F}\), on obtient

\[\Sigma(\mathcal{F}) \leq \frac{1}{4} \sum_{i=1}^{2n^2} A_iB_i^2,\]

où \(A_1, A_2, \ldots, A_{2n^2}, B_1, B_2, \ldots, B_{2n^2}\) est une certaine permutation des points de \(S\). Notons

\[f\big((A_i), (B_i)\big) = \sum_{i=1}^{2n^2} A_iB_i^2.\]

Lemme 2. La valeur maximale de \(f\big((A_i), (B_i)\big)\) sur toutes les permutations de \(S\) est \(\frac{4}{3} n^2 (4n^2 - 1)\) ; elle est atteinte lorsque \(A_i\) est le symétrique de \(B_i\) par rapport à \(O\) pour tout \(i\).

Preuve. Écrivons \(A_i = (p_i, q_i)\) et \(B_i = (r_i, s_i)\). On a

\[f\big((A_i), (B_i)\big) = \sum_{i=1}^{2n^2} (p_i - r_i)^2 + \sum_{i=1}^{2n^2} (q_i - s_i)^2 ;\]

il suffit de majorer la première somme, la seconde se traite de même. Chaque abscisse \(j \in \{0, \ldots, 2n-1\}\) apparaît \(2n\) fois parmi les points de \(S\). Avec l'inégalité entre moyenne quadratique et moyenne arithmétique :

\[\begin{aligned} \sum_{i=1}^{2n^2} (p_i - r_i)^2 &= \sum_{i=1}^{2n^2} \left(2p_i^2 + 2r_i^2 - (p_i + r_i)^2\right) = 4n \sum_{j=0}^{2n-1} j^2 - \sum_{i=1}^{2n^2} (p_i + r_i)^2 \\ &\leq 4n \sum_{j=0}^{2n-1} j^2 - \frac{1}{2n^2} \left( \sum_{i=1}^{2n^2} (p_i + r_i) \right)^2 = 4n \sum_{j=0}^{2n-1} j^2 - \frac{1}{2n^2} \left( 2n \sum_{j=0}^{2n-1} j \right)^2 \\ &= 4n \cdot \frac{2n(2n-1)(4n-1)}{6} - 2n^2(2n-1)^2 = \frac{2n^2(2n-1)(2n+1)}{3}. \end{aligned}\]

Toutes ces majorations sont des égalités si \(p_i + r_i = 2n - 1\) pour tout \(i\). Ainsi

\[f\big((A_i), (B_i)\big) \leq \frac{4n^2(4n^2 - 1)}{3},\]

avec égalité lorsque \(p_i + r_i = q_i + s_i = 2n - 1\) pour tout \(i\), c'est-à-dire lorsque \(A_i\) et \(B_i\) sont symétriques par rapport à \(O\). \(\square\)

Le lemme 2 donne

\[\Sigma(\mathcal{F}) \leq \frac{1}{4} \cdot \frac{4n^2(4n^2 - 1)}{3} = \frac{n^2(2n-1)(2n+1)}{3}.\]

Enfin, toutes les majorations sont atteintes simultanément par l'ensemble \(\mathcal{G}\) des carrés centraux. \(\blacksquare\)

Remarques

Remarque 1. Il existe plusieurs variantes de la solution 1, valables pour les deux versions. Par exemple, on peut n'utiliser que l'inégalité \([OA_iA_{i+1}] \leq \frac{1}{2} OA_i \cdot OA_{i+1}\) pour obtenir

\[\Sigma(\mathcal{F}) \leq \frac{1}{2} \sum_{i=1}^{4n^2} OK_i \cdot OL_i,\]

où \((K_i)\) et \((L_i)\) sont deux permutations de tous les points de \(S\) ; on majore ensuite le membre de droite par l'inégalité de réordonnement, et la borne est atteinte par \(\mathcal{G}\). La version 2 semble toutefois plus difficile que la version 1 : la configuration optimale est beaucoup moins facile à deviner tant qu'on n'a pas l'idée de la majoration, et la version 1 admet des solutions (comme la solution 2) qui ne semblent pas se généraliser facilement.

Remarque 2. Le lemme 2 admet d'autres preuves. Par exemple, on peut optimiser la somme \(\sum_i p_i r_i\) pas à pas : si \(p_i < p_j\) et \(r_i < r_j\), échanger \(r_i\) et \(r_j\) diminue \(\sum_i p_i r_i\), donc augmente \(\sum_i (p_i - r_i)^2\). (Le livret dit que l'échange « augmente la somme » ; c'est la somme \(\sum (p_i - r_i)^2\) qui augmente.) Par une suite convenable de tels échanges (en échangeant éventuellement les éléments de certaines paires \((p_i, r_i)\)), on aboutit à une permutation où \(p_i + r_i = 2n - 1\) pour tout \(i\).

Remarque 3. On peut aussi considérer la version 2 pour une grille carrée ayant un nombre impair \(n\) de points sur chaque côté. Si l'on autorise les polygones réduits à un point, la solution 1 s'applique mot pour mot et donne la réponse \(\frac{1}{12} n^2 (n^2 - 1)\). Si on ne les autorise pas, il faut retrancher \(\frac{1}{2}\) à cette réponse.