Shortlist 2012, C3¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Double comptage · AM-GM et moyennes
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 21 (page 21 du PDF)
Énoncé¶
Dans un tableau carré \(999 \times 999\), certaines cases sont blanches et les autres rouges. Soit \(T\) le nombre de triplets \((C_1, C_2, C_3)\) de cases, les deux premières dans une même ligne et les deux dernières dans une même colonne, avec \(C_1\) et \(C_3\) blanches et \(C_2\) rouge. Trouver la plus grande valeur que peut atteindre \(T\).
Énoncé original (anglais)
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).
Réponse : \(T_{\max} = \frac{4 \cdot 999^4}{27}\).
Solution¶
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
Avec l'inégalité \(2ab \leq a^2 + b^2\), on obtient
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,
avec égalité si et seulement si \(x = \frac{2n}{3}\). En rassemblant, on obtient
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 :
Elle permet d'aboutir à la même conclusion.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2024 C3 ★★☆☆☆ : Des chevaliers en cercle échangent leurs places pour serrer la main de leur partenaire : combien d'échanges ?
- 2018 C3 ★★☆☆☆ : Sisyphe déplace des pierres d'autant de cases au plus que la pile en compte : il lui faut au moins \(\sum \lceil n/k \rceil\) tours.
- 2016 C3 ★★☆☆☆ : Les sommets d'un \(n\)-gone régulier sont coloriés en trois couleurs, chacune en nombre impair : un triangle isocèle est tricolore.
- 2016 C4 ★★☆☆☆ · OIM P2 : Pour quels \(n\) peut-on remplir un tableau \(n \times n\) de \(I\), \(M\), \(O\) équilibrés sur les lignes, colonnes et certaines diagonales ?