Shortlist 2025, C6

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

Concepts : Graphes : degrés, chemins, arbres · Principe extrémal · Double comptage

Solution officielle : Shortlist officielle 2025 (avec solutions), section C6 (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é

On a \(45 \times 45\) square grid there is an echidna. From any cell, the echidna can move to any other cell that shares a side. The echidna makes a sequence of \(2024\) moves, after which it has visited each cell exactly once. Prove that it is possible to write the numbers from \(1\) to \(2025\), one in each cell, in such a way that:

• For any pair of adjacent cells in the same row, the cell containing the larger number was visited earlier.
• For any pair of adjacent cells in the same column, the cell containing the larger number was visited later.

Indices : les idées clés

• Graphes : degrés, chemins, arbres : on oriente chaque paire de cases voisines vers le plus petit nombre souhaité ; une numérotation existe dès que ce graphe orienté n'a pas de cycle (ordre topologique).
• Argument de séparation (courbe fermée) : le chemin de l'échidné ne se recoupe pas, ce qui interdit certaines configurations locales de flèches autour d'un nœud ou d'une case.
• Principe extrémal (solution 1) : on considère un cycle d'aire minimale et l'on en fabrique un plus petit.
• Double comptage (solution 2) : on place des charges \(\pm 1\) autour des nœuds intérieurs au cycle ; la somme est \(\geq 0\) comptée par nœuds et \(\leq -4\) comptée par cases.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions, précédées de remarques communes).

Remarques communes. On trace une flèche entre deux cases voisines. Si elles sont dans la même ligne, la flèche va de la case visitée le plus tard vers la case visitée le plus tôt ; si elles sont dans la même colonne, c'est l'inverse. Dans les deux cas, on veut que chaque flèche pointe vers le plus petit nombre. Si les flèches ne forment aucun cycle, on peut écrire les nombres en \(2025\) étapes : à la \(i\)-ième étape, on suit les flèches depuis une case non numérotée jusqu'à une case non numérotée qui ne pointe vers aucune case non numérotée, et l'on y écrit \(i\). Il suffit donc de prouver que les flèches ne forment aucun cycle.

On appelle nœud un coin où se rejoignent quatre cases. Les configurations suivantes sont impossibles :

• (a) les quatre flèches autour d'un nœud forment un circuit orienté (et de même pour le circuit en sens inverse) ;
• (b), (c) les quatre flèches d'une case vers ses quatre voisines sont toutes sortantes, ou toutes entrantes.

En effet, notons \(A, B\) (en haut) et \(C, D\) (en bas) les quatre cases autour d'un nœud. Dans la configuration (a), d'après le sens des flèches, l'échidné a visité \(B\) et \(C\) avant \(A\) et \(D\). Le chemin de l'échidné entre \(B\) et \(C\), refermé par un segment diagonal, forme un polygone qui sépare \(A\) de \(D\) ; le chemin entre \(A\) et \(D\) devrait alors couper ce polygone, ce qui est impossible. De même, pour une case \(C\) de voisines \(A\) (en haut), \(B\) (à gauche), \(D\) (à droite) et \(E\) (en bas), dans la configuration (b) l'échidné a visité \(B\) et \(D\) avant \(C\), et \(C\) avant \(A\) et \(E\) ; le chemin entre \(B\) et \(D\), refermé par \(C\), forme un polygone qui sépare \(A\) de \(E\). Même argument pour (c).

On associe à un cycle la courbe fermée formée des segments joignant les centres des cases consécutives du cycle.

Solution 1

Supposons que les flèches forment un cycle, et considérons un cycle \(L\) d'aire minimale (principe extrémal), c'est-à-dire entourant le moins de nœuds possible. Il ne peut pas entourer un seul nœud, car on aurait la configuration (a) ou sa renversée. Il existe donc une case \(C_0\) de \(L\) et une case voisine \(C_1\) telles que la flèche entre \(C_0\) et \(C_1\) soit à l'intérieur de \(L\).

