Problems and Solutions #018

Problem #018

어떤 나라에 유한개의 마을이 있다고 하자. 각각의 마을은 일방통행만이 가능한 길로 연결되어 있다. 또한 이 나라의 어떤 두 마을을 선택하더라도 한쪽 마을에서 다른쪽 마을로 가는 길이 존재한다고 하자. (제 삼의 마을을 거쳐서 가는것이 물론 허용된다.) 이 때, 이 나라의 모든 마을을 한번씩 거쳐갈 수 있는 길이 존재함을 증명하여라.

우선 문제를 수학적 용어로 다시 풀어 써 보자. $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}} \]

가 우리가 원하는 경로가 된다.