체스에서도 그렇다. 바로 Knight’s Tour라는 문제이다.

우리에게 친숙한 한붓그리기와 살짝 비슷하고, 만일 그래프에 대해서 배운 학생이 있다면, Hamilton Cycle과 같음을 알 수 있을 것이다. 이번 글에서 Knight’s Tour의 해답이 유한개의 경우를 제외한 모든 짝수 n에 대해서 가능함을 보이고, 수학의 한 분야인 Graph Theory를 소개하려 한다. 증명의 아이디어는 굉장히 간단하지만, 이를 엄격하게 증명하는 과정에서 조금은 생각해 보고 검증할 부분들이 다수 존재하기 때문에 살짝 복잡하게 느껴질 수 있다. 따라서 증명을 완벽하게 이해하는 데 초점을 두기보다, 수학에 이런 분야도 있고 Knight’s Tour를 이런 방식으로 정복할 수 있다는 정도만 알아두면 좋을 것 같다. 그럼 시작해 보자!


지금부터 우리가 증명할 Theorem이다. 우리는 $n × n$에 대해서 Knight’s Tour를 고려하지만, 이보다 좀 더 일반적인 $m × n$에 대해서 증명하려고 한다. 먼저 해당 Theorem의 결과에 대해서 먼저 이야기하자. (a)와 (b)에 따르면, $1 × 1$, $2 × 2$, $3 × 3$, $4 × 4$ 그리고 홀수 × 홀수를 제외한 짝수 $n$에 대해서는 항상 Knight’s Tour의 경로를 찾을 수 있다. 놀랍지 않은가? 체스 게임에 사용하는 실제 체스 보드는 $8 × 8$이므로 Knight’s Tour가 가능하다! 증명의 전체적인 틀은 우선 (a), (b) 그리고 (c)의 조건을 만족할 때, Knight’s Tour가 불가능함을 보이고, 이를 제외한 짝수 × 짝수에 대해서는 Knight’s Tour가 가능함을 귀납적으로 증명하는 것이다. 불가능한 경우의 증명은 생략하고, 짝수 × 짝수의 보드에 대해서만 증명의 스케치를 하겠다. 이를 위해서는 보조 정리(Lemma)가 필요하며 다음과 같다.


그렇다면, $G(m, n + 4)$또한 Hamilton Cycle을 가지며, 다음 10개의 Edges(선)를 포함한다.
$(1, n+ 3)- (3, n + 4)$, $(m - 2, n+ 3)- (m, n+ 4)$, $(m -1, 1)- (m, 3)$,
$(m -1, n+ 2)- (m, n + 4)$, $(4, n+ 3)- (2, n + 4)$, $(1, n+ 4) - (3, n + 3)$,
$(m -2, n+ 4) - (m, n + 3)$, $(m, 1)- (m-1, 3)$,
$(m, n+ 2) - (m - 1, n+ 4)$, $(m, 2) - (m- 1, 4)$.

이 정리를 이해하기 위해서는 Graph에 대해 조금 알아야 한다. Graph에는 여러 종류가 있지만, 가장 일반적인 Simple Graph는 점들과 선들로 이루어진 집합을 의미한다. 선은 각 두 점을 연결하며, 이때 하나의 점에서 시작하여 그 점으로 끝나는 선은 없으며 두 점은 항상 한 개의 선으로만 연결되어야 한다. 자! 여기서 이제 놀라운 아이디어가 펼쳐진다! Knight’s Tour를 Graph로 옮기는 것이다. 각 점은 체스 보드의 한 칸과 대응하고, 선은 Knight가 움직일 수 있는 경로를 표시한다. Fig. 1은 $3 × 3$ 보드를 Graph로 대응시킨 그림이다. Lemma에서 사용한 표기법은 Fig. 1에 표현되어 있다. $m × n$ 보드를 이처럼 Graph로 옮긴 것을 $G(m, n)$라 한다. 그리고 Hamilton Cycle이란 한 그래프에서 선을 최대 1번씩만 지나며, 시작점과 끝점을 제외한 모든 점을 정확히 한 번씩 지나 다시 처음 위치로 돌아오는 경로를 말한다. 따라서 Problem은 $G(m, n)$에서 Hamilton Cycle을 찾는 문제로 정확히 치환된다.


