Shortlist 2024, C4

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Hong Kong

Concepts : Jeux et stratégies gagnantes

Solution officielle : Shortlist officielle 2024 (avec solutions), section C4 (livret PDF)

Problème 5 de l'OIM 2024

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2024, où il était le problème 5 (jour 2).

Figures reprises du livret officiel de la Shortlist.

Énoncé

On a board with \(2024\) rows and \(2023\) columns, Turbo the snail tries to move from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then moves one step at a time to an adjacent cell sharing a common side. He wins if he reaches any cell in the last row. However, there are \(2022\) predetermined, hidden monsters in \(2022\) of the cells, one in each row except the first and last rows, such that no two monsters share the same column. If Turbo unfortunately reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move.

Suppose Turbo is allowed to take \(n\) attempts. Determine the minimum value of \(n\) for which he has a strategy that guarantees reaching the last row, regardless of the locations of the monsters.

Indices : les idées clés

• Stratégie contre un adversaire : pour la minoration, les monstres « s'adaptent » aux deux premières tentatives ; pour la majoration, chaque tentative ratée révèle une information exploitable.
• Une ligne entière pour localiser un monstre : la première tentative balaie la ligne 2 et trouve forcément son monstre.
• Un monstre par ligne et par colonne : une fois le monstre d'une ligne (ou d'une colonne) connu, le reste de cette ligne (ou colonne) est sûr ; un chemin en escalier en diagonale oblige le monstre rencontré à être juste à côté d'une case sûre.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (une solution et deux remarques).

Réponse. \(n = 3\).

Solution

Deux tentatives ne suffisent pas. Soit \((2, i)\) la première case de la deuxième ligne atteinte par Turbo lors de sa première tentative. Il peut y avoir un monstre dans cette case ; Turbo retourne alors immédiatement à la première ligne, sans avoir atteint d'autre case au-delà de la première ligne. Soit ensuite \((3, j)\) la première case de la troisième ligne atteinte lors de la deuxième tentative. Turbo y arrive depuis \((2, j)\), donc \(j \neq i\). Il peut donc y avoir un monstre en \((3, j)\) (ce qui est compatible avec le monstre en \((2, i)\)), et Turbo échoue aussi à sa deuxième tentative. Turbo ne peut donc pas être sûr d'atteindre la dernière ligne en \(2\) tentatives.

Une stratégie en trois tentatives. Lors de la première tentative, Turbo suit le chemin

\[(1, 1) \to (2, 1) \to (2, 2) \to \cdots \to (2, 2023).\]

Ce chemin passe par toutes les cases de la deuxième ligne : Turbo trouve donc le monstre de la ligne \(2\), et sa tentative s'arrête.

Si le monstre de la ligne \(2\) n'est pas au bord, c'est-à-dire en \((2, i)\) avec \(2 \leq i \leq 2022\), Turbo emprunte lors des deuxième et troisième tentatives les chemins

\[(1, i-1) \to (2, i-1) \to (3, i-1) \to (3, i) \to (4, i) \to \cdots \to (2024, i),\]

\[(1, i+1) \to (2, i+1) \to (3, i+1) \to (3, i) \to (4, i) \to \cdots \to (2024, i).\]

Les seules cases de ces chemins qui peuvent contenir un monstre sont \((3, i-1)\) et \((3, i+1)\) (la colonne \(i\) ne contient que le monstre de la ligne \(2\), et les autres cases de la ligne \(2\) sont sûres). Une seule au plus de ces deux cases contient un monstre, donc l'un des deux chemins réussit (voir la figure 1).

Si le monstre de la ligne \(2\) est au bord, on peut supposer sans perte de généralité qu'il est en \((2, 1)\). Lors de la deuxième tentative, Turbo suit l'escalier

\[(1, 2) \to (2, 2) \to (2, 3) \to (3, 3) \to \cdots \to (2022, 2023) \to (2023, 2023) \to (2024, 2023).\]

S'il n'y a aucun monstre sur ce chemin, Turbo gagne. Sinon, soit \((i, j)\) la première case où il rencontre un monstre ; on a \(j = i\) ou \(j = i + 1\). Lors de la troisième tentative, Turbo suit le chemin

\[\begin{aligned} &(1, 2) \to (2, 2) \to (2, 3) \to (3, 3) \to \cdots \to (i-2, i-1) \to (i-1, i-1) \\ &\to (i, i-1) \to (i, i-2) \to \cdots \to (i, 2) \to (i, 1) \\ &\to (i+1, 1) \to \cdots \to (2023, 1) \to (2024, 1). \end{aligned}\]

(voir la figure 2). Or :

• les cases de \((1, 2)\) à \((i-1, i-1)\) ne contiennent pas de monstre, car elles ont été atteintes avant \((i, j)\) lors de la tentative précédente ;
• les cases \((i, k)\) pour \(1 \leq k \leq i - 1\) ne contiennent pas de monstre, car il n'y a qu'un monstre dans la ligne \(i\), et il est en \((i, i)\) ou \((i, i+1)\) ;
• les cases \((k, 1)\) pour \(i \leq k \leq 2024\) ne contiennent pas de monstre, car il y a au plus un monstre dans la colonne \(1\), et il est en \((2, 1)\).

Turbo gagne donc lors de la troisième tentative. Le minimum cherché est \(n = 3\). \(\blacksquare\)

Remarques

Remarque 1. L'une des principales difficultés est de trouver la bonne valeur de \(n\) : on peut perdre beaucoup de temps à essayer de prouver des bornes pour une mauvaise valeur avant de trouver de meilleures stratégies. On peut aussi supposer à tort que Turbo n'a pas le droit de repasser par une case déjà visitée au cours d'une même tentative ; cette hypothèse ne change pas la réponse, mais rend la stratégie gagnante un peu plus difficile à trouver.

Remarque 2 (variante quand le monstre de la ligne 2 est au bord). Lors de la deuxième tentative, Turbo peut balayer les lignes une à une :

\[\begin{aligned} &(1, 2023) \to (2, 2023) \to (2, 2022) \to \cdots \to (2, 2) \to (2, 3) \to \cdots \to (2, 2023) \\ &\to (3, 2023) \to (3, 2022) \to \cdots \to (3, 3) \to (3, 4) \to \cdots \to (3, 2023) \\ &\to \cdots \\ &\to (2022, 2023) \to (2022, 2022) \to (2022, 2023) \to (2023, 2023) \to (2024, 2023). \end{aligned}\]

S'il rencontre un monstre, disons en \((i, j)\), il peut, lors de la troisième tentative, descendre directement jusqu'à la case située juste à gauche du monstre, au lieu de refaire le chemin de la deuxième tentative :

\[\begin{aligned} &(1, j-1) \to (2, j-1) \to \cdots \to (i-1, j-1) \to (i, j-1) \\ &\to (i, j-2) \to \cdots \to (i, 2) \to (i, 1) \to (i+1, 1) \to \cdots \to (2023, 1) \to (2024, 1). \end{aligned}\]

(voir la figure 3).