Supposons d'abord que cette flèche aille de \(C_0\) vers \(C_1\). On définit une suite de cases : tant que \(C_i\) est à l'intérieur de \(L\) et n'est pas déjà apparue dans la suite, \(C_i\) a quatre voisines, et ses quatre flèches ne peuvent pas être toutes entrantes. (Précision ajoutée : le livret renvoie ici à la figure (b) ; avec les conventions ci-dessus, ce qui sert est l'impossibilité de quatre flèches toutes entrantes, c'est-à-dire (c) ; dans le cas inverse traité plus bas, c'est (b).) Il y a donc au moins une flèche sortant de \(C_i\), et l'on note \(C_{i+1}\) la case vers laquelle elle pointe. On obtient un chemin orienté ; soit \(C_k\) la dernière case de la suite. Alors \(C_k\) est sur \(L\), ou bien est déjà apparue dans la suite.

• Dans le premier cas, le chemin construit, complété par la portion de \(L\) allant de \(C_k\) à \(C_0\), forme un cycle d'aire plus petite que \(L\).
• Dans le second cas, si \(C_k = C_i\), le chemin de \(C_i\) à \(C_k\) est un cycle entièrement intérieur à \(L\), donc d'aire plus petite.

Dans les deux cas, on contredit la minimalité de \(L\).

Si la flèche entre \(C_0\) et \(C_1\) va de \(C_1\) vers \(C_0\), on procède de même en remontant les flèches : on construit \(C_2, \ldots, C_k\) avec une flèche de \(C_{i+1}\) vers \(C_i\) pour \(1 \leq i < k\), où \(C_k\) est sur \(L\) ou répète une case précédente (cette fois, on utilise que les quatre flèches d'une case ne sont pas toutes sortantes). On aboutit à la même contradiction.

Il n'y a donc aucun cycle. \(\blacksquare\)

Solution 2

Supposons qu'il existe un cycle \(L\). Autour de chaque nœud intérieur à \(L\), on place quatre charges, une sur chacune des quatre cases qui touchent ce nœud. Pour un nœud \(N\) et une case \(C\) qui le touche, on regarde les deux flèches allant de \(C\) vers les deux autres cases voisines de \(C\) autour de \(N\) : si elles pointent toutes deux vers \(C\), ou toutes deux à l'opposé de \(C\), on place une charge \(+1\) sur \(C\) près de \(N\) ; si l'une entre et l'autre sort, on place une charge \(-1\). On obtient une contradiction par double comptage de la charge totale.

Par nœuds. Comme (a) et sa renversée sont interdites, les quatre charges autour d'un nœud ne sont pas toutes négatives. Par parité, il y a un nombre pair de charges négatives autour de chaque nœud. La somme des charges autour de chaque nœud est donc positive ou nulle, et la charge totale aussi.

Par cases. Une case \(C\) intérieure à \(L\) porte quatre charges ; comme (b) et (c) sont impossibles, elles ne sont pas toutes positives ; par parité encore, le nombre de charges négatives est pair, donc la charge totale de la case est négative ou nulle. Si \(C\) est sur \(L\), on distingue les coins convexes, les côtés plats et les coins concaves (cases touchant respectivement \(1\), \(2\) ou \(3\) nœuds intérieurs). Sur un coin convexe, la charge vaut \(-1\). Sur un côté plat, la charge totale vaut \(0\). Sur un coin concave, les trois charges ne peuvent pas être toutes positives, sinon on aurait (b) ou (c) ; la charge totale est donc au plus \(+1\). Or \(L\) est un polygone dont les angles valent \(90°\) et \(270°\) : il a quatre coins convexes de plus que de coins concaves. En sommant sur toutes les cases, la charge totale est au plus \(-4\), ce qui contredit le décompte par nœuds.

Il n'y a donc aucun cycle. \(\blacksquare\)