위토프 게임(이)란?
위토프 게임은 두 더미로 합니다. 차례에는 님처럼 한 더미에서 원하는 만큼 가져가거나, 두 더미에서 동시에 같은 수를 가져갑니다. 마지막 물건을 가져간 사람이 이깁니다. 이 게임은 항상 일반 규칙으로 하므로 표준 게임의 미제르 설정과 시작 더미 옵션은 적용되지 않습니다.
더미 크기는 테이블 설정의 크기 옵션에서 정해집니다: 5와 7(작게), 9와 12(보통, 기본값), 14와 20(크게). 이 게임을 떠올리는 잘 알려진 방법은 왼쪽, 아래, 왼쪽 아래 대각선으로만 움직일 수 있는 체스 퀸입니다. 두 더미는 판의 두 가장자리에서 퀸까지의 거리이며, 퀸을 구석으로 옮기는 사람이 이깁니다.
규칙 변경
| 규칙 | 표준 님 | 위토프 게임 |
|---|---|---|
| 더미 | 표준 님여러 더미: 기본값 1, 3, 5, 7개, 또는 테이블 설정에서 고른 다른 조합. | 위토프 게임두 더미: 5와 7, 9와 12(기본값), 14와 20. 테이블 설정의 크기로 고릅니다. |
| 수 | 표준 님한 더미에서 하나 이상 가져갑니다. | 위토프 게임한 더미에서 하나 이상 가져가거나, 두 더미에서 같은 수를 가져갑니다. |
| 목표 | 표준 님기본값은 미제르: 마지막 물건을 가져간 사람이 집니다. 설정에서 마지막 물건을 가져가면 이기는 일반 규칙으로 바꿀 수 있습니다. | 위토프 게임항상 일반 규칙: 마지막 물건을 가져간 사람이 이깁니다. |
| 필승법 | 표준 님더미의 님 합(크기의 비트 XOR)을 0으로 만들어 넘깁니다. 미제르 종반에는 변형이 있습니다. | 위토프 게임차례인 사람이 지는 국면은 1과 2, 3과 5, 4와 7, 6과 10, 8과 13 같은 쌍입니다. k번째 쌍은 k × φ와 k × φ²의 정수 부분이며, φ는 황금비입니다. 여기의 시작 국면은 어느 것도 그런 쌍이 아니므로 선수가 이길 수 있습니다. |
역사
네덜란드 수학자 빌렘 아브라함 위토프는 1907년 Nieuw Archief voor Wiskunde에 실린 논문 「A modification of the game of nim」에서 이 게임과 해법을 발표했습니다. 그는 지는 국면이 황금비를 따른다는 것을 보였습니다. 지는 쌍의 작은 수와 큰 수는 두 베아티 수열을 이루며, 둘을 합치면 모든 양의 정수를 정확히 한 번씩 나열합니다. 그래서 이 게임은 게임에 관한 글뿐 아니라 정수론 글에도 등장합니다.
마틴 가드너는 1977년 3월 잡지 칼럼 '수학 게임'에서 이 게임을 다루며, 중국에서 jiǎn shízǐ, 즉 '돌 줍기'라는 이름으로 했다고 썼습니다. 이 주장의 다른 출처는 알려져 있지 않습니다.