$ $
풀이. 우선 문제를 수학적 용어로 다시 풀어 써 보자. $n$개의 마을을 $n$개의 점 $a_1,\, a_2,\, \ldots,\, a_n$이라 하고, 이 $n$개의 점으로 이루어진 완전유향그래프(complete digraph)를 생각하자. 이 때, $n$개의 점을 한번씩 모두 지나는 경로
\[ a_{i_{1}} \rightarrow a_{i_{2}} \rightarrow \cdots \rightarrow a_{i_{n}} \]
가 반드시 존재함을 증명하여야 한다. 증명을 위해 $n$에 대한 (강한) 수학적귀납법을 이용하자.
$ $
우선 $n=1$ 또는 $n=2$인 경우 주어진 경로가 존재함은 자명하다. 이제 임의의 $1 \leq k \leq n$에 대하여, 크기가 $k$인 완전유향그래프의 모든 점을 지나는 경로가 언제나 존재한다고 가정하자. 이제 $n+1$개의 점 $a_1,\, a_2,\, \ldots,\, a_n,\, a_{n+1}$로 이루어진 완전유향그래프를 생각해 보자. 그러면 모든 $1 \leq i \leq n$에 대하여, 점 $a_{i}$와 $a_{n+1}$를 연결하는 유향선분이 존재한다. 이제 아래와 같이 두 집합 $A$와 $B$를 정의한다.
\[ A = \set{a_i}{a_i \to a_{n+1}}, \quad B = \set{a_j}{a_{n+1} \to a_j}. \]
그러면 집합 $A$와 $B$는 서로소이이고 $\abs{A} = k$, $\abs{B} = n-k$라 하면 각 집합의 크기는 $n$보다 작거나 같다. 따라서 귀납법 가정에 의하여 집합 $A$와 $B$의 모든 원소들을 연결하는 경로가 각각 존재한다. 이 경로를 각각
\[ a_{i_{1}} \rightarrow a_{i_{2}} \rightarrow \cdots \rightarrow a_{i_{k}}, \quad a_{j_{1}} \rightarrow a_{j_{2}} \rightarrow \cdots \rightarrow a_{i_{n-k}} \]
라 하면,
\[ a_{i_{1}} \rightarrow a_{i_{2}} \rightarrow \cdots \rightarrow a_{i_{k}} \rightarrow a_{n+1} \rightarrow a_{j_{1}} \rightarrow a_{j_{2}} \rightarrow \cdots \rightarrow a_{i_{n-k}} \]
가 우리가 원하는 경로가 된다..