님 규칙과 필승 전략
님은 돌무더기에서 돌을 가져가다 마지막 돌을 가져가는 사람이 이기는 게임입니다. 우연이 전혀 없는 게임이라 시작 상태만 정해지면 누가 이기는지가 이미 정해져 있습니다. 이 글은 그 이유와 이기는 방법을 이진수로 설명합니다.
한눈에 보기
| 시작 상태 | 네 더미에 돌이 각각 1개, 3개, 5개, 7개로 모두 16개 |
|---|---|
| 먼저 두는 쪽 | 플레이어 1 |
| 한 차례에 하는 일 | 더미 하나를 골라 그 더미에서 돌을 1개 이상 가져갑니다. 한 더미에서만 가져갈 수 있습니다. |
| 끝나는 조건 | 마지막 돌을 가져간 사람이 승리합니다. |
| 무승부 | 없음 |
| 필승 전략 | 시작 상태의 님 합은 0이며, 양쪽이 최선이면 후공 필승입니다. |
이 사이트의 규칙 페이지 가운데 필승 전략을 구체적으로 풀어 쓰는 것은 이 페이지뿐입니다. 님은 우연도 숨겨진 정보도 없어서 시작부터 끝까지 수학으로 설명할 수 있기 때문입니다.
시작 상태 그림
화면에서는 더미마다 돌이 그려지고, 더미 아래에 가져갈 개수를 고르는 버튼이 늘어서 있습니다. 가져갈 수 있는 개수는 그 더미에 남은 돌의 수까지이며, 0개는 고를 수 없습니다.
규칙 자세히
차례마다 하는 일은 하나입니다. 돌이 남은 더미를 하나 고르고, 그 더미에서 1개 이상 남은 개수 이하를 가져갑니다. 여러 더미에서 동시에 가져갈 수는 없고, 가져간 돌을 다시 놓을 수도 없습니다.
판에서 돌이 모두 사라진 순간, 그 마지막 돌을 가져간 사람이 승리합니다. 마지막 돌을 가져가야 이기므로, 돌이 한 개 남은 상황에서 내 차례가 오면 이깁니다. 반대로 두 개가 든 더미 하나만 남았을 때 한 개만 가져가면 상대가 마지막 한 개를 가져가므로, 이때는 두 개를 모두 가져가야 합니다.
무승부는 없고, 한 수마다 돌이 줄어들므로 게임은 반드시 끝납니다. 최대 16수 안에 끝나는데, 이는 한 수에 최소 1개를 가져가기 때문입니다.
이기는 방법: 님 합과 XOR
더미의 돌 수를 이진수로 씁니다. 1은 001, 3은 011, 5는 101, 7은 111입니다. 각 자리의 1의 개수를 세어 보면 가장 오른쪽 자리는 네 개, 가운데 자리는 두 개, 왼쪽 자리는 두 개로 모두 짝수입니다. 모든 자리의 1이 짝수 개인 상태를 님 합이 0이라고 부르며, 이것은 모든 더미 수를 XOR로 합친 값이 0이라는 말과 같습니다.
님 합이 0인 상태에서는 어느 한 더미에서 돌을 가져가도 그 더미의 이진수가 바뀌므로 반드시 님 합이 0이 아닌 상태가 됩니다. 반대로 님 합이 0이 아닌 상태에서는 한 더미를 알맞게 줄여 님 합을 다시 0으로 만드는 수가 항상 있습니다. 그 수는 님 합에서 가장 왼쪽에 있는 1의 자리를 가진 더미를 골라, 그 더미의 수를 더미 수와 님 합의 XOR 값으로 줄이는 것입니다.
이 두 사실을 합치면 결론이 나옵니다. 시작 상태는 님 합이 0이므로 선공은 어떻게 두어도 님 합이 0이 아닌 상태를 만들게 되고, 후공은 매번 님 합을 0으로 되돌릴 수 있습니다. 모든 돌이 없어진 상태도 님 합 0이므로 마지막 돌을 가져가는 사람은 후공이 됩니다. 이 사이트의 규칙 엔진으로 모든 경우를 따져 본 결과도 후공 필승이었습니다.
예시로 따라 해 보기
다음은 가상의 예시입니다. 플레이어 1이 더미 4에서 3개를 가져가면 더미는 1, 3, 5, 4가 됩니다. 님 합은 1 XOR 3 XOR 5 XOR 4로 3입니다. 이제 플레이어 2는 님 합 3과 XOR했을 때 더미 수보다 작아지는 더미를 찾아야 합니다.
더미 1(1개)은 1 XOR 3이 2여서 커지고, 더미 3(5개)은 5 XOR 3이 6이라 커지며, 더미 4(4개)도 4 XOR 3이 7이라 커집니다. 더미 2(3개)만 3 XOR 3이 0으로 작아지므로, 더미 2에서 3개를 모두 가져가면 더미는 1, 0, 5, 4가 되고 님 합은 1 XOR 5 XOR 4로 0이 됩니다. 이 상태가 되면 이제부터 플레이어 1이 어떻게 두어도 플레이어 2는 같은 방법으로 님 합 0을 되돌립니다.
자주 하는 실수
- 마지막 돌을 가져가면 지는 규칙으로 알고 둔 경우. 이 사이트에서는 마지막 돌을 가져가야 이깁니다.
- 더미 수만 보고 암산하다가 이진수 자리의 개수 세기를 틀리는 경우
- 선공이면 이길 수 있다고 생각하는 경우. 후공이 님 합 0을 유지하면 선공은 어떻게 두어도 이기지 못합니다.
- 님 합이 0인 상태를 만들었는데 한 번 더 확인하지 않고 다음 수를 서둘러 두는 경우
혼자 해 보는 연습 과제
님은 계산 규칙이 분명해서 혼자서도 연습하기 좋습니다. 먼저 후공의 입장에서 연습하는 것을 권합니다.
- 플레이어 1이 더미 3(돌 5개)에서 2개를 가져가 1, 3, 3, 7이 되는 판을 만들어 보세요. 님 합은 1 XOR 3 XOR 3 XOR 7이어서 6이 됩니다. 6과 XOR했을 때 더미 수보다 작아지는 더미를 직접 찾아 응수해 보세요.
- 돌이 모두 한 개짜리 더미만 남은 마무리 상황을 만들어 보세요. 이때는 더미 개수가 홀수인지 짝수인지를 보면 승패가 갈립니다. 마지막 돌을 가져가야 이기는 규칙에서 이 상태가 왜 님 합과 같은 결과를 주는지 확인해 보세요.
- 시작 상태에서 선공이 할 수 있는 수가 몇 가지인지 세어 보세요. 더미마다 가져갈 수 있는 개수는 그 더미의 돌 수와 같으므로 1, 3, 5, 7을 모두 더한 16가지입니다. 그 모든 수에 대해 후공이 님 합 0으로 되돌리는 응수가 있다는 것이 후공 필승의 의미입니다.
한 기기로 둘이 할 때
전략을 아는 사람과 모르는 사람이 두면 승부가 일방적으로 끝납니다. 모임에서는 후공이 이기는 방법을 먼저 숨기고 몇 판 해 본 뒤, 이진수 설명을 함께 읽고 다시 두어 보는 식으로 진행하면 게임 구조를 이해하기 좋습니다.
새 게임은 플레이어 1부터 시작하고 무르기가 없습니다. 이긴 기록보다 님 합을 몇 번 정확히 계산했는지를 서로 확인하는 방식이 전략 연습에 알맞습니다.