먼저 규칙 확인부터 하겠습니다. 제가 이해한 게임 규칙은 다음과 같습니다. 맞으면 그대로 따라하세요.
- 바둑돌 한 무더기에서 두 사람이 번갈아가며 한 번에 3개, 5개, 또는 7개 중 하나를 가져간다.
- 마지막 돌을 가져가는 사람이 이긴다(정상형 규칙).
(다른 규칙이면 알려주세요. 규칙이 바뀌면 전략도 달라집니다.)
핵심 결론(한 줄 요약)
- 남은 돌 수 n에 대해 n mod 10 가 0,1,2 이면 그 위치는 패(두는 사람은 필패).
- 그 외의 나머지(3,4,5,6,7,8,9)면 현재 두는 사람이 한 수로 n을 10k+0,1,2(=10의 블록의 처음 3칸)로 만드는 수(3,5,7 중 하나)를 두어 필승을 만들 수 있다.
전략(실전용)
- 시작할 때 n mod 10 ∈ {0,1,2}이면 선공은 필패(상대가 정확히 대응하면 무조건 진다). 반대로 n mod 10 ∉ {0,1,2}이면 선공이 필승 가능.
- 항상 상대에게 돌 개수를 10k + r (r = 0,1,2)인 상태로 남기도록 두세요. 즉, 당신의 수가 끝난 뒤 남은 돌 수가 0,1,2 (mod 10)이 되게 만드세요.
- 구체적인 한 수 규칙(현재 n mod 10 값에 따른 제거 수):
- n mod 10 = 3 또는 4 → 3개를 가져간다.
- n mod 10 = 5 또는 6 → 5개를 가져간다.
- n mod 10 = 7, 8, 9 → 7개를 가져간다.
- n mod 10 = 0,1,2 → (이 경우는 패 위치이므로) 상대가 실수하지 않으면 이길 수 없다.
- 이 전략을 유지하면 상대가 어떤 수(3,5,7)를 가져가든 당신이 다음 수로 반드시 10k + {0,1,2} 상태를 다시 만들 수 있고, 결국 마지막 돌을 가져가 승리합니다.
간단한 예
- 처음 돌이 37개이면 37 mod 10 = 7 → 선공(당신)은 7개를 가져가 30개로 만든다(30 ≡ 0 mod 10). 이후 상대가 3,5,7 중 하나를 가져가면(예: 상대가 5를 가져가 25가 되었다면) 당신은 5를 가져가 20으로 만들고(20 ≡ 0), 같은 방식으로 승리를 유지할 수 있다.
- 처음 돌이 42개이면 42 mod 10 = 2 → 선공은 패. 선공이 아무 수를 가져가도 후공이 위 규칙으로 응수하면 결국 선공이 패배한다.
간단한 증명(직관)
- 0,1,2는 더 이상 둘 수 있는 수(3,5,7)가 없어 패(P)이다.
- 어떤 수 m이 P라면 m+s(3,5,7)인 수는 모두 N(이기는 위치)이다(한 수로 P로 보낼 수 있으므로). 반대로 모든 m에서 가능한 수들이 모두 N이면 그 m은 P. 위 계산을 해보면 P는 블록 단위로 10간격으로 반복되어 0,1,2; 10,11,12; 20,21,22; ... 가 된다. 따라서 모듈로 10으로 보는 위 규칙이 성립합니다.
참고/배경(이론적 근거)
- 이런 종류의 ‘항상 이기는 수’를 보장하는 일반적 이론은 체르멜로(체르멜로) 정리 및 님·삭션 게임 이론과 연결됩니다 — 존재는 보장되지만 실제 전략은 규칙(가능한 이동 집합)에 따라 계산해야 합니다.
사용한 참고 자료
원하시면
- 초기 돌 개수(예: 지금 바둑돌이 몇 개인지)를 알려주시면 바로 첫 수로 무엇을 가져야 하는지 계산해 드립니다.
- 규칙이 ‘마지막을 가져가면 지는(미제어 규칙)’ 등이라면 그 경우용 필승/필패표도 다시 만들어 드립니다.