이번 시험 문제였는데 제가 맞게 증명한 건지 알고 싶습니다.
강의 중에 비슷한 문제도 없었는데 나와서 조금 멘붕이... 소설 쓰는 느낌으로 지었습니다.
게다가 시험이 문답 모두 영어라 방법이 맞아도 틀리다고 채점될 가능성조차 있습니다(...)

문). N이 홀수일 경우, NxN 체스판에서 나이트가 어떤 위치에서 출발하여 모든 칸을 한 번씩 방문하고 원래 위치로 돌아오는 방법이 없음을 증명하라.


제 해답)
체스판 위에서 해밀토니안 사이클이 존재하는지 확인해야 한다.
나이트는 검은 칸에서 흰 칸으로, 흰 칸에서 검은 칸으로 이동한다.

그러므로 이러한 사이클이 존재한다면 나이트의 이동 경로는

검0 -> 흰0-> 검1 -> 흰1 -> ... -> 검X -> 흰X -> 검0
과 같은 형태가 될 것이다.

그런데 N이 홀수인 경우, 체스판 위의 검은 칸은 흰 칸보다 1개 더 많게 된다.

이렇게 되면 흰색이 검은 색에 비해 모자라므로
경로의 마지막 부분이

흰X-1 -> 검X -> 검0 이 되어야 한다.

나이트는 검은 칸에서 검은 칸으로 이동할 수 없으므로 이는 모순이다.

따라서 N이 홀수인 경우 그러한 경로는 존재할 수 없다.