Shortlist 2017, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Austria
Concepts : Jeux et stratégies gagnantes · Invariants et monovariants
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 44 (page 46 du PDF)
Problème 3 de l'OIM 2017
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2017, où il était le problème 3 (jour 1).
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Un chasseur et un lapin invisible jouent dans le plan euclidien. Le point de départ \(H_0\) du chasseur coïncide avec le point de départ \(R_0\) du lapin. Au \(n\)-ième tour (\(n \geq 1\)) :
(1) d'abord, le lapin invisible se déplace secrètement, sans être observé, de sa position \(R_{n-1}\) vers un nouveau point \(R_n\) tel que \(R_{n-1}R_n = 1\) ;
(2) le chasseur dispose d'un appareil de pistage (par exemple un chien) qui lui donne une position approximative \(R_n'\) du lapin, telle que \(R_nR_n' \leq 1\) ;
(3) le chasseur se déplace ensuite, de façon visible, du point \(H_{n-1}\) vers un nouveau point \(H_n\) tel que \(H_{n-1}H_n = 1\).
Le chasseur a-t-il une stratégie qui lui garantit qu'après \(10^9\) tours, la distance entre lui et le lapin est inférieure à \(100\) ?
Énoncé original (anglais)
A hunter and an invisible rabbit play a game in the Euclidean plane. The hunter's starting point \(H_0\) coincides with the rabbit's starting point \(R_0\). In the \(n\)-th round of the game (\(n \geq 1\)), the following happens.
(1) First the invisible rabbit moves secretly and unobserved from its current point \(R_{n-1}\) to some new point \(R_n\) with \(R_{n-1}R_n = 1\).
(2) The hunter has a tracking device (e.g. dog) that returns an approximate position \(R_n'\) of the rabbit, so that \(R_nR_n' \leq 1\).
(3) The hunter then visibly moves from point \(H_{n-1}\) to a new point \(H_n\) with \(H_{n-1}H_n = 1\).
Is there a strategy for the hunter that guarantees that after \(10^9\) such rounds the distance between the hunter and the rabbit is below \(100\)?
Indices : les idées clés
- Jeux et stratégies gagnantes : on montre que le lapin (aidé par des signaux défavorables au chasseur) a une stratégie qui met en échec toute stratégie du chasseur.
- Invariants et monovariants : tant que \(d_n < 100\), le lapin peut faire augmenter \(d_n^2\) d'au moins \(\frac12\) tous les 200 tours.
- Rendre le chasseur indécis : le lapin vise l'un de deux points symétriques par rapport à la droite chasseur-lapin, et les signaux restent sur cette droite.
- Calcul précis de distances : \(\varepsilon = 200 - \sqrt{200^2 - 1} > \frac{1}{400}\) et \(\varepsilon^2 + 1 = 400\varepsilon\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (une solution et deux remarques).
Réponse : non, il n'existe pas de telle stratégie pour le chasseur ; c'est le lapin qui « gagne ».
Solution¶
Si la réponse était « oui », le chasseur aurait une stratégie qui marche quels que soient les déplacements du lapin et les positions \(R'_n\) renvoyées par le radar. Nous montrons le contraire : avec des signaux radar malchanceux, aucune stratégie du chasseur ne garantit que la distance reste inférieure à \(100\) pendant \(10^9\) tours.
Soit \(d_n\) la distance entre le chasseur et le lapin après \(n\) tours. Bien sûr, si \(d_n \geq 100\) pour un \(n < 10^9\), le lapin a gagné : il lui suffit de s'éloigner en ligne droite du chasseur, et la distance restera au moins \(100\) par la suite.
Nous montrons que, tant que \(d_n < 100\), quelle que soit la stratégie du chasseur, le lapin peut augmenter \(d_n^2\) d'au moins \(\frac12\) tous les 200 tours (pourvu que les signaux radar lui soient favorables). Ainsi \(d_n^2\) atteindra \(10^4\) en moins de \(2 \cdot 10^4 \cdot 200 = 4 \cdot 10^6 < 10^9\) tours, et le lapin gagne.
Supposons le chasseur en \(H_n\) et le lapin en \(R_n\). Supposons même que le lapin révèle sa position à cet instant (ce qui permet d'ignorer toute l'information des signaux précédents). Soit \(r\) la droite \(H_nR_n\), et soient \(Y_1\) et \(Y_2\) les deux points situés à distance \(1\) de \(r\) et à distance \(200\) de \(R_n\), du côté opposé à \(H_n\).

Le plan du lapin est simple : choisir l'un des points \(Y_1\) ou \(Y_2\) et sauter 200 fois en ligne droite vers lui. Comme tous les sauts restent à distance au plus \(1\) de \(r\), il est possible que tous les signaux radar soient sur \(r\) (le projeté orthogonal de \(R_k\) sur \(r\) convient). Dans ce cas, le chasseur n'a aucun moyen de savoir si le lapin a choisi \(Y_1\) ou \(Y_2\).
Que fait le chasseur face à de tels signaux ? Si sa stratégie lui dit d'avancer 200 tours tout droit vers la droite (le long de \(r\), en s'éloignant de \(H_n\) vers \(R_n\)), il arrive au point \(H'\) de \(r\) tel que \(H_nH' = 200\). Le chasseur n'a pas de meilleure option : après ces 200 tours, sa projection sur \(r\) est toujours à gauche de \(H'\) (ou en \(H'\)). S'il s'est écarté au-dessus de \(r\), il est encore plus loin de \(Y_2\) ; s'il s'est écarté au-dessous, il est encore plus loin de \(Y_1\). Autrement dit, quelle que soit sa stratégie, il ne peut jamais être sûr que sa distance au lapin sera inférieure à \(y := H'Y_1 = H'Y_2\) après ces 200 tours.
Pour estimer \(y^2\), soit \(Z\) le milieu de \([Y_1Y_2]\) (il est sur \(r\)), soit \(R'\) le point de \(r\) à distance \(200\) de \(R_n\) du côté de \(H'\), et posons \(\varepsilon = ZR'\) (remarquons que \(H'R' = d_n\)). Alors
où
En particulier \((200 - \varepsilon)^2 = 200^2 - 1\) donne \(\varepsilon^2 + 1 = 400\varepsilon\), donc
Comme \(\varepsilon > \frac{1}{400}\) et \(d_n < 100\), on a \(400 - 2d_n > 200\), d'où \(y^2 > d_n^2 + \frac12\). Ainsi, comme annoncé, avec cette suite de signaux radar et quoi que fasse le chasseur, le lapin peut obtenir \(d_{n+200}^2 > d_n^2 + \frac12\). Le lapin gagne. \(\blacksquare\)
Remarques¶
Remarque 1. On obtient de nombreuses variantes en remplaçant \(200\) par un autre nombre \(N\) de sauts entre deux révélations. On a alors
donc, tant que \(N > d_n\),
Par exemple \(N = 101\) suffit déjà : le carré de la distance augmente d'au moins \(\frac{1}{101}\) tous les 101 tours, et \(101^2 \cdot 10^4 = 1{,}0201 \cdot 10^8 < 10^9\) tours suffisent au lapin. Si l'énoncé était rendu plus exigeant, certaines de ces variantes pourraient ne plus marcher.
Remarque 2. L'énoncé original demandait si la distance pouvait être maintenue sous \(10^{10}\) pendant \(10^{100}\) tours.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2023 C5 ★★★☆☆ : Elisa ajoute des gemmes, une fée verrouille des coffres : Elisa garde les coffres équilibrés à une constante près.
- 2012 C4 ★★★☆☆ : \(B\) déplace une pièce de chaque boîte, \(A\) corrige : combien de pièces faut-il à \(A\) pour ne jamais laisser de boîte vide ?
- 2009 C5 ★★★☆☆ : La belle-mère verse un litre par tour dans cinq seaux en pentagone, Cendrillon vide deux seaux voisins : un seau peut-il déborder ?
- 2014 C8 ★★★★☆ : On se partage \(1024\) cartes portant des ensembles de chiffres : avec quel premier coup le premier joueur gagne-t-il ?