Shortlist 2016, C4¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Double comptage
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 34 (page 37 du PDF)
Problème 2 de l'OIM 2016
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2016, où il était le problème 2 (jour 1).
Énoncé¶
Find all positive integers \(n\) for which we can fill in the entries of an \(n \times n\) table with the following properties:
- each entry can be one of \(I\), \(M\) and \(O\);
- in each row and each column, the letters \(I\), \(M\) and \(O\) occur the same number of times; and
- in any diagonal whose number of entries is a multiple of three, the letters \(I\), \(M\) and \(O\) occur the same number of times.
Indices : les idées clés
- Construction périodique : un tableau \(9 \times 9\) convenable, recopié \(k \times k\) fois, donne un tableau \(9k \times 9k\).
- Cases vitales : on découpe le tableau en blocs \(3 \times 3\) et on ne considère que les lignes, colonnes et diagonales passant par les centres des blocs.
- Double comptage : on compte les couples (ligne vitale, case contenant \(M\)) de deux façons, puis on compare modulo \(3\) ; chaque case est sur \(1\) ou \(4\) lignes vitales.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (une solution).
Réponse. Les entiers \(n\) cherchés sont exactement les multiples de \(9\).
Solution¶
Construction pour \(n\) multiple de \(9\). Considérons le tableau \(9 \times 9\) suivant :
On vérifie directement que le tableau (1) satisfait les conditions. Pour \(n = 9k\) avec \(k\) entier positif, on forme un tableau \(n \times n\) avec \(k \times k\) copies de (1). Dans chaque ligne et chaque colonne du grand tableau, il y a trois \(I\), trois \(M\) et trois \(O\) dans chaque bloc de neuf cases consécutives, donc les nombres de \(I\), de \(M\) et de \(O\) sont égaux. De plus, toute diagonale du grand tableau dont le nombre de cases est divisible par \(3\) coupe chaque copie de (1) selon une diagonale dont le nombre de cases est divisible par \(3\) (éventuellement nul). Chacune de ces diagonales contient donc autant de \(I\), de \(M\) que de \(O\).
Condition nécessaire. Considérons un tableau \(n \times n\) satisfaisant les conditions. Le nombre de cases de chaque ligne doit être un multiple de \(3\) ; posons \(n = 3k\) avec \(k\) entier positif. Découpons le tableau en \(k \times k\) blocs \(3 \times 3\). On appelle case vitale la case centrale d'un tel bloc, et ligne vitale toute ligne, colonne ou diagonale contenant au moins une case vitale. Notons \(N\) le nombre de couples \((l, c)\) où \(l\) est une ligne vitale et \(c\) une case de \(l\) contenant la lettre \(M\) (double comptage).
Premier comptage. Chaque ligne vitale contient autant de \(I\), de \(M\) que de \(O\) (les diagonales vitales ont un nombre de cases multiple de \(3\)). Chaque ligne vitale et chaque colonne vitale contient donc \(k\) lettres \(M\), ce qui fait \(k \cdot k + k \cdot k = 2k^2\). Les diagonales vitales d'une direction donnée ont \(3, 6, \ldots, 3k, \ldots, 6, 3\) cases ; elles contiennent donc au total exactement
lettres \(M\). Par conséquent \(N = 4k^2\).
Second comptage. Le tableau contient en tout \(3k^2\) lettres \(M\) (chacune des \(3k\) lignes en contient \(k\)). Or chaque case appartient à exactement \(1\) ou \(4\) lignes vitales. Donc \(N \equiv 3k^2 \pmod 3\).
On obtient \(4k^2 \equiv 3k^2 \pmod 3\), c'est-à-dire \(3 \mid k^2\), ce qui impose que \(k\) soit multiple de \(3\). Ainsi \(n\) est multiple de \(9\), ce qui achève la preuve. \(\blacksquare\)