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é¶
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.