Shortlist 2022, C8¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Serbia
Concepts : Double comptage · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 38 (page 40 du PDF)
Problème 6 de l'OIM 2022
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2022, où il était le problème 6 (jour 2).
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Alice fills the fields of an \(n \times n\) board with numbers from \(1\) to \(n^2\), each number being used exactly once. She then counts the total number of good paths on the board. A good path is a sequence of fields of arbitrary length (including \(1\)) such that:
(i) The first field in the sequence is one that is only adjacent to fields with larger numbers,
(ii) Each subsequent field in the sequence is adjacent to the previous field,
(iii) The numbers written on the fields in the sequence are in increasing order.
Two fields are considered adjacent if they share a common side. Find the smallest possible number of good paths Alice can obtain, as a function of \(n\).
Indices : les idées clés
- Réponse : \(2n^2 - 2n + 1\).
- Compter les chemins selon leur case d'arrivée : le nombre \(B\) de bons chemins finissant en une case est \(1\) pour un « puits », et la somme des valeurs de \(B\) des voisines plus petites sinon.
- Double comptage : la somme des \(B\) des cases non-puits est la somme, sur les paires de cases adjacentes, du \(B\) de la plus petite ; elle vaut donc au moins le nombre \(2n(n-1)\) de paires adjacentes.
- Graphes : degrés, chemins, arbres : l'égalité revient à marquer des cases qui forment un arbre (pour l'adjacence), les cases non marquées étant deux à deux non adjacentes.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2022 (une solution, accompagnée de remarques communes).
Remarques communes du livret. La construction peut se faire de plusieurs façons ; par exemple récursivement, en complétant toute construction pour \(n\) en une construction pour \(n + 1\). Il est aussi naturel de renverser le sens des chemins : un chemin peut alors commencer n'importe où, mais doit finir dans un puits, c'est-à-dire là où on ne peut plus le prolonger. Ce n'est qu'une reformulation, mais elle peut aider l'intuition.
Solution¶
Réponse : \(2n^2 - 2n + 1\).
On appelle puits une case qui n'est adjacente qu'à des cases portant des nombres plus grands ; les autres cases sont des non-puits. Sur un second plateau \(n \times n\), noté \(B\), on écrit dans chaque case le nombre de bons chemins qui finissent sur la case correspondante du plateau original \(A\). On cherche donc la plus petite valeur possible de la somme des cases de \(B\).
Un puits a exactement un bon chemin qui y finit (le chemin réduit au puits). Toute autre case a un nombre de bons chemins y finissant égal à la somme de ces nombres pour ses voisines de valeur plus petite, car un bon chemin ne peut arriver dans une case que depuis une case de valeur plus petite. Ainsi, si l'on remplit \(B\) dans l'ordre croissant des valeurs de \(A\), chaque case non adjacente à une case déjà remplie reçoit \(1\), et chaque case adjacente à des cases déjà remplies reçoit la somme des nombres déjà écrits dans ces voisines.
Minoration. Il y a au moins un puits dans \(A\) : la case portant \(1\). La somme des cases de \(B\) correspondant aux puits vaut donc au moins \(1\). Minorons la somme des cases non-puits. On attribue à chaque paire de cases adjacentes la valeur de \(B\) de sa case de plus petit nombre (dans \(A\)) ; la somme des cases non-puits est alors égale à la somme de ces valeurs attribuées (double comptage). Chacune vaut au moins \(1\), donc la somme des cases non-puits est au moins le nombre de paires de cases adjacentes, soit \(2n(n-1)\). La somme totale est donc au moins
Pour que ce minimum soit atteint, il faut qu'il n'y ait qu'un seul puits et que deux cases de \(B\) de valeur strictement supérieure à \(1\) ne soient jamais adjacentes.
Construction. Montrons que \(2n^2 - 2n + 1\) est atteint. Il suffit de marquer un ensemble de cases (celles qui auront la valeur \(1\) dans \(B\)) tel que deux cases non marquées ne soient jamais adjacentes et que les cases marquées forment un arbre connexe pour l'adjacence. (Précision ajoutée : on numérote alors d'abord les cases marquées, en partant d'une case et en ajoutant à chaque fois une case marquée adjacente à celles déjà numérotées ; comme elles forment un arbre, chacune n'a qu'une voisine déjà numérotée et reçoit \(1\) dans \(B\). On numérote ensuite les cases non marquées, dont toutes les voisines sont marquées. Chaque paire adjacente contribue alors exactement \(1\) et il n'y a qu'un puits.)
Pour \(n = 1\) et \(n = 2\), on marque respectivement l'unique case et un triomino en L. Pour \(n \geq 3\), on repère une case par \((\text{colonne}, \text{ligne})\), et on pose \(s = 2\) si \(n \equiv 0, 2 \pmod 3\) et \(s = 1\) si \(n \equiv 1 \pmod 3\) ; \(k\), \(l\) et \(t\) désignent des entiers positifs ou nuls quelconques.
- On construit d'abord un chemin de cases marquées dans les deux premières colonnes : toutes les cases \((1, i)\) où \(i\) n'est pas de la forme \(6k + s\), et les cases \((2, j)\) où \(j\) est de la forme \(6k + s - 1\), \(6k + s\) ou \(6k + s + 1\). Ce chemin est clairement connexe.
- On considère ensuite les cases \((2, 6k + s)\) et \((1, 6k + s + 3)\). Pour chaque telle case \((i, j)\), on marque toutes les cases \((l, j)\) avec \(l > i\) (le reste de la ligne) et les cases \((i + 2t, j \pm 1)\) (une case sur deux dans les lignes voisines).
On vérifie facilement que les cases marquées ne forment pas de cycle, que les seules cases non marquées sont de la forme \((1, 6k + s)\), \((2 + 2l + 1, 6k + s \pm 1)\) et \((2 + 2l, 6k + s + 3 \pm 1)\), et que deux d'entre elles ne sont jamais adjacentes, car les cases considérées consécutives sont dans des colonnes de parités opposées. Des exemples de marquages pour \(n = 3, 4, 5, 6, 7\), ainsi que les plateaux \(A\) et \(B\) correspondants pour \(n = 5\), sont donnés dans le livret (voir la figure du livret officiel). Par exemple, pour \(n = 5\), le livret propose (lignes de haut en bas)
dont la somme des cases de \(B\) vaut \(41 = 2 \cdot 25 - 10 + 1\). \(\blacksquare\)