토큰 다섯 개가 남았고 한 번에 1개나 2개를 가져가요. 마지막 토큰을 가져간 사람이 진다. 내게만 한 번 차례를 쉬는 권한이 있다면, 바로 써도 이길까요? 권한이 있다는 것과 지금 쓰는 것이 좋은 선택인지는 달라요.
다음은 직접 정한 게임 규칙이에요. n개 토큰에서 두 사람이 번갈아 1개부터 min(k,n)개를 가져가요. n,k는 양의 정수예요. 자기 권한을 하나 써서 아무것도 가져가지 않고 차례를 넘길 수도 있어요. 현재 차례인 사람의 남은 권한을 r, 상대의 남은 권한을 s로 놓아요. 둘 다 0 이상의 정수예요. 서로의 권한을 쓸 수 없고 모든 상태는 공개되어 있어요. 마지막 토큰을 가져가면 즉시 져서, 그 뒤에는 쉬기 권한을 쓰지 못해요. 무작위나 실제 참가자의 반응은 넣지 않았어요.
상대가 어떻게 두어도 이길 전략이 있는 상태를 W, 그렇지 않은 상태를 L이라 해 볼까요? 오래 쉬기만 하여 끝나지 않을까 걱정할 필요는 없어요. 다음 합은 가져가거나 쉬는 모든 차례에 적어도 1 줄어들어요.
따라서 유한 번에 승패가 정해져요. 모든 시작의 결과는 다음과 같아요.
| 현재 사람과 상대의 남은 권한 | 현재 사람이 이길 수 있나요? |
|---|---|
| r>s | 남은 토큰 수와 관계없이 가능 |
| r<s | 상대가 제대로 두면 불가능 |
| r=s | n을 k+1로 나눈 나머지가 1이면 불가능, 그 밖에는 가능 |
왜 권한이 하나만 더 있어도 모든 n에서 이길까요? 토큰이 2개 이상이면 하나를 가져가면 돼요. 다음 사람이 더 적은 권한을 가진 상태가 돼요. 하나만 남았다면 가져가는 대신 쉬어서 상대에게 그 하나를 넘긴다. 상대의 권한이 더 적거나 같아지고, 권한이 같고 하나만 남은 상태에서는 차례를 받은 상대가 결국 진다.
이 설명을 단순한 느낌으로 끝내지 않으려면 순서를 정해야 해요. 합 M 이하의 모든 상태가 표와 같다는 명제로 수학적 귀납법을 써요. M=1인 n=1,r=s=0은 바로 진다. 더 작은 합의 결과를 안다고 놓으면 위의 이동 뒤 상태도 모두 그 안에 있어요. r<s인 사람의 비종료 제거와 쉬기는 상대에게 더 많은 권한을 줘요. 마지막 토큰을 가져가는 선택도 지므로 피할 길이 없어요.
권한이 같으면 쉬는 쪽이 상대에게 더 많은 권한을 넘겨주어 상대를 이길 수 있게 만들어요. 가져가는 선택만 남겨 보면, 익숙한 마지막 토큰 패배의 나머지 규칙이에요. n이 1 mod q이면 1개부터 k개를 제거한 나머지는 그 값이 아니어서 상대가 이길 수 있어요. 그 밖의 n에서는 n−1의 q 나머지만큼 가져가면 상대에게 1 mod q인 양을 남겨요. 마지막 하나를 직접 가져가지 않는 범위도 함께 맞아요. 이를 작은 M에서 큰 M으로 반복하면 표의 모든 경우가 증명돼요.
이제 이길 수 있는 상태에서 첫 선택을 골라 봐요. r>s이면 마지막 토큰을 남기는 모든 제거가 승리 행동이에요. 하지만 쉬기도 좋은 선택이려면 다음 조건이 필요해요.
두 권한의 차가 2 이상이면 한 번 쉬어도 상대보다 많이 남아요. 차가 정확히 1이면 쉬는 순간 같아지므로, 상대에게 패배 나머지를 줄 때만 좋아요. 권한이 같은 W 상태에서 승리하는 제거는 다음 한 가지이고, 쉬기는 승리 행동이 아니에요.
처음 예에서 1개를 가져가면 상대는 4개와 권한 0·1, 2개를 가져가면 3개와 권한 0·1을 받아요. 둘 다 상대가 이길 수 없는 상태예요. 바로 쉬면 상대는 5개와 권한 0·0을 받아요. 상대가 1개를 가져가면 내게 4개를 남기고, 나는 더 쉬지 못해 진다. 반대로 한 개만 남고 나에게만 한 번 권한이 있으면, 쉬는 선택만 이겨요. 좋은 권한도 사용하는 시점이 달라요.
교사는 토큰 수만 적은 표 옆에 두 사람의 남은 권한도 적게 해요. 이길 전략이 존재하는 상태의 진리집합과 실제로 이기는 첫 선택의 집합을 구별하는 거예요. 몇 번의 성공 게임을 모든 상태의 증명으로 바꾸지 않고, 매번 줄어드는 M을 귀납의 기준으로 쓰게 해요. 제공 교재의 귀납법과 진리집합은 이 논증의 표현 근거이며 개인 권한 게임의 분류 정리를 제공한 것은 아니에요.
착안: Pacific Science Center, Curiosity at Home: Game of Nim, Explore More. 원문에서 한 줄의 토큰을 제한된 수만큼 가져가고 마지막 토큰을 가져간 쪽이 지는 배경만 참고했어요. 개인별 쉬기 권한·모든 상태와 첫 선택의 분류는 자체 교육용이며 원문의 게임 진행도나 역사 서술, 실제 수업 효과를 옮긴 것이 아니에요.