Baltic Way 1991 · Problem 14
Combinatorics
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).
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Algorithms and processes · Invariants and monovariants
Solutions
Solution
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.