Shortlist 2006, C6

Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Colombia

Concepts : Coloriages et pavages · Récurrence et constructions récursives · Principe extrémal

Solution officielle : Shortlist officielle 2006 (avec solutions), p. 29 (page 30 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

A holey triangle is an upward equilateral triangle of side length \(n\) with \(n\) upward unit triangular holes cut out. A diamond is a \(60^\circ\)–\(120^\circ\) unit rhombus. Prove that a holey triangle \(T\) can be tiled with diamonds if and only if the following condition holds: Every upward equilateral triangle of side length \(k\) in \(T\) contains at most \(k\) holes, for \(1 \leq k \leq n\).

Indices : les idées clés

• Nécessité : chaque losange couvre une cellule montante et une descendante ; un sous-triangle de taille \(k\) a \(\frac{k^2 + k}{2}\) cellules montantes et \(\frac{k^2 - k}{2}\) descendantes (pavages).
• Lemme des triangles pleins : si deux triangles « pleins » (exactement \(k\) trous) se touchent, le plus petit triangle les contenant est aussi plein.
• Récurrence sur \(n\) : on pave la dernière ligne en déplaçant chaque trou \(a_i\) vers une cellule \(b_i\) de la ligne au-dessus ; le bon choix \(b_1 = w\) vient du triangle plein maximal associé à \(u = a_1\).

Solutions

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

Solution

Soit \(T\) un triangle troué. Ses triangles unités sont appelés cellules. On dit simplement « triangle » au lieu de « triangle équilatéral pointe en haut » et « taille » au lieu de « longueur de côté ».

Prouvons d'abord la nécessité. Supposons qu'un triangle troué \(T\) puisse être pavé par des losanges, et considérons un tel pavage. Soit \(T'\) un triangle de taille \(k\) dans \(T\) contenant \(h\) trous. Concentrons-nous sur les losanges qui recouvrent une ou deux cellules de \(T'\). Ils forment une figure \(R\). Le bord de \(T'\) est formé de cellules montantes, donc \(R\) est un triangle de taille \(k\) privé de \(h\) trous montants, avec éventuellement des cellules descendantes qui dépassent. Il y a donc exactement \((k^2 + k)/2 - h\) cellules montantes dans \(R\), et au moins \((k^2 - k)/2\) cellules descendantes (sans compter celles qui dépassent). D'autre part, chaque losange recouvre une cellule montante et une cellule descendante, ce qui implique \((k^2 + k)/2 - h \geq (k^2 - k)/2\). Il s'ensuit que \(h \leq k\), comme voulu.

Passons à la suffisance. Pour abréger, on dit qu'un ensemble de trous d'un triangle donné \(T\) est dispersé si tout triangle de taille \(k\) de \(T\) contient au plus \(k\) trous. Pour un ensemble \(S\) de trous dispersés, un triangle de taille \(k\) est dit plein de \(S\) s'il contient exactement \(k\) trous de \(S\). La preuve repose sur l'observation suivante.

Lemme. Soit \(S\) un ensemble de trous dispersés dans \(T\). Supposons que deux triangles \(T'\) et \(T''\) soient pleins de \(S\) et qu'ils se touchent ou se coupent. Notons \(T' + T''\) le plus petit triangle de \(T\) qui les contient. Alors \(T' + T''\) est aussi plein de \(S\).

Preuve. Soient \(a\), \(b\), \(c\) et \(d\) les tailles des triangles \(T'\), \(T''\), \(T' \cap T''\) et \(T' + T''\), et supposons qu'ils contiennent respectivement \(a\), \(b\), \(x\) et \(y\) trous de \(S\). (Remarquons que \(T' \cap T''\) peut être un point, auquel cas \(c = 0\).) Comme \(S\) est dispersé, on a \(x \leq c\) et \(y \leq d\). La configuration géométrique des triangles vérifie évidemment \(a + b = c + d\). De plus, \(a + b \leq x + y\), puisque \(a + b\) compte deux fois les trous de \(T' \cap T''\). Ces conclusions impliquent \(x = c\) et \(y = d\), comme voulu. \(\square\)

Soit maintenant \(T_n\) un triangle troué de taille \(n\), et supposons que l'ensemble \(H\) de ses trous soit dispersé. Montrons par récurrence sur \(n\) que \(T_n\) peut être pavé par des losanges. Le cas de base \(n = 1\) est trivial. Supposons \(n \geq 2\) et l'affirmation vraie pour les triangles troués de taille inférieure à \(n\).

Notons \(B\) la ligne du bas de \(T_n\) et \(T'\) le triangle formé par ses \(n - 1\) lignes du haut. Il y a au moins un trou dans \(B\), puisque \(T'\) contient au plus \(n - 1\) trous. S'il n'y a qu'un trou, il y a une unique façon de paver \(B\) par des losanges. De plus, \(T'\) contient exactement \(n - 1\) trous, ce qui en fait un triangle troué de taille \(n - 1\), et ces trous sont dispersés. Il reste alors à appliquer l'hypothèse de récurrence.

Supposons donc qu'il y ait \(m \geq 2\) trous dans \(B\), notés \(a_1, \ldots, a_m\) de gauche à droite. Soit \(\ell\) la droite séparant \(B\) de \(T'\). Pour tout \(i = 1, \ldots, m - 1\), choisissons une cellule montante \(b_i\) entre \(a_i\) et \(a_{i+1}\), de base sur \(\ell\). Plaçons un losange recouvrant \(b_i\) et sa voisine inférieure, une cellule descendante de \(B\). Le reste de \(B\) se pave de façon unique par des losanges. Retirons de \(T_n\) la ligne \(B\) et les cellules \(b_1, \ldots, b_{m-1}\) pour obtenir un triangle troué \(T_{n-1}\) de taille \(n - 1\). La conclusion découlera de la récurrence si le choix de \(b_1, \ldots, b_{m-1}\) garantit la condition suivante : si l'on remplace les trous \(a_1, \ldots, a_{m-1}\) par \(b_1, \ldots, b_{m-1}\), le nouvel ensemble de trous est encore dispersé.

Montrons qu'un tel choix est possible. On peut définir les cellules \(b_1, \ldots, b_{m-1}\) une par une dans cet ordre, en s'assurant que la condition ci-dessus est vérifiée à chaque étape. Il suffit donc de prouver qu'il existe un choix convenable pour \(b_1\), et l'on pose \(a_1 = u\), \(a_2 = v\) pour plus de clarté.

Soit \(\Delta\) le triangle de taille maximale qui est plein de \(H\), qui contient le sommet supérieur du trou \(u\), et dont la base est sur la droite \(\ell\). On appelle \(\Delta\) l'associé de \(u\). Remarquons que \(\Delta\) ne touche pas \(v\). En effet, si \(\Delta\) est de taille \(r\), il contient \(r\) trous de \(T_n\). En prolongeant ses côtés obliques vers le bas, on obtient un triangle \(\Delta'\) de taille \(r + 1\) contenant au moins un trou de plus, à savoir \(u\). Comme il y a au plus \(r + 1\) trous dans \(\Delta'\), il ne peut pas contenir \(v\). Par conséquent, \(\Delta\) ne contient pas le sommet supérieur de \(v\).

Soit \(w\) la cellule montante de base sur \(\ell\) qui est à droite de \(\Delta\) et qui a un sommet commun avec lui. L'observation ci-dessus montre que \(w\) est à gauche de \(v\). Remarquons que \(w\) n'est pas un trou, sinon \(\Delta\) pourrait être agrandi en un triangle plus grand plein de \(H\).

Montrons que si l'on remplace le trou \(u\) par \(w\), le nouvel ensemble de trous est encore dispersé. Pour le vérifier, il suffit de vérifier que si un triangle \(\Gamma\) de \(T_n\) contient \(w\) mais pas \(u\), alors \(\Gamma\) n'est pas plein de \(H\). Supposons au contraire que \(\Gamma\) soit plein de \(H\). Considérons le plus petit triangle \(\Gamma + \Delta\) contenant \(\Gamma\) et l'associé \(\Delta\) de \(u\). Évidemment, \(\Gamma + \Delta\) est plus grand que \(\Delta\), puisque \(\Gamma\) contient \(w\) mais pas \(\Delta\). Ensuite, \(\Gamma + \Delta\) est plein de \(H \setminus \{u\}\) d'après le lemme, puisque \(\Gamma\) et \(\Delta\) ont un point commun et qu'aucun d'eux ne contient \(u\).

Si \(\Gamma\) est au-dessus de la droite \(\ell\), alors \(\Gamma + \Delta\) aussi, ce qui contredit le choix maximal de \(\Delta\). Si \(\Gamma\) contient des cellules de la ligne \(B\), remarquons que \(\Gamma + \Delta\) contient \(u\). Soit \(s\) la taille de \(\Gamma + \Delta\). Comme il est plein de \(H \setminus \{u\}\), \(\Gamma + \Delta\) contient \(s\) trous autres que \(u\). Mais il contient aussi \(u\), ce qui contredit l'hypothèse que \(H\) est dispersé.

L'affirmation en découle : \(b_1 = w\) est un choix convenable pour \(a_1 = u\) et \(a_2 = v\). Comme expliqué ci-dessus, cela suffit pour terminer la récurrence. \(\blacksquare\)