MathDB

14

Part of 1991 Baltic Way

Problems(1)

Knight leaving a castle by visiting its halls

Source:

4/19/2013
A castle has a number of halls and nn 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 2n2n halls (a hall is counted each time it is entered).