그룬디의 게임

그룬디의 게임은 2인칭의 수학적 전략 게임이다.출발 구성은 한 무더기의 오브젝트인데, 두 플레이어는 한 힙을 서로 다른 크기의 두 무더기로 번갈아 나눈다.이 게임은 크기가 2 이하인 무더기만이 남아 있을 때 끝나는데, 그 중 어느 것도 똑같이 분할할 수 없다.이 게임은 보통 일반적인 플레이 게임으로 진행되는데, 이것은 허용된 동작을 할 수 있는 마지막 사람이 이긴다는 것을 의미한다.

삽화

8의 단일 힙으로 시작하는 일반적인 플레이 게임은 첫 번째 플레이어가 힙을 7과 1의 힙으로 나누는 것으로 시작할 경우 승리하는 것이다.

선수 1:8 → 7+1

이제 플레이어 2에는 7-heap을 6 + 1, 5 + 2 또는 4 + 3으로 나누는 세 가지 선택이 있다.이러한 각각의 경우에, 플레이어 1은 다음 동작에서 4사이즈 더미에 2사이즈 더미 및 더 작은 사이즈 더미를 상대방에게 돌려주도록 할 수 있다.

2:7+1 → 6+1+1 플레이어 2:7+1 → 5+2+1 플레이어 2:7+1 → 4+3+1 플레이어 1:6+1+1 → 4+2+1 플레이어 1:5+2+1 → 4+1+1 플레이어 1:4+3+1 → 4+2+1 플레이어 1

이제 2번 선수는 4-heap을 3+1로 나누고, 1번 선수는 3-heap을 2+1로 나누어야 한다.

2: 4+2+1+1 → 3+1+2+1+1+1 플레이어 1: 3+1+2+1 → 2+1+1 플레이어 2는 움직임이 남아 있지 않고 패한다.

수학 이론

이 게임은 스프래그-그룬디 정리를 사용하여 분석할 수 있다.이를 위해서는 게임의 힙 크기를 동일한 님 힙 크기에 매핑해야 한다.이 매핑은 온라인 정수 시퀀스 백과사전에서 OEIS: A002188:

힙 크기: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20 ...등가 Nim 힙 : 0 0 0 1 2 0 2 2 1 2 2 3 2 3 4 3 0 ... 

이 매핑을 이용하면 게임 님 플레이 전략을 그룬디의 게임에도 활용할 수 있다.그룬디의 게임의 일련의 님-값들이 과연 주기적인 것이 될지는 아직 풀리지 않은 문제다.엘윈 베를레캄프, 존 호튼 콘웨이, 리처드 가이 등은 그 순서가 결국 주기적인 것이 된다고^[1] 추측해 왔지만, 아킴 플램멘캄프의 처음³⁵ 두 값을 계산했음에도 불구하고 그 문제는 해결되지 않았다.

참고 항목

• 님
• 스프래그-그룬디 정리
• 와이토프 게임
• 제곱을 빼다

참조

외부 링크

• 그룬디의 수학월드 게임
• A에 의한 그룬디 게임의 스프래그그-그룬디 값.플램멘캄프