Exercice 1 — Un « compte» de fée

Sujet

La princesse Clara veut épouser le fils du roi Pierre le M agnifique. Le roi s'oppose au mariage. II enferme son fils dans une chambre de son château et propose à la princesse le marché suivant :
«Tu n'entreras pas dans le château mais, à partir du premier jour du mois, chaque jour tu pourras faire ouvrir les fenêtres d'une chambre de ton choix. Si le prince mon fils est dans cette chambre, vous vous marierez. Sinon, les fenêtres se refermeront, et tu devras attendre le lendemain pour recommencer. Entretemps, j'aurai fait déplacer mon fils dans une chambre voisine. Si, à la fin du mois, tu ne l'as pas trouvé, tu devras partir immédiatement sans te retourner ».

1. Si le château ne possède que trois chambres disposées selon le schéma ci-contre,

prouver que la princesse peut trouver le prince en deux jours au plus.
2. Le château possède en réalité 17 chambres disposées selon le schéma

a. Dans cette question uniquement, on suppose que Clara sait que le prince est initialement dans une chambre de numéro pair. Donner une liste de 15 essais qui permettront à Clara d'atteindre son objectif quels que soient les déplacements ordonnés par le roi.
b. Prouver que si la princesse a tout le mois de juin pour trouver le prince, ils se marieront.
3. Dans la même configuration (17 chambres), Clara a décidé à l'avance d'une suite de choix de chambres. Les espions du roi ont connaissance de cette suite, et en informent le roi.
a. Prouver que si, malgré tout, Clara trouve le prince, elle aura fait ouvrir au moins deux fois les fenêtres de chaque chambre autre que les extrêmes 1 et 17.
b. Prouver que le roi peut empêcher le mariage si l'épreuve débute le \(1^{\text {er }}\) février.
4. N'ayant pas pensé à la solution précédente, le roi imagine d'enfermer son fils dans un château plus vaste, et dont le plan est plus compliqué. En voici le plan, où figurent les 21 chambres et les couloirs permettant les communications :

Y a-t-il une stratégie permettant à Clara de trouver son prince, malgré les espions du roi et quel que soit le mois qu'il aura choisi ?