【 한헌조의 수학특강 - 5. 님(nim) 게임 】

1. 님게임의 유래

옛날 서양의 선술집에서는 테이블 위에 성냥 상자를 놓아 두었다. 선술집에 오는 사람들은 성냥개비를 이용해 여러 가지 게임을 만들어서 내기를 하면 놀았는데 그 중 하나가 님게임이다.

이 게임은 13개의 성냥개비를 놓고 두 사람이 번갈아 가면서 하나나 둘, 혹은 세 개의 성냥개비를 가져가는데, 맨 마지막 성냥개비를 가져가는 사람이 지는 것으로 하였다. 이후 이 성냥개비 게임은 수학의 재형성(recreational)이라는 한 분야로 적용되었고, 컴퓨터 전략 게임에서도 중요한 한 장르가 되었다.

이 님게임은 초등 저학년의 여러 사고력 프로그램애서 널리 활용되고 있고, 초 중등 영재교육원에서도 님게임을 그래프 이론으로 소개하고 있다.

물론 영재교육원 선발 시험에서도 자주 출제되었다. 이 게임을 해 본 사람은 쉽게 문제를 풀 수도 있지만 여러 가지 변형된 문제가 나오기 때문에 정확한 원리를 이해하지 못하면 자칫 잘못 풀 수도 있기에 주의를 요한다.

2. 영재교육원 기출문항

‣ 11개의 구슬이 있는데 한번에 1개, 2개 또는 3개의 구슬을 잡을 수 있습니다. 마지막 구슬을 잡는 사람이 질 때, 처음에 몇 개의 구슬을 잡아야 꼭 이길 수 있습니까?[2005 서울교대]

‣ 친구와 내가 구슬 가져가기 게임을 하려고 합니다. 구슬 20개를 놓고 한 사람이 1개에서 3개까지 구슬을 가져갈 수 있습니다. 마지막 구슬을 가져가는 사람이 이길 때. 항상 내가 게임에서 이기려면 어떻게 해야 합니까?[2004 공주대]

‣ 다음은 어떤 게임의 규칙입니다.

① 바둑둘을 하나는 4개, 다른 하나는 6개로 두 더미를 만듭니다.

② 한 번에 한 더미에서만 1개 또는 2개를 꺼낼 수 있습니다.

③ 꺼낼 것이 더 이상 없는 사람이 집니다.

이기는 방법을 쓰시오.[2006 대진대]

3. 님게임을 직접 해 보자

옛날 선술집에서 한 님게임은 13개의 성냥개비를 이용하였고, 한 번에 1개에서 3개까지 성냥개비를 가져올 수 있고, 마지막 성냥개비를 가져오는 사람이 진 것으로 정했다.

이러한 님게임은 성냥개비의 개수를 바꾸거나, 한 번에 가져올 수 있는 성냥개비의 개수를 다르게 하거나, 마지막 성냥개비를 가져오는 사람이 이기거나 해서 게임의 규칙을 바꿀 수 있다.

또한 성냥개비를 두 더미로 나누어서 하는 게임 등 여러 가지 수없이 많은 변형을 만들 수 있다.

먼저 게임을 여러 번 해 보자. 꼭 성냥개비가 아니라도 바둑돌이든 동전이든 그저 13개만 있으면 된다. 장소와 관계없이 두 사람만 있으면 된다. 심지어 혼자 해도 된다.

그리고 게임의 규칙을 바꾸어 여러 번 해 보자. 여러 번 게임을 하다 보면 정확히는 아니지만 어렴풋이 그 원리를 알 수 있을 것이다.

님게임은 반드시 승패가 정해지는 게임이다. 원리를 알면 그 어떤 변형된 게임도 그 게임의 승패를 알 수 있다.

4. 님게임에서 이기는 방법

우선 간단한 경우를 만들어 님게임을 해 보자.

예컨대 5개의 구슬이 있고, 한 번에 1개 또는 2개의 구슬을 가져올 수 있고, 마지막 구슬을 가져오는 사람이 이긴다고 할 때, 마지막 구슬을 가져오기 위해서는 처음에 몇 개의 구슬을 가져와야 할까?

이해를 돕기 위해 구슬에 번호를 매기고 차례대로 구슬을 가져온다고 하자. 이 게임에서는 마지막 5번 구슬을 가져오는 사람이 이기는 것으로 되어 있다.

①  ②  ③  ④  ⑤

이 때 내가 마지막에 ⑤번 구슬을 가져오기 위해서는 상대가 몇 번 구슬을 가져가게 만들어야 하는가?

바로 ③번 또는 ④번 구슬이다.

상대가 ③번 구슬을 가져가면 나는 ④, ⑤번 두 개의 구슬을 가져와서 이길 것이고, 상대가 ④번 구슬을 가져가면 나는 ⑤번 한 개의 구슬을 가져와서 이길 수 있을 것이다.

그렇다면 다시 상대가 ③번 또는 ④번 구슬을 가져가게 만들기 위해서 그 전에 나는 몇 번 구슬을 가져와야 하는가?

