Aller au contenu

Shortlist 2012, C3

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

Concepts : Double comptage · AM-GM et moyennes · Cauchy-Schwarz et lemme de Titu

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

Énoncé

In a \(999 \times 999\) square table some cells are white and the remaining ones are red. Let \(T\) be the number of triples \((C_1, C_2, C_3)\) of cells, the first two in the same row and the last two in the same column, with \(C_1\) and \(C_3\) white and \(C_2\) red. Find the maximum value \(T\) can attain.

Indices : les idées clés
  • Double comptage : avec \(a_i\) et \(b_j\) les nombres de cases blanches de la ligne \(i\) et de la colonne \(j\), \(T = \sum_{(i,j) \text{ rouge}} a_i b_j\).
  • Séparer les variables : \(2a_i b_j \leq a_i^2 + b_j^2\), et chaque ligne \(i\) contient \(n - a_i\) cases rouges, d'où \(T \leq \frac{1}{2}\sum_i (n - a_i)a_i^2 + \frac{1}{2}\sum_j (n - b_j)b_j^2\).
  • AM-GM : \((n - x)x^2 \leq \frac{4n^3}{27}\), avec égalité pour \(x = \frac{2n}{3}\) ; le maximum \(\frac{4n^4}{27}\) est atteint avec \(666\) cases blanches par ligne et par colonne.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution et une remarque).

Solution

Réponse : \(T_{\max} = \frac{4 \cdot 999^4}{27}\).

Montrons que, dans une table \(n \times n\), il y a au plus \(\frac{4n^4}{27}\) tels triplets.

Notons \(a_i\) et \(b_j\) le nombre de cases blanches de la ligne \(i\) et de la colonne \(j\), et \(R\) l'ensemble des cases rouges. Pour toute case rouge \((i, j)\), il y a \(a_i b_j\) triplets admissibles \((C_1, C_2, C_3)\) avec \(C_2 = (i, j)\), donc

\[T = \sum_{(i,j) \in R} a_i b_j.\]

Avec l'inégalité \(2ab \leq a^2 + b^2\), on obtient

\[T \leq \frac{1}{2} \sum_{(i,j) \in R} (a_i^2 + b_j^2) = \frac{1}{2} \sum_{i=1}^{n} (n - a_i) a_i^2 + \frac{1}{2} \sum_{j=1}^{n} (n - b_j) b_j^2,\]

car la ligne \(i\) contient \(n - a_i\) cases rouges et la colonne \(j\) en contient \(n - b_j\). Maximisons maintenant le membre de droite. Par l'inégalité arithmético-géométrique,

\[(n - x)x^2 = \frac{1}{2}(2n - 2x) \cdot x \cdot x \leq \frac{1}{2}\left(\frac{2n}{3}\right)^3 = \frac{4n^3}{27},\]

avec égalité si et seulement si \(x = \frac{2n}{3}\). En rassemblant, on obtient

\[T \leq \frac{n}{2} \cdot \frac{4n^3}{27} + \frac{n}{2} \cdot \frac{4n^3}{27} = \frac{4n^4}{27}.\]

Pour \(n = 999\), tout coloriage avec \(x = \frac{2n}{3} = 666\) cases blanches dans chaque ligne et chaque colonne atteint le maximum, puisque toutes les inégalités ci-dessus deviennent des égalités. Par exemple, on colorie une case \((i, j)\) en blanc si \(i - j \equiv 1, 2, \ldots, 666 \pmod{999}\), et en rouge sinon. La valeur maximale de \(T\) est donc \(\frac{4 \cdot 999^4}{27}\). \(\blacksquare\)

Remarque

On peut obtenir une meilleure estimation préliminaire avec l'inégalité de Cauchy-Schwarz :

\[T = \sum_{(i,j) \in R} a_i b_j \leq \Bigg(\sum_{(i,j) \in R} a_i^2\Bigg)^{1/2} \cdot \Bigg(\sum_{(i,j) \in R} b_j^2\Bigg)^{1/2} = \Bigg(\sum_{i=1}^{n} (n - a_i) a_i^2\Bigg)^{1/2} \cdot \Bigg(\sum_{j=1}^{n} (n - b_j) b_j^2\Bigg)^{1/2}.\]

Elle permet d'aboutir à la même conclusion.