Balti Tee 1991 · Ülesanne 14
Kombinatoorika
A castle has a number of halls and doors. Every door leads into another hall or outside. Every hall has at least two doors. A knight enters the castle. In any hall, he can choose any door for exit except the one he just used to enter that hall. Find a strategy allowing the knight to get outside after visiting no more than halls (a hall is counted each time it is entered).
Kui oled valmis
Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.
Ülevaade
Teemad
Algoritmid ja protsessid · Invariandid ja monovariandid
Lahendused
Lahendus
Solution:
The knight can use the following strategy: exit from any hall through the door immediately to the right of the one he used to enter that hall. Then, knowing which door was passed last and in which direction we can uniquely restore the whole path of the knight up to that point. Therefore, he will not be able to pass any door twice in the same direction unless he has been outside the castle in between.