Shortlist 2021, C7¶

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

Concepts : Coloriages et pavages · Double comptage

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 35 (page 35 du PDF)

Pas encore relu

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

Énoncé¶

Consider a checkered \(3m \times 3m\) square, where \(m\) is an integer greater than \(1\). A frog sits on the lower left corner cell \(S\) and wants to get to the upper right corner cell \(F\). The frog can hop from any cell to either the next cell to the right or the next cell upwards.

Some cells can be sticky, and the frog gets trapped once it hops on such a cell. A set \(X\) of cells is called blocking if the frog cannot reach \(F\) from \(S\) when all the cells of \(X\) are sticky. A blocking set is minimal if it does not contain a smaller blocking set.

(a) Prove that there exists a minimal blocking set containing at least \(3m^2 - 3m\) cells.

(b) Prove that every minimal blocking set contains at most \(3m^2\) cells.

(The official booklet shows an example of a minimal blocking set for \(m = 2\).)

Indices : les idées clés

Construction explicite en bandes (partie (a)) : \(m\) bandes \(3 \times 3m\) donnent un ensemble bloquant minimal de \(3m^2 - 2m + 2\) cases.
Coloriages et pavages (partie (b)) : cases rouges (atteignables depuis \(S\)), bleues (depuis lesquelles on atteint \(F\)), vertes (collantes) ; la minimalité impose que chaque case verte ait un prédécesseur rouge et un successeur bleu.
Double comptage (solution 1 de (b)) : on compte les sauts issus des cases rouges, d'où \(G \leq R + 1\) et, symétriquement, \(G \leq B + 1\).
Chaînes vertes dans des rectangles (solution 2 de (b)) : chaque chaîne de cases vertes tient dans un rectangle dont elle occupe au plus un tiers, et ces rectangles sont disjoints.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution pour la partie (a), deux solutions pour la partie (b), et trois remarques).

Repérons une case par \((i, j)\) (colonne \(i\) de gauche à droite, ligne \(j\) de bas en haut, \(1 \leq i, j \leq 3m\)), de sorte que \(S = (1, 1)\) et \(F = (3m, 3m)\). Un saut va de \((i, j)\) à \((i+1, j)\) ou à \((i, j+1)\).

Solution de la partie (a)¶

On découpe le carré en \(m\) bandes verticales de taille \(3 \times 3m\) (la bande \(t\) est formée des colonnes \(3t-2\), \(3t-1\), \(3t\)), et on prend pour \(X\) l'ensemble suivant (voir la figure 1 du livret officiel) :

dans la première bande : la case \((1, 3m)\), les cases \((2, j)\) pour \(3 \leq j \leq 3m-1\), et la case \((3, 2)\) ; soit \(3m - 1\) cases ;
dans chaque bande intermédiaire \(t\) (\(2 \leq t \leq m-1\)) : la case \((3t-2, 3m-1)\), les cases \((3t-1, j)\) pour \(3 \leq j \leq 3m-2\), et la case \((3t, 2)\) ; soit \(3m - 2\) cases ;
dans la dernière bande : la case \((3m-2, 3m-1)\), les cases \((3m-1, j)\) pour \(2 \leq j \leq 3m-2\), et la case \((3m, 1)\) ; soit \(3m - 1\) cases.

