Chomp 게임과 힐베르트의 정리

Source: http://fibonacci-freak.hatenablog.com/entry/2017/10/20/113016

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

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

Source: http://fibonacci-freak.hatenablog.com/entry/2017/10/20/113016

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

Hilbert’s basis theorem에 의해 \mathbb{C}[x_1,\ldots,x_n] 역시 Noetherian ring이므로, 2차원에서 n차원으로 일반화하는 것도 쉽게 가능하다.

또한 위 문제는 엄상일 교수님께서 말씀하신 바와 같이 well-quasi-order의 곱이 역시 well-quasi-order란 결과를 이용해서도 보일 수 있다. well-quasi-order는 집합에 대소관계가 주어져있을 때 x_1, x_2, \ldots를 잡으면 반드시 x_i \leq x_ji<j가 존재하는 경우를 뜻하는데, 일반적인 정수의 대소관계를 지닌 \mathbb{Z}_{\geq 0}이 well-quasi-order이므로 그 곱인 위에서 주어진 집합 역시 well-quasi-order이다. 따라서 무한히 계속 할 수 있다면 (x_1,y_1),(x_2,y_2),\ldots를 계속 잡아야 하는데 그 과정에서 언젠가 x_i \leq x_j,y_i \leq y_ji<j를 잡게 되므로 모순이 된다.

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

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중