A castle has a number of halls and $n$ 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 $2n$ halls (a hall is counted each time it is entered).
Problem
Source:
Tags:
mavropnevma
05.01.2014 01:36
Consider the graph having the halls as vertices, plus the "outside" vertex $\Omega$, and the doors as edges. Since the knight does enter the castle, it means $\deg \Omega \geq 1$, and $\deg h \geq 2$ for all halls $h$. Let $h_1$ be the hall entered. Consider any path $P$ starting at $h_1$ (with no repeating vertices, thus no repeating edges). If $\Omega$ appears in the path, the knight would have exited the castle after visiting at most $n-1$ halls. If not, there will be a moment when the path ends at some hall $h_m$, since any new door from $h_m$ will enter some hall $h_k$ already visited, for some $1\leq k \leq m-2$. But then the knight may follow the walk $W = h_1h_2\ldots h_mh_kh_{k-1}\ldots h_2h_1\Omega$. There are $k + (m-k+1) = m+1$ different doors involved, so $m\leq n-1$, and there are $2k + (m-k) = m+k \leq 2m-2 \leq 2n-4$ halls visited. Thus, with no strategy other than obeying the rules, the knight exits the castle after visiting at most $\max\{n-1, 2n-4\}$ halls.