Shortlist 2016, C8

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

Concepts : Coloriages et pavages · Graphes : degrés, chemins, arbres · Principe des tiroirs

Solution officielle : Shortlist officielle 2016 (avec solutions), p. 42 (page 45 du 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. Determine the smallest positive integer \(k\) with the following property: it is possible to mark \(k\) cells on a \(2n \times 2n\) board so that there exists a unique partition of the board into \(1 \times 2\) and \(2 \times 1\) dominoes, none of which contains two marked cells.

Indices : les idées clés

• Coloriages et pavages : une construction explicite avec \(2n\) cases marquées sur la moitié d'une diagonale force tout le pavage.
• Graphes : on superpose le pavage et son symétrique par rapport à la diagonale ; le graphe à arêtes rouges et bleues se décompose en cycles alternés.
• Principe des tiroirs : avec moins de \(2n\) cases marquées, l'un des \(n\) cycles passant par la diagonale contient au plus une case marquée, et on peut y échanger les dominos.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2016 (une solution).

Réponse. \(k = 2n\).

Solution

Numérotons les lignes et les colonnes \(1, 2, \ldots, 2n\), et notons \((i, j)\) la case de la \(i\)-ème ligne et de la \(j\)-ème colonne.

Construction avec \(2n\) cases. Pour \(i = 1, 2, \ldots, n\), on marque les cases \((i, i)\) et \((i, i+1)\). Montrons que la partition voulue existe et est unique. Les deux diagonales du plateau le découpent en quatre régions. Le domino qui recouvre la case \((1, 1)\) doit être vertical (il ne peut pas contenir \((1,2)\), qui est marquée). Cela force à son tour les dominos recouvrant \((2, 2), (3, 3), \ldots, (n, n)\) à être verticaux. Par récurrence, tous les dominos de la région de gauche sont verticaux. Par symétrie de rotation, ceux de la région du bas sont horizontaux, et ainsi de suite. La partition existe donc et elle est unique.

Minimalité. Supposons qu'on ait marqué seulement \(k < 2n\) cases et qu'il existe une partition \(\mathcal{P}\) convenable. Il suffit de construire une autre partition convenable, distincte de \(\mathcal{P}\). Soit \(d\) la diagonale principale du plateau.

On construit un graphe dont les arêtes ont deux couleurs. Ses sommets sont les cases du plateau. On relie deux sommets par une arête rouge s'ils appartiennent au même domino de \(\mathcal{P}\), et par une arête bleue si leurs symétriques par rapport à \(d\) sont reliés par une arête rouge. Deux sommets peuvent être reliés par des arêtes des deux couleurs. Chaque sommet a exactement une arête rouge et une arête bleue ; le graphe se décompose donc en cycles dans lesquels les couleurs alternent (un cycle peut être de longueur \(2\)).

Soit \(c\) une case de la diagonale \(d\). Ses deux arêtes sont symétriques l'une de l'autre par rapport à \(d\) ; comme un domino contenant \(c\) n'est pas symétrique par rapport à \(d\), elles relient \(c\) à deux cases différentes. Donc \(c\) appartient à un cycle \(C(c)\) de longueur au moins \(4\). Considérons une portion \(c_0, c_1, \ldots, c_m\) de ce cycle, avec \(c_0 = c\) et \(m\) le plus petit entier strictement positif tel que \(c_m\) soit sur \(d\). Clairement \(c_m \neq c\). Par construction, le chemin symétrique de celui-ci par rapport à \(d\) est aussi dans le graphe, et ces deux chemins forment ensemble le cycle \(C(c)\). Ainsi \(C(c)\) contient exactement deux cases de \(d\). Les \(2n\) cases de \(d\) se répartissent donc en \(n\) cycles \(C_1, C_2, \ldots, C_n\), chacun de longueur au moins \(4\).

Par le principe des tiroirs, puisque \(k < 2n\), l'un des cycles \(C_i\) contient au plus une des \(k\) cases marquées. On modifie alors \(\mathcal{P}\) : on retire tous les dominos qui contiennent les sommets de \(C_i\) (ce sont les arêtes rouges de \(C_i\)) et on pose à la place les dominos correspondant aux arêtes bleues de \(C_i\). Comme \(C_i\) a au moins \(4\) sommets, la nouvelle partition \(\mathcal{P}'\) est différente de \(\mathcal{P}\). Aucun domino de \(\mathcal{P}'\) ne contient deux cases marquées, puisque \(C_i\) contient au plus une case marquée. La partition n'est donc pas unique, et \(k\) ne peut pas être inférieur à \(2n\).

La plus petite valeur est donc \(k = 2n\). \(\blacksquare\)