마지막 돌을 가져가는 사람이 지는 게임에서, 예전의 승리 전략을 그대로 쓰면 될까요? 한 번에 한 더미에서 1개 이상을 가져가는 니므 게임을 볼까요? 두 사람은 번갈아 움직이고, 처음에는 돌이 적어도 1개 있어요. 상대도 최선으로 움직인다고 가정해요.
먼저 돌이 (5,1,1)개인 세 더미를 비교해 봐요. 큰 더미를 모두 없애면 (1,1)이 돼요. 각 더미에서 하나씩밖에 가져갈 수 없어서 상대가 하나, 내가 마지막 하나를 가져가요. 내가 진다. 큰 더미를 1개로 줄이면 (1,1,1)이라 상대가 마지막 돌을 가져가게 돼요.
두 번째 선택이 유리해요. 한 번에 많이 가져가는 것이 목표가 아니며, 남은 돌의 총수만 같은 홀짝으로 만들려는 것도 아니에요. 모두 1개인 끝 상태에서는 남은 더미 수가 홀수일 때 현재 차례가 진다.
큰 더미가 여러 개일 때는 다른 규칙이 필요해요. 각 개수를 2진법으로 적어 자릿수를 맞춰요. 모든 열의 1 개수가 짝수인 상태를 이 글에서 ‘균형’이라고 불러요. 전체 돌 수가 짝수라는 뜻은 아니에요. 균형 상태에서 한 더미를 실제로 줄이면 적어도 한 열의 홀짝이 바뀌어 균형을 유지할 수 없어요.
균형이 깨져 있으면 1 개수가 홀수인 가장 높은 열을 찾아요. 그 열에 1인 더미를 택해 0으로 바꾸고 오른쪽 열을 짝수가 되게 정해요. 가장 높은 변경이 1에서 0으로 내려갔으므로 그 더미는 실제로 줄어들어요. 따라서 합법적인 한 번의 이동으로 균형을 회복해요.
하지만 큰 더미가 정확히 하나 남았을 때는 이 규칙을 멈춰야 해요. 나머지 q개 더미가 모두 1개라면, 마지막 큰 더미 H>1을 다음처럼 줄여요.
어느 경우에도 상대에게 홀수 개의 1더미를 남겨요. H>1이므로 0이나 1로 줄이는 것은 항상 합법적이에요. q=0도 짝수이므로 마지막 큰 더미에서 돌 하나를 남겨야 해요.
왜 큰 더미가 둘 이상일 때는 균형 복원을 해도 될까요? 한 번에 한 더미만 바꾸므로 다른 큰 더미가 남아요. 큰 더미가 정확히 하나인 상태는 높은 이진 열의 1을 다른 1더미가 지울 수 없어 균형이 될 수 없어요. 따라서 균형을 회복한 결과에도 큰 더미가 둘 이상이에요. 상대가 그중 하나만 남기는 순간, 위 끝 상태 규칙으로 바꾸면 돼요.
처음부터 큰 더미가 둘 이상인 균형 상태라면 현재 차례가 강제 승리를 할 수 없어요. 상대는 균형을 복원하거나 마지막 큰 더미에서 홀수 1더미를 남겨요. 전체 돌 수는 계속 줄어들어 끝나므로 이 설명은 우연히 잘된 한 경기의 관찰이 아니에요.
교사는 ‘마지막 돌을 가져가면 이긴다’를 ‘진다’로 바꿨을 때, 끝 상태의 규칙도 고쳤는지 물어요. 여기서는 승리 전략 전체를 폐기하지 않고 적용을 멈춰야 할 경계를 정확히 찾아요. 실제 학생들의 승률은 측정하지 않았어요.
착안: Charles L. Bouton, Nim, A Game with a Complete Mathematical Theory, §§1·2·5·6. 고전의 이진 균형 전략을 정직하게 참조하고, 잘못 재사용한 자동 규칙의 끝 상태를 자체 예와 일반 q로 검사했어요. 원문 표·문항·문장의 번역이나 실제 경기 자료가 아니에요.