두말 할 것 없이 내가 ②번 구슬을 가져오면 된다. 내가 ②번 구슬을 가져오게 되면, 상대편은 한 개의 구슬만 가져갈 경우 ③번 구슬을 가져갈 것이고, 두 개의 구슬을 가져가기 위해서는 ③번과 ④번 구슬을 가져가야 하기 때문이다.

따라서 내가 ②번 구슬을 가져오면 상대는 반드시 ③번 또는 ③, ④번 구슬을 가져갈 수밖에 없게 되고, 다시 내 차례에서 마지막 ⑤번 구슬을 내가 차지할 수 있게 되므로 이 게임에서 이기게 된다.

즉 처음에 2개의 구슬을 가져오는 사람이 반드시 이기게 되는 것이다.

위에서는 간단한 게임상황을 예로 들었지만 그 예에서도 볼 수 있듯이 님게임에서 이기는 전략은 뒤에서부터 몇 개를 남겨두면 이길 수 있을까를 생각하면서 거꾸로 차근차근 따져 보는 것이 그 핵심이다 .

이 전략을 수학적 용어로 다시 말하면 이길 수 있는 상태를 가정하여 거꾸로 생각하여 문제를 해결하는 것이라고 할 수 있다.

이제 선술집의 님게임을 이 원리를 이용하여 이길 수 있는 방법을 알아보자. 다만 여기서는 성냥개비 대신에 계속 구슬의 예로 생각하기로 한다.

13개의 구슬이 있고, 한 번에 1개, 2개 또는 3개의 구슬을 가져올 수 있고, 마지막 구슬을 가져오는 사람이 진다고 할 때. 이길 수 있는 방법은 무엇인가?

마지막 구슬을 가져오는 사람이 진다고 했으므로 내가 이기기 위해서는 ⑫번 구슬을 가져와야 한다. 다시 말해 이 경우는 ⑬번 구슬이 하나 남아 있는 상태가 이길 수 있는 상태인 것이다.

따라서 이 ⑫번 구슬을 이기는 구슬이라 하자.

① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬

↑ ꀣ 이길 수 있는 상태

이기는 구슬

이제 다시 내가 ⑫번 구슬을 가져오기 위해서(이길 수 있는 상태를 만들기 위해서) 몇 번 구슬을 가져와야 하는가를 거꾸로 생각해 보자.

상대가 3개까지 가져갈 수 있으므로 내가 ⑧번 구슬을 가져오면 된다.

내 차례에서 ⑧번 구슬을 가져왔을 때

상대가 ⑨번 한 개의 구슬을 가져가면 나는

⑩,⑪,⑫번 세 개 구슬을 가져오면 되고,

상대가 ⑨,⑩번 두 개의 구슬을 가져가면 나는

⑪,⑫번 두 개 구슬을 가져오면 되고,

상대가 ⑨,⑩,⑪번 세 개의 구슬을 가져가면 나는

⑫번 한 개 구슬을 가져오면 되니까 어떤 경우라도 내가 이기는 12번 구슬을 갖게 되지!

따라서 ⑧번 구슬도 이기는 구슬이 되는 것이다. 다시 ⑧번 구슬을 갖기 위해 몇 번 구슬을 가져와야 하는가를 거꾸로 생각해 보면 마찬가지 이유로 ④번 구슬을 가져오면 된다.

즉, 이길 수 있는 구슬인 ⑫번, ⑧번, ④번 구슬을 가져오면 다음과 같이 이길 수 있는 상태가 만들어지는 것이다.

① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬

↑                    ↑                    ↑

이기는 구슬               이기는 구슬                이기는 구슬

자, 이제는 단지 ①, ②, ③, ④번 구슬만 생각하면 된다.

내가 ④번 구슬을 가져오기 위해서는 어떻게 해야 할까?

내가 먼저 시작하면 한 번에 3개까지의 구슬을 잡을 수 있으므로 ①번이나 ②번 또는 ③번까지의 구슬을 잡게 되고, 상대가 ④번 구슬을 잡을 수 있게 된다. 그래서는 안 된다.

따라서 내가 이 게임에서 이기기 위해서는 나는 필히 나중에 시작해야 한다. 그래서

상대방이 한 개 가져오면 나는 세 개의 구슬을 가져와 이기는 4번 구슬을 가져오고,

상대방이 두 개 가져오면 나는 두 개의 구슬을 가져와 이기는 4번 구슬을 가져오고,

상대방이 세 개 가져오면 나는 한 개의 구슬을 가져와 이기는 4번 구슬을 가져 와야 하는 것이다.

이번 호의 기출문제 풀이는 지면 관계상 다음 호에 연재하겠습니다.

관심 있는 독자께서는  위의 3개의 기출문제를 풀어 보시고 푸신 답을 저희 시매쓰 홈페이지(www.cmath.co.kr) - <커뮤니티> - <경향 하이스터디>에 올리시면 정답자중 5명을 추첨하여 최근 출간된 [영재교육원 대비 초등 사고력 수학 1031] 1 셑트(학년별 3권)를 드리겠습니다.