와이토프 게임

와이토프의 게임은 2인용 수학적 뺄셈 게임으로, 카운터 2더미와 함께 한다.플레이어는 한 개 또는 두 개 더미에서 카운터를 차례로 제거하며, 양쪽 더미에서 카운터를 제거할 때는 각 더미에서 제거된 카운터 수가 같아야 한다.한 선수가 마지막 카운터나 카운터를 제거하면 게임이 끝나기 때문에 승리한다.

게임에 대한 동등한 설명은 하나의 체스 여왕이 큰 사각형의 격자 어딘가에 배치되어 있고, 각 플레이어는 여왕을 그리드의 왼쪽 하단 구석(남, 서, 남서)으로 이동할 수 있다는 것이다.승자는 여왕을 구석으로 옮기는 선수다.

마틴 가드너는 1977년 3월 사이언티픽 아메리칸에 실린 '수학적 게임' 칼럼에서 이 게임이 중국에서 子子 지엔 시즈("픽 스톤")라는 이름으로 진행되었다고 주장한다.^[1]네덜란드의 수학자 W. A. Wythoff는 1907년에 이 게임의 수학적인 분석을 발표했다.^[2]

최적전략

게임 내의 어떤 포지션도 n ≤ m의 정수(n, m) 한 쌍으로 설명할 수 있으며, 여왕의 위치나 좌표에 있는 양쪽 말뚝의 크기를 묘사한다.이 게임의 전략은 차가운 포지션과 뜨거운 포지션을 중심으로 전개되는데, 차가운 포지션에서는 움직이는 차례가 가장 좋은 플레이로 지는 반면, 뜨거운 포지션에서는 움직이는 차례가 가장 좋은 플레이로 이기는 것이다.핫 포지션에서 최적의 전략은 도달 가능한 콜드 포지션으로 이동하는 것이다.

직위 분류는 다음의 세 가지 규칙을 가지고 재귀적으로 실시할 수 있다.

1. (0,0)은 차가운 자세다.
2. 한 번의 움직임으로 차가운 위치에 도달할 수 있는 어떤 위치도 뜨거운 위치다.
3. 동작 하나 하나가 핫 포지션으로 이어진다면 포지션은 차갑다.

예를 들어, 규칙 2에 의해 m > 0인 형태(0, m)와 (m, m)의 모든 위치가 뜨겁다.그러나 그 위치에서 도달할 수 있는 유일한 위치인 (0,1), (0,2), (1,0), (1,1)가 모두 뜨겁기 때문에 (1,2)는 차갑다.n과 m 값이 가장 작은 콜드 위치(n, m)는 (0, 0), (1, 2, 2), (3, 5), (4, 7), (6, 10), (OEIS의 경우) (시퀀스 A066096 및 A090909) (OEIS: A072061 참조)이다.

이 게임의 미제르 게임은 (0, 1)과 (2, 2)가 콜드 포지션이고, m, n > 2가 있는 포지션(n, m)은 정상 게임에서 (n, m)이 콜드인 경우에만 콜드 포지션이다.

콜드 포지션에 대한 공식

Wythoff는 차가운 위치가 황금 비율에 의해 결정되는 규칙적인 패턴을 따른다는 것을 발견했다.특히 k가 자연수라면

${\displaystyle n_{k}=\lfloor k\phi \llloor =\lllloor m_{k}\phi \phloor -m_{k}\,}$

${\displaystyle m_{k}=\lfloor k\phi ^{2}\lceil n_{k}\lceil \rceil =n_{k}+k\,}$

여기서 φ은 황금비율이고 바닥기능을 사용하고 있는데, (n_k, m_k)은 k cold^th 포지션이다.이 두 시퀀스의 숫자는 각각 OEIS: A000201과 OEIS: A001950으로 온라인 정수 백과사전에 기록된다.

두 시퀀스 n과_k m은_k 방정식과 연관된 Beatty 시퀀스다.

${\displaystyle {\frac {1}{\phi }+{\frac {1}{\phi ^{2}}=1\,.}$

일반적으로 Beatty 시퀀스 쌍에 대해 사실인 것처럼, 이 두 시퀀스는 상호 보완적이다: 각 양의 정수는 두 시퀀스 중 한 번에 정확하게 나타난다.

참고 항목

• 님
• 그룬디의 게임
• 제곱을 빼다
• 와이토프 배열

참조

외부 링크

• Weisstein, Eric W. "Wythoff's Game". MathWorld.
• Grime, James. "Wythoff's Game (Get Home)" (video). YouTube. Brady Haran. Archived from the original on 2021-12-15. Retrieved 21 August 2017.