(Description reconstituée d'après les figures 1 et 2(a) du livret.) On vérifie facilement que \(X\) est un ensemble bloquant minimal. Il contient

\[2(3m - 1) + (m - 2)(3m - 2) = 3m^2 - 2m + 2 \geq 3m^2 - 3m\]

cases, ce qui répond à la question. \(\blacksquare\)

Solution 1 de la partie (b)¶

Le coloriage. Soit \(X\) un ensemble bloquant. Une case non collante est rouge si la grenouille peut l'atteindre depuis \(S\) par des sauts sans entrer dans \(X\). Une case non collante est bleue si la grenouille peut atteindre \(F\) depuis cette case par des sauts sans entrer dans \(X\) ; autrement dit, les cases bleues sont celles qu'on atteint depuis \(F\) par des « anti-sauts » (vers le bas ou vers la gauche). Enfin, les cases de \(X\) sont vertes. Comme \(X\) est bloquant, aucune case ne reçoit deux couleurs (une case rouge et bleue donnerait un chemin de \(S\) à \(F\)). (Voir la figure 2 du livret officiel pour un exemple.)

Supposons maintenant \(X\) minimal, et notons \(R\), \(B\), \(G\) les nombres de cases rouges, bleues et vertes.

Affirmation : \(G \leq R + 1\) et \(G \leq B + 1\). Il y a au plus \(2R\) sauts possibles partant de cases rouges. Toute case verte ou rouge, sauf \(S\), est la cible d'un tel saut. Pour une case rouge, c'est la définition. Pour une case verte \(x\) : par minimalité, \(X \setminus \{x\}\) n'est pas bloquant, donc il existe un chemin de \(S\) à \(F\) qui ne rencontre \(X\) qu'en \(x\) ; la case qui précède \(x\) sur ce chemin est rouge. (Précision ajoutée sur ce point.) Par ce double comptage,

\[2R \geq G + (R - 1), \quad \text{soit} \quad G \leq R + 1.\]

Pour obtenir \(G \leq B + 1\), on retourne la grille (en échangeant les rôles de \(S\) et \(F\)) et on applique le même argument.

Conclusion. On obtient

\[9m^2 \geq B + R + G \geq 3G - 2,\]

donc \(G \leq \frac{9m^2 + 2}{3}\), et comme \(G\) est entier, \(G \leq 3m^2\). \(\blacksquare\)

Solution 2 de la partie (b)¶

Cette solution s'appuie sur de nombreuses figures du livret officiel ; nous en donnons le déroulement. On utilise le même coloriage, avec \(X\) minimal. Comme ci-dessus, la minimalité entraîne que chaque case verte a un voisin rouge (ou \(S\)) à gauche ou en dessous, et un voisin bleu (ou \(F\)) à droite ou au-dessus.

Pas plus de deux cases vertes dans un carré \(2 \times 2\). Si un carré \(2 \times 2\) contenait trois cases vertes :

si la case non verte est en haut à droite, la case verte en bas à gauche a ses deux successeurs verts ; elle ne bloque aucun chemin, ce qui contredit la minimalité (figure 3(a)) ; même chose, symétriquement, si la case non verte est en bas à gauche ;
si la case non verte est en haut à gauche, elle devrait être rouge (seul prédécesseur possible de la case verte en haut à droite) et bleue (seul successeur possible de la case verte en bas à gauche), ce qui est impossible (figure 3(b)) ; de même si elle est en bas à droite.

Chaînes. On peut donc répartir les cases vertes en chaînes formées de trois types de liens : deux cases voisines horizontalement, deux cases voisines verticalement, ou deux cases diagonalement voisines, l'une en haut à gauche de l'autre (figure 4). Deux cases vertes voisines selon l'autre diagonale (l'une en bas à gauche de l'autre) ne sont pas reliées : elles appartiennent à des chaînes différentes. Par exemple, la figure 2(b) comporte trois chaînes.

Plan. On va inscrire les chaînes dans des rectangles disjoints, à côtés parallèles aux axes, de sorte que chaque rectangle contienne au plus \(\frac{1}{3}\) de son aire en cases vertes. Cela donnera \(G \leq \frac{9m^2}{3} = 3m^2\). Le rectangle est parfois le plus petit rectangle contenant la chaîne, parfois ce rectangle agrandi dans une ou deux directions.

Pour deux cases consécutives d'une chaîne, la couleur de certaines cases voisines est imposée (figure 5) : pour un lien diagonal, la case en bas à gauche est rouge et celle en haut à droite est bleue ; pour un lien horizontal, les deux cases du dessous sont rouges et les deux du dessus bleues ; pour un lien vertical, les deux cases de gauche sont rouges et les deux de droite bleues.

Chaîne de hauteur (ou de largeur) \(1\). Une chaîne horizontale de \(a\) cases s'inscrit dans un rectangle \(3 \times a\), avec une rangée rouge en dessous et une rangée bleue au-dessus (figure 6(a)). Une case verte isolée s'inscrit dans un rectangle \(1 \times 3\) ou \(3 \times 1\) avec une case rouge et une case bleue (figures 6(b)–(c)) ; sinon on obtient l'une des configurations impossibles de la figure 3.
Chaîne diagonale de longueur \(2\). Elle s'inscrit toujours dans un rectangle \(2 \times 3\) ou \(3 \times 2\) sans autre case verte. En effet, la case rouge imposée en bas à gauche du lien doit elle-même avoir un prédécesseur rouge, à sa gauche ou en dessous (figure 7(a)). Si c'est celui du dessous, la case restante du rectangle \(2 \times 3\) correspondant a la même couleur (figure 7(b)) ; on a alors \(2\) cases vertes sur \(6\).
Chaîne plus longue de hauteur (ou de largeur) \(2\). Elle contient forcément un lien horizontal (resp. vertical) et s'inscrit dans un rectangle \(3 \times a\) : on agrandit le plus petit rectangle contenant la chaîne du côté du grand côté qui touche ce lien (figure 8(a)). La case du coin supérieur droit doit aussi être bleue : elle ne peut être ni rouge ni verte, et si elle n'était pas bleue (figure 8(b)), tous les chemins d'anti-sauts de \(F\) vers elle seraient bloqués par des cases vertes, elles-mêmes entourées de cases bleues, ce qui est impossible. La chaîne contient alors \(a\) cases, exactement le tiers de l'aire du rectangle.
Cas restant : le plus petit rectangle contenant la chaîne est de taille \(a \times b\) avec \(a, b \geq 3\). Notons \(\ell\) la longueur de la chaîne (son nombre de cases).
Si la chaîne a au moins deux liens diagonaux (figure 9), alors \(\ell \leq a + b - 3 \leq \frac{ab}{3}\) (la dernière inégalité équivaut à \((a-3)(b-3) \geq 0\)).
Si elle n'a qu'un lien diagonal, alors \(\ell = a + b - 2\). Dans ce cas, ses liens extrêmes sont l'un horizontal, l'autre vertical, et on agrandit le rectangle dans deux directions pour obtenir un rectangle \((a+1) \times (b+1)\) (figure 10). Là encore \(\ell \leq a + b - 2 \leq \frac{(a+1)(b+1)}{3}\) (ce qui équivaut à \((a-2)(b-2) + 3 \geq 0\)).

Les rectangles sont entièrement coloriés. Toutes les cases des rectangles construits sont rouges, vertes ou bleues (les cases au-dessus et à droite des cases vertes sont bleues, celles en dessous et à gauche sont rouges) ; la preuve reprend l'argument de la figure 8(b).

Les rectangles sont disjoints. Supposons que deux rectangles aient une case commune. D'après ce qui précède, cette case ne peut être qu'un coin commun (figure 11), et les deux rectangles doivent alors avoir été agrandis, sinon ils partageraient une case verte en coin. S'ils ont été agrandis selon le même axe (figure 11(a)), le coin commun ne peut pas être colorié correctement. S'ils ont été agrandis selon des axes différents (figure 11(b)), les deux chaînes ont un point commun et devraient former une seule chaîne. (Les mêmes arguments valent pour les rectangles \(2 \times 3\) et \(1 \times 3\).)

Les rectangles étant disjoints et contenus dans la grille, on obtient \(G \leq \frac{1}{3} \cdot 9m^2 = 3m^2\). \(\blacksquare\)

(Les valeurs \((a-3)(b-3) \geq 0\) et \((a-2)(b-2)+3 \geq 0\) sont des vérifications ajoutées ; le livret donne seulement les inégalités.)

Remarques¶

Remarque 1. On ne sait pas a priori que toute case est rouge, bleue ou verte ; on pourrait colorier les autres en noir. Les arguments de la solution 2 montrent qu'il n'y a pas de case noire : on part d'une case noire la plus proche de \(S\) ; ses voisins de gauche et du dessous doivent être verts ou bleus, et dans tous les cas on obtient une configuration analogue à la figure 8(b).

Remarque 2. La taille maximale d'un ensemble bloquant minimal dans un carré \(3m \times 3m\) semble être \(3m^2 - 2m + 2\). On peut prouver la borne plus fine \(G \leq 3m^2 - m + 2\). Notons \(D_R\) le nombre de cases rouges de branchement (ayant deux voisins suivants rouges) et \(D_B\) le nombre analogue de cases bleues. Un double comptage donne \(G \leq R - D_R + 1\) et \(G \leq B - D_B + 1\), d'où

\[9m^2 \geq R + B + G \geq 3G + D_R + D_B - 2,\]

et il reste à minorer le nombre de cases de branchement pour obtenir \(G \leq 3m^2 - m + 2\).

Remarque 3. Un exemple avec \(3m^2 - 2m + 2\) cases vertes peut avoir une autre allure (voir la figure 12 du livret officiel).