이제 Lemma를 증명해 보자. 실제 증명을 보여 주기보다 $G(5, 6)$으로부터 $G(5, 10)$을 증명하는 과정을 Sketch하듯이 보여 주고자 한다. 우선 $G(5, 4)$로부터 $H(5, 4)$라는 Graph를 만든다.$G(5, 4)$에서 1) 2열과 3열을 연결하는 모든 선을 제거한다. 2) 두 개의 열만큼 떨어져 있는 점들을 연결하는 선들은 제거한다. 이때 1행과 2행, 4행과 5행에 있는 점들은 제외한다. 이렇게 만들어진 그래프를 $H(5, 4)$라 한다. 그러면 놀랍게도 $H(5, 4)$의 모든 점은 각각 단 두 개의 선만 가지며, 길이 10짜리 2개의 Cycle로 이루어져 있다(why?). 이제 $G(5, 6)$의 Hamilton Cycle에 $H(5, 4)$를 연결하여 $G(5, 10)$의 Hamilton Cycle을 만들어 낼 것이다. Fig. 2를 보자. $G(5, 6)$의 Hamilton Cycle과 $H(5, 4)$가 등장한다. $G(5, 6)$의 Hamilton Cycle에서 $(1, 6) - (3, 5)$와 $(2, 6) - (4, 5)$를 제거하고, $H(5, 4)$에서 $(1, 8) - (3, 7)$와 $(2, 8) - (4, 7)$를 제거한다. 그다음 Hamilton Cycle과 $H(5, 4)$사이에 $(1, 6) - (2, 8)$, $(2, 6) - (1, 8)$, $(3, 5) - (4, 7)$, $(4, 5) - (3, 7)$을 연결한다. 이렇게 만들어진 Graph는 $G(5, 10)$에서 Hamilton Cycle을 가지는 그래프가 된다. 그리고 만들어진 Graph는 Lemma에 적힌 10개의 선(Edges)을 가져, Lemma가 증명된다(why?).

이제 마지막 아이디어의 핵심을 설명하겠다. 앞서 말했듯이, Theorem을 귀납적인 방법으로 증명한다. 즉, Lemma에 의해서 $G(m, n)$이 Hamilton Cycle을 가진다면, $G(m, n + 4)$ 역시 Cycle을 가진다. 그렇다면, 특정 초기 보드들에 대해서 Knight’s Tour가 가능함만 보인다면, 귀납법에 따라서 증명이 끝이 난다(why?). 따라서 Theorem을 증명하기 위해 우리가 검토해야 하는 것은 초기 보드들이 $m, n = 1, 2, 3$ or $4$일 때 $G(m, n)$이 Hamilton Cycle을 가짐을 보이는 것이다. 물론 Theorem에 적혀있듯이 (a), (b), (c)의 불가능한 경우를 제외한 나머지 9개에 대해서만 성립함을 보이면 된다. Fig. 3이 이 9개들이 Hamilton Cycle을 가진다는 것을 보여준다. 따라서 $n × n$ 체스 보드가 있을 때, $1 × 1$, $2 × 2$, $3 × 3$, $4 × 4$ 그리고 홀수 × 홀수를 제외한 짝수 $n$에 대해서는 항상 Knight’s Tour의 경로를 찾을 수 있다.

누군가는 체스에서 패배하게 되면 눈물을 흘린다. 어떤 이는 고작 체스에 눈물이 떨어지는 것을 이해하지 못한다. 우리는 눈물을 흘릴 만큼 이토록 우리에게 소중한 무언가가 있는지, 눈물을 이해하지 못할지언정, 우리는 눈물을 흘린 사람보다 못나다. 누군가는, 어떤 이는, 우리는 심지어 Knight는 Tour를 끝낼 수 있을지 알지 못하지만, 한 칸 또 앞으로 간다.

이번 호 MARCUS 글을 흥미롭게 읽었다면 다음 문제를 풀어보는 건 어떨까요?



이번 호 문제는 2022년 2월 28일(월)까지 알리미 E-MAIL(postech-alimi@postech.ac.kr)로 풀이와 함께 답안을 보내주세요.
정답자가 많을 경우 간결하고 훌륭한 답안을 보내 주신 분들 중 추첨을 통하여 포스텍의 기념품을 보내 드립니다.
(학교/학년을 꼭 적어 주세요.)