Chomp 게임과 힐베르트의 정리

두 좌표가 0 이상인 정수인 모든 점들을 생각한다. 남아있는 점들 중 한 점을 잡아, 이 점보다 두 좌표가 크거나 같은 (즉 상대적으로 우상단에 있는) 모든 점들을 없애는 스텝을 되풀이할 때, 어떻게 해도 유한번 안에 모든 점을 없애게 된다.

Fibonacci Freak에서 소개된 문제. Chomp란 이름의 게임이 있는데, 유한한 직사각형 모양의 점들에서 위에서 묘사한 시행을 되풀이하여 마지막으로 점을 없애는 사람이 지는 게임이다. 여기에서 처음에 점이 양쪽 좌표로 양의 방향으로 무한히 주어지게 되는 배리에이션 역시 유한게임임을 말하는 셈이 된다. 이 문제를 Hilbert’s basis theorem을 이용해 매우 간단하게 증명하는 방법이 있다.

귀류법 가정으로 문제에서 주어진 시행을 무한히 계속 할 수 있다고 가정한다. 먼저 점 에 단항식 를 부여한다. 그리고 에서의 ideal인 을 생각한다. 여기서 에 대해 문제에서 설명한 시행을 행하는 것은, 에 ideal 를 더하는 과정으로 볼 수 있다. 즉 가 지워져있는 것과 가 에 속하는 것이 동치가 된다. Hilbert’s basis theorem에 의해 는 Noetherian ring이고 이는 즉 앞의 ideal을 포함하는 또 다른 ideal을 잡는 chain을 잡으면 어느 시점부터는 계속 동일한 ideal로 일정하게 나온다는 것을 의미한다. 즉 앞에서처럼 계속 를 로 업데이트하다보면 어느 순간부터 는 계속 일정하게 유지되어야 한다. 그러나 시행을 무한히 계속 할 수 있다는 귀류법 가정에 의해 는 계속 strictly 커져야 하므로 모순이 되어 증명이 끝난다.

Hilbert’s basis theorem에 의해 역시 Noetherian ring이므로, 2차원에서 차원으로 일반화하는 것도 쉽게 가능하다.

또한 위 문제는 엄상일 교수님께서 말씀하신 바와 같이 well-quasi-order의 곱이 역시 well-quasi-order란 결과를 이용해서도 보일 수 있다. well-quasi-order는 집합에 대소관계가 주어져있을 때 를 잡으면 반드시 인 가 존재하는 경우를 뜻하는데, 일반적인 정수의 대소관계를 지닌 이 well-quasi-order이므로 그 곱인 위에서 주어진 집합 역시 well-quasi-order이다. 따라서 무한히 계속 할 수 있다면 를 계속 잡아야 하는데 그 과정에서 언젠가 인 를 잡게 되므로 모순이 된다.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2017/10/25)

43. 두 좌표가 0 이상인 정수인 모든 점들을 생각한다. 남아있는 점들 중 한 점을 잡아, 이 점보다 두 좌표가 크거나 같은 (즉 상대적으로 우상단에 있는) 모든 점들을 없애는 스텝을 되풀이할 때, 어떻게 해도 유한번 안에 모든 점을 없애게 된다. pic.twitter.com/dGIOwjyRy0

— Elegant Math (@elegant_math) October 25, 2017