Shortlist 2024, C8

Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Peru

Concepts : Récurrence et constructions récursives · Graphes : degrés, chemins, arbres · Coloriages et pavages · Principe extrémal

Solution officielle : Shortlist officielle 2024 (avec solutions), section C8 (livret PDF)

Figures reprises du livret officiel de la Shortlist.

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(n\) be a positive integer. Given an \(n \times n\) board, the unit cell in the top left corner is initially coloured black, and the other cells are coloured white. We then apply a series of colouring operations to the board. In each operation, we choose a \(2 \times 2\) square with exactly one cell coloured black and we colour the remaining three cells of that \(2 \times 2\) square black.

Determine all values of \(n\) such that we can colour the whole board black.

Indices : les idées clés

• Construction récursive : pour \(n = 2^{m+1}\), colorier un quart, puis le carré \(2 \times 2\) central, puis les trois autres quarts.
• Graphes : arbres : chaque opération devient un « X » (solution 1) ou une flèche (solution 2) ; l'ensemble forme un arbre, car une opération qui fermerait un cycle toucherait deux cases déjà noires.
• Pavage par des L-triominos et parité : les centres des opérations sont tous des points \((i, j)\) avec \(i \equiv j \pmod 2\), ce qui impose \(n\) pair et force les opérations au bord.
• Réduction \(n \to n/2\) : en regroupant les cases en « grosses cases » \(2 \times 2\), on obtient une configuration de même nature sur un plateau \(\frac{n}{2} \times \frac{n}{2}\).
• Principe extrémal (solution 2) : prendre un « zigzag » le plus loin possible de la racine.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (deux solutions). Les figures, numérotées comme dans le livret, en sont reprises.

Réponse. On peut colorier tout le plateau en noir si et seulement si \(n = 2^k\), avec \(k\) entier positif ou nul.

Solution 1

Les puissances de 2 conviennent. Par récurrence sur \(k\). Pour \(n = 1\) il n'y a rien à faire, et le cas \(k = 1\) est immédiat (une seule opération). Supposons le résultat vrai pour \(k = m\) et considérons un plateau \(2^{m+1} \times 2^{m+1}\), découpé en quatre sous-plateaux \(2^m \times 2^m\). On colorie le sous-plateau en haut à gauche grâce à l'hypothèse de récurrence. On colorie ensuite le carré \(2 \times 2\) central en une seule opération (seule sa case en haut à gauche est noire). Enfin, chacun des trois autres sous-plateaux \(2^m \times 2^m\) peut être entièrement colorié grâce à l'hypothèse de récurrence, en partant de sa case noire la plus proche du centre. Cela achève la récurrence.

Réciproque. Supposons qu'on puisse colorier un plateau \(n \times n\) avec \(n > 1\). On repère les sommets du quadrillage par des coordonnées, le coin en haut à gauche étant \((0, 0)\) et le coin en bas à droite \((n, n)\). Chaque fois qu'on effectue une opération sur le carré \(2 \times 2\) centré en \((i, j)\), on dessine un « X » reliant les centres de ses quatre cases (voir la figure 4), et l'on désigne ce X par \((i, j)\). La première opération donne un X en \((1, 1)\). Comme tout le plateau finit noir, le centre de chaque case est relié à au moins un X. L'ensemble des X forme un graphe \(G\).

Affirmation 1. \(G\) est un arbre.

Preuve. Chaque opération nécessite une case déjà noire, donc chaque nouveau X (sauf le premier) est relié à un X déjà dessiné : \(G\) est connexe. Supposons que \(G\) contienne un cycle, et considérons le X le plus récent de ce cycle : il est relié aux X précédents en au moins deux points (deux centres de cases). L'opération correspondante colorierait donc au plus deux cases, contradiction. \(\square\)

Dans la suite, les affirmations 2 à 4 n'utilisent que deux propriétés : \(G\) est un arbre, et chaque case est reliée à \(G\).

Affirmation 2. S'il y a un X en \((i, j)\), alors \(1 \leq i, j \leq n - 1\) et \(i \equiv j \pmod 2\).

Preuve. Les inégalités sont claires. Disons qu'un X en \((i, j)\) est bon si \(i \equiv j \pmod 2\), et mauvais sinon. Le premier X, en \((1, 1)\), est bon. S'il existait des X mauvais, comme \(G\) est connexe, un bon X serait relié à un mauvais X. Mais deux tels X ont des centres voisins horizontalement ou verticalement, donc partagent deux cases : ils sont reliés en deux points, ce qui crée un cycle. Contradiction : tous les X sont bons. \(\square\)

On dit qu'un X en \((i, j)\) est impair si \(i \equiv j \equiv 1 \pmod 2\), et pair si \(i \equiv j \equiv 0 \pmod 2\).

