Shortlist 2023, C6

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

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

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 49 (page 51 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, and consider an \(N \times N\) grid. A right-down path is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A right-up path is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence.

Prove that the cells of the \(N \times N\) grid cannot be partitioned into less than \(N\) right-down or right-up paths. For example, the following partition of the \(5 \times 5\) grid uses \(5\) paths.

Indices : les idées clés

• Pavages (solution 1) : on traduit une partition en \(k\) chemins en un empilement de « bons parallélogrammes » (deux demi-carrés isocèles rectangles) laissant une aire \(k\) vide ; il faut montrer que l'aire vide est au moins \(N\).
• Rayons laser et miroirs (solution 1) : en traçant dans chaque case la diagonale qui ne coupe aucun parallélogramme, un rayon qui traverse un bon parallélogramme retrouve sa direction ; un rayon qui tourne d'un quart de tour (resp. fait demi-tour) traverse au moins un (resp. deux) triangle(s) vide(s).
• Rayons qui ne se croisent pas (solution 1) : on ne peut pas avoir à la fois des rayons reliant gauche et droite et des rayons reliant haut et bas, ce qui force \(2N\) triangles vides.
• Récurrence sur \(N\) (solution 2) : on prolonge le chemin issu du coin supérieur gauche jusqu'au coin inférieur droit, puis on le retire et l'on recolle les deux morceaux en une grille \((N-1) \times (N-1)\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (deux solutions).

Solution 1

On appelle bon parallélogramme un parallélogramme formé de deux triangles rectangles isocèles (deux demi-cases) recollés (voir la figure : quatre orientations possibles).

À toute partition en \(k\) chemins « droite-bas » ou « droite-haut », on associe un empilement de bons parallélogrammes qui laisse une aire \(k\) vide (voir la figure : entre deux cases consécutives d'un chemin, on place un bon parallélogramme à cheval sur ces deux cases ; un chemin de \(\ell\) cases en utilise \(\ell - 1\), d'aire \(\ell - 1\), et laisse donc une aire \(1\) vide). Précision ajoutée : le livret ne détaille pas cette correspondance, qu'il montre sur une figure. Il suffit donc de montrer que lorsqu'on place des bons parallélogrammes (sans chevauchement) dans une grille \(N \times N\), l'aire vide est au moins \(N\). C'est d'ailleurs équivalent au problème initial, car on retrouve de manière unique la partition en chemins à partir de l'empilement.

Miroirs. Dans chaque case, on trace l'une des diagonales, de sorte qu'elle ne coupe aucun bon parallélogramme. On regarde ces segments comme des miroirs, et l'on envoie un rayon laser par chacune des \(4N\) arêtes du bord (direction initiale perpendiculaire à l'arête), qui rebondit sur les miroirs jusqu'à sortir par une autre arête du bord. Quand un rayon traverse un bon parallélogramme, il rebondit deux fois et reprend sa direction initiale. Donc si la direction finale d'un rayon est perpendiculaire à sa direction initiale, il traverse au moins un triangle vide ; si elle est opposée, il traverse au moins deux triangles vides.

Comptage. On associe l'arête d'entrée d'un rayon à son arête de sortie : les arêtes du bord sont ainsi réparties en \(2N\) paires, de trois types :

1. une arête verticale et une arête horizontale ;
2. deux arêtes du même côté ;
3. deux arêtes de côtés opposés.

Comme les rayons ne se croisent pas, on ne peut pas avoir à la fois une paire de type (3) formée d'arêtes verticales et une paire de type (3) formée d'arêtes horizontales. Quitte à faire une symétrie, supposons qu'il y ait \(t\) paires de type (3), toutes formées d'arêtes verticales. Parmi les arêtes restantes, il y a \(2N\) arêtes horizontales et \(2N - 2t\) arêtes verticales ; il y a donc au moins \(t\) paires de type (2) formées d'arêtes horizontales. Un rayon de type (1) traverse au moins un triangle vide, un rayon de type (2) au moins deux. Comme les rayons ne se croisent pas (et ne traversent donc pas les mêmes triangles), il y a au moins \((2N - 2t) + 2 \cdot t = 2N\) triangles vides dans la grille, soit une aire vide d'au moins \(N\). \(\blacksquare\)

Solution 2

Par récurrence sur \(N\). Le cas \(N = 1\) est trivial. Supposons l'énoncé vrai pour \(N - 1\) et montrons-le pour \(N \geq 2\).

Notons \(P\) le chemin contenant la case en haut à gauche. Si \(P\) est droite-haut, toutes ses cases sont dans la ligne du haut ou dans la colonne de gauche. Par hypothèse de récurrence, au moins \(N - 1\) chemins passent par la sous-grille \((N-1) \times (N-1)\) en bas à droite ; \(P\) n'en fait pas partie, donc il y a au moins \(N\) chemins.

Supposons maintenant \(P\) droite-bas. Si \(P\) contient la case en bas à droite, on obtient une grille \((N-1) \times (N-1)\) en retirant \(P\) et en recollant les deux parties restantes. L'idée est de prolonger \(P\) pour qu'il contienne la case en bas à droite, de sorte que cette procédure donne une partition valide d'une grille \((N-1) \times (N-1)\).

Construction du prolongement \(Q\). On construit pas à pas un chemin droite-bas \(Q\) prolongeant \(P\) ; au départ, \(Q = P\). Soit \(A\) la dernière case de \(Q\), \(B\) la case sous \(A\) et \(C\) la case à droite de \(A\) (si elles existent). Supposons que \(A\) ne soit pas le coin inférieur droit et que

\((\ast)\) ni \(B\) ni \(C\) n'appartient au même chemin que \(A\).

On prolonge alors \(Q\) ainsi (si plusieurs options sont possibles, on en choisit une) :

1. si \(B\) appartient à un chemin droite-bas \(R\), on ajoute à \(Q\) la partie de \(R\) allant de \(B\) à sa fin ;
2. si \(C\) appartient à un chemin droite-bas \(R\), on ajoute à \(Q\) la partie de \(R\) allant de \(C\) à sa fin ;
3. si \(B\) appartient à un chemin droite-haut \(R\) qui se termine en \(B\), on ajoute à \(Q\) la partie de \(R\) située dans la colonne de \(B\) ;
4. si \(C\) appartient à un chemin droite-haut \(R\) qui commence en \(C\), on ajoute à \(Q\) la partie de \(R\) située dans la ligne de \(C\) ;
5. sinon, \(B\) et \(C\) appartiennent au même chemin droite-haut \(R\) ; on ajoute alors à \(Q\) la case \(B\) et la case à droite de \(B\).

Si \(B\) n'existe pas, on est dans le cas 4 ; si \(C\) n'existe pas, dans le cas 3. On vérifie facilement que le prolongement satisfait encore \((\ast)\) ; en répétant, on obtient un prolongement \(Q\) de \(P\) contenant le coin inférieur droit.

Vérification. Montrons qu'en retirant \(Q\) et en recollant les deux parties restantes, on obtient une partition de la grille \((N-1) \times (N-1)\) en chemins droite-bas ou droite-haut. Soit \(R\) un chemin de la partition qui rencontre \(Q\). Si l'intersection provient du cas 1 ou 2, il existe une case \(D\) de \(R\) telle que \(Q \cap R\) soit la partie de \(R\) allant de \(D\) à sa fin : \(R\) reste un chemin droite-bas après le retrait. De même, dans les cas 3 et 4, \(R\) reste un chemin droite-haut. Dans le cas 5, l'intersection est formée de exactement deux cases adjacentes ; après leur retrait, les deux parties de \(R\) se recollent en un chemin droite-haut.

On peut donc appliquer l'hypothèse de récurrence à la partition obtenue de la grille \((N-1) \times (N-1)\) : elle contient au moins \(N - 1\) chemins. Comme \(P\) est contenu dans \(Q\) et ne fait pas partie de ces chemins, la partition initiale contient au moins \(N\) chemins. \(\blacksquare\)