Affirmation 3. L'entier \(n\) est pair. De plus, il y a \(4(n/2 - 1)\) X impairs reliant les cases du bord du plateau, disposés comme sur la figure 5.

Preuve. Si \(n\) est impair, les quatre coins de la case en bas à gauche sont \((n, 0)\), \((n-1, 0)\), \((n-1, 1)\) et \((n, 1)\), et aucun ne vérifie les conditions de l'affirmation 2 : cette case ne peut être reliée à aucun X. Si \(n\) est pair, chaque case du bord a exactement un coin qui vérifie les conditions de l'affirmation 2, donc le X qui la relie est déterminé de manière unique. Les cases du bord sont donc reliées aux X comme sur la figure 5. \(\square\)

On découpe le plateau \(n \times n\) en \(n^2/4\) blocs \(2 \times 2\), appelés grosses cases. Une grosse case est pleine si elle contient un X impair en son centre, et vide sinon. D'après l'affirmation 3, les grosses cases du bord sont pleines.

Affirmation 4. Toutes les grosses cases sont pleines.

Preuve. Les X ne peuvent être qu'en des points \((i, j)\) avec \(i \equiv j \pmod 2\). Si la grosse case centrée en \((i, j)\) est vide, ses quatre cases ne peuvent être coloriées que par quatre X pairs en \((i-1, j-1)\), \((i+1, j-1)\), \((i-1, j+1)\) et \((i+1, j+1)\), qui « entourent » la grosse case (figure 6). D'après l'affirmation 3, aucune grosse case vide n'est au bord. Donc, s'il existe des grosses cases vides, la frontière entre grosses cases vides et pleines est formée d'une ou plusieurs boucles fermées, constituées de segments de longueur \(2\) qui séparent chacun une grosse case pleine d'une grosse case vide. Comme chaque grosse case vide est entourée de X pairs et chaque grosse case pleine contient un X impair, les deux extrémités de chacun de ces segments sont reliées par des X. Une boucle fermée de tels segments donne alors un cycle de X, ce qui est une contradiction. \(\square\)

Réduction. Ainsi, chaque grosse case est remplie par un X impair, et les liaisons entre grosses cases sont assurées par des X pairs. On réduit alors le problème \(n \times n\) au problème \(\frac n2 \times \frac n2\) : on applique l'homothétie de rapport \(\frac12\) centrée en \((0, 0)\) ; chaque grosse case devient une case ordinaire ; on remplace chaque X impair en \((i, j)\) par le simple point \((i/2, j/2)\), et chaque X pair en \((i, j)\) par un X en \((i/2, j/2)\).

Le nouveau graphe de X est un arbre qui relie toutes les cases du plateau \(\frac n2 \times \frac n2\). En effet, deux X reliés dans le plateau initial le restent après remplacement (certains X étant devenus de simples points). Le centre de chaque case du nouveau plateau correspond à un X impair d'une grosse case pleine, donc il est relié au graphe. Enfin, un cycle dans le nouveau graphe serait formé de X correspondant à des X pairs reliant des grosses cases en cycle ; comme les quatre cases de chaque grosse case sont reliées par un X impair, cela donnerait un cycle dans le graphe initial, contradiction.

Le nouveau graphe vérifie donc les hypothèses des affirmations 2 à 4. On peut répéter l'argument, en divisant la taille du plateau par \(2\) à chaque fois, jusqu'au plateau \(1 \times 1\) (où l'arbre est réduit à un point). Donc \(n\) est une puissance de \(2\). \(\blacksquare\)

Solution 2

Comme dans la solution 1, on peut tout colorier pour \(n = 2^k\).

Une opération revient à poser un L-triomino (les trois cases nouvellement noircies). Pour chaque L-triomino posé, on dessine une flèche et un nœud comme sur la figure 7, et l'on place aussi un nœud au coin en haut à gauche du plateau. (La figure n'est pas reproduite ici ; d'après la suite du texte (racine en \((0,0)\), arêtes diagonales, nœuds en des points \((i, j)\) avec \(i + j\) pair), le nœud est vraisemblablement au centre du carré \(2 \times 2\) de l'opération, et la flèche traverse en diagonale la case noire déjà présente, depuis son coin opposé jusqu'à ce centre. Description reconstituée, à vérifier sur la figure.)

Affirmation 1. Les flèches et les nœuds forment un arbre orienté de racine le coin en haut à gauche.

Preuve. Elle est analogue à celle de l'affirmation 1 de la solution 1 ; de plus, l'orientation des flèches suit l'ordre des opérations, donc elles s'éloignent du nœud racine. \(\square\)

Comme toutes les arêtes de l'arbre sont diagonales, les nœuds ne peuvent être qu'en des points \((i, j)\) avec \(i + j \equiv 0 \pmod 2\). On ne peut donc poser que des L-triominos d'une certaine parité : leur centre est un point avec \(i + j \equiv 0 \pmod 2\). On utilise implicitement cette propriété dans la suite pour déterminer les positions possibles des L-triominos.

On montre ensuite que certaines configurations d'arêtes sont impossibles.

Affirmation 2. Deux arêtes ne peuvent pas être en configuration « parallèle » (figure 8).

Preuve. Les deux arêtes sont orientées dans le même sens ou en sens opposés. Dans le même sens, les L-triominos correspondants se chevauchent. En sens opposés (figure 9), deux cases marquées \(\star\) doivent être dans le plateau, donc couvertes par des L-triominos ; il n'y a qu'une façon de les couvrir par un L-triomino de la bonne parité, mais alors les flèches forment un cycle, ce qui est impossible. \(\square\)

Affirmation 3. Trois arêtes ne peuvent pas être en configuration « zigzag » (figure 10).

Preuve. Supposons qu'il existe un zigzag, et prenons-en un dont la distance à la racine (mesurée le long de l'arbre, jusqu'à l'arête du milieu) est maximale (principe extrémal). On peut supposer que l'arête du milieu est orientée vers le bas à droite. L'arête de droite est alors orientée vers le haut à droite, car deux flèches ne peuvent pas aboutir au même nœud. On dessine les L-triominos correspondants et l'on considère la case marquée \(\star\) : à cause de la parité des centres, il y a deux façons de la couvrir.

• Si le centre du L-triomino est le coin en haut à droite de la case (figure 11), on obtient immédiatement un autre zigzag.
• Si le centre est le coin en bas à gauche de la case (figure 12), il faut couvrir la case marquée \(\star\star\). Un centre au coin en haut à gauche de cette case donnerait deux arêtes parallèles, ce qui contredit l'affirmation 2 ; le centre est donc au coin en bas à droite, ce qui donne un zigzag.

Dans les deux cas, on obtient un zigzag plus éloigné de la racine, ce qui contredit la maximalité. \(\square\)

Coloriage des nœuds. On colorie la racine en jaune. Tout autre nœud est colorié en blanc s'il en part une flèche de direction différente de celle de la flèche qui y arrive, et en noir sinon.

Affirmation 4. Tout enfant d'un nœud noir est blanc.

Preuve. Soit un nœud noir ayant un enfant : la flèche qui en sort a la même direction que la flèche qui y entre (figure 13, à gauche). La case marquée \(\star\) doit être couverte par un L-triomino. Si son centre est le coin en bas à gauche, une flèche sortirait du nœud noir dans une autre direction, ce qui est impossible. Le centre est donc le coin en haut à droite, ce qui fait sortir du nœud supérieur une flèche de direction différente : ce nœud est blanc. \(\square\)

Affirmation 5. Tout nœud blanc a trois enfants, tous noirs.

Preuve. Voir la figure 14. Soit un nœud blanc. La case marquée \(\star\) doit être couverte par un L-triomino ; un centre au coin en bas à droite de la case formerait un zigzag, exclu par l'affirmation 3, donc le centre est au coin en haut à gauche. Ensuite, la case marquée \(\star\star\) doit être couverte ; un centre au coin en haut à droite formerait un zigzag, donc le centre est au coin en bas à gauche. Le nœud blanc a donc trois enfants. Enfin, si l'un de ces enfants avait lui-même trois enfants, on obtiendrait des arêtes parallèles, ce qui contredit l'affirmation 2 : les enfants du nœud blanc sont donc tous noirs. \(\square\)

Les couleurs alternent donc entre noir et blanc en descendant l'arbre : tous les nœuds blancs sont en des points de coordonnées \((2i, 2j)\) et tous les nœuds noirs en des points \((2i + 1, 2j + 1)\).

Réduction. Supposons \(n > 1\) et construisons un nouveau plateau dont les cases sont les carrés \(2 \times 2\) du plateau actuel. On remplace la racine et son enfant par une grosse case et un gros nœud racine, et chaque nœud blanc avec ses trois enfants par un gros L-triomino, une grosse flèche et un gros nœud (figure 15). Chaque nœud noir est l'enfant de la racine ou d'un nœud blanc, donc chaque L-triomino intervient dans exactement un remplacement. De plus, le parent d'un nœud blanc est un nœud noir, dont le parent est un nœud blanc ou la racine ; le point de départ de chaque grosse flèche est donc un gros nœud. On obtient ainsi un pavage par des L-triominos formant un arbre.

Pour \(n > 1\), si un plateau \(n \times n\) peut être pavé par des L-triominos formant un arbre, alors \(n\) est pair et le plateau \(\frac n2 \times \frac n2\) peut l'être aussi. Comme le plateau \(1 \times 1\) l'est trivialement, les seules valeurs possibles sont les \(n = 2^k\). \(\blacksquare\)