님(NIM)게임에서 이기는 필승전략

님(NIM)게임에서 이기는 필승전략

1. 님게임의 유래 

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

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

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

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

2. 게임방법

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

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

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

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

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

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

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

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

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

① ② ③ ④ ⑤ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                                                  이기는 구슬

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

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

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

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

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

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

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

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

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

따라서 내가 이 게임에서 이기기 위해서는 나는 필히 나중에 시작해야 한다. 그래서 상대방이 한 개 가져오면 나는 세 개의 구슬을 가져와 이기는 4번 구슬을 가져오고, 상대방이 두 개 가져오면 나는 두 개의 구슬을 가져와 이기는 4번 구슬을 가져오고, 상대방이 세 개 가져오면 나는 한 개의 구슬을 가져와 이기는 4번 구슬을 가져 와야 하는 것이다.

■ 기출문제

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

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

3. 다음은 어떤 게임의 규칙입니다.
① 바둑둘을 하나는 4개, 다른 하나는 6개로 두 더미를 만듭니다.
② 한 번에 한 더미에서만 1개 또는 2개를 꺼낼 수 있습니다.
③ 꺼낼 것이 더 이상 없는 사람이 집니다.
이기는 방법을 쓰시오.[2006 대진대]

  

▷ 정답 해설

 

1. 2005년 서울교대 문제는

구슬의 수는 11개, 한 번에 1개에서 3개까지 잡을 수 있고, 마지막 구슬을 잡는 사람이 질 때, 이기기 위해서 처음에 잡아야 할 구슬의 수를 구해야 한다.

구슬에 번호를 매기고 차례대로 구슬을 가지고 간다고 할 때, 이기는 구슬은 ⑩번, ⑥번, ②번이다. 따라서 이기기 위해서는 처음에 2개의 구슬을 잡으면 된다.

① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ⑪
     ↑                 ↑                 ↑
이기는 구슬    이기는 구슬     이기는 구슬

 

2. 2004년 공주대 문제는
구슬의 수는 20개, 한 번에 1개에서 3개까지 잡을 수 있고, 마지막 구슬을 잡는 사람이 이길 때, 이기기 위한 방법을 찾는 것이다.
위와 마찬 가지 방법으로 이기는 구슬을 찾으면 ⑳번, ⑯번, ⑫번, ⑧번, ④번이다.

① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬ ⑭ ⑮ ⑯ ⑰ ⑱ ⑲ ⑳
               ↑                 ↑                 ↑                ↑                  ↑
      이기는 구슬       이기는 구슬     이기는 구슬     이기는 구슬    이기는 구슬

따라서 내가 ④번 구슬을 잡기 위해서는 먼저 잡지 말고 나중에 잡아야 한다.
상대가 1개 잡으면 나는 3개, 상대가 2개 잡으면 나는 2개, 상대가 3개 잡으면 나는 1개 잡으면 된다.

 

3. 2006년 대진대 문제는
위의 두 문제보다는 좀 더 까다로운 어려운 문제이지만 역시 똑같은 원리를 사용하면 된다.
구슬의 수는 10개인데 4개, 6개로 두 더미로 나누어져 있고,
한 번에 1개 또는 2개를 꺼낼 수 있는데 한 더미에서만 꺼낼 수 있고,
꺼낼 것이 없는 사람이 지므로 마지막 구슬을 꺼낸 사람이 이긴다고 하였다. 
   
먼저 차례대로 구슬을 꺼낸다고 할 때, 이기는 구슬은 ⑩번, ⑦번, ④번, ①번이 된다.

따라서 4개 더미의 구슬 하나를 꺼내면 이기게 된다.
만약 내가 ①번을 꺼냈을 때, 상대가 ②번이나 ②, ③번을 꺼내지 않고, ⑤번이나 ⑤, ⑥번을 꺼냈다 하더라도 내 차례가 되어 ⑦번을 꺼내면 되므로 이기는 구슬은 변함이 없게 된다.
   
하지만 아래와 같이 6개 더미에서 구슬 하나를 꺼내면 상황은 달라진다.
내가 ①번 구슬을 꺼내면 일단 ④번 구슬은 잡을 수 있다.
그런데 상대방이 ⑤번 구슬을 잡으면 내 차례가 되어 ⑥, ⑦번을 잡아 ⑦번 구슬을 꺼내야 하는데 한 더미에서만 구슬을 꺼내야 하므로 ⑦번 구슬을 잡을 수 없게 된다. 즉 이기는 ⑦번 구슬을 잡지 못하는 상황이 발생하는 것이다.
    
따라서 먼저 구슬 1개를 꺼내면 되지만 두 더미의 조건 하에서는 4개 더미에서 구슬 하나를 꺼내야 하는 것이다.
그렇다면 이길 수 있는 방법은 4개 더미에서 구슬 한 개를 꺼내는 것이 유일한 방법인가?
두 더미가 아닌 한 더미의 상황에서는 이기는 상태는 단 한 가지만 존재하였다.
그런데 두 더미의 상황에서는 다음과 같이 이기는 상태가 2가지 존재한다.
(1) 첫째는 마지막에 한 더미에 구슬 3개가 남게 되는 경우이고, 위에서 푼 경우와 같다.
   
(2) 둘째는 한 더미에 구슬 1개, 다른 더미에 구슬 1개가 남게 되는 경우이다.
   
이 경우의 이기는 상태를 거꾸로 따져 나가면
두 더미의 구슬의 개수가 같게 만들면 된다.
따라서 6개 더미에서 구슬 2개를 꺼내면 두 더미의 구슬의 수가 같게 되고 결국은 이길 수 있게 되는 것이다.
결국 이 게임에서 이기는 방법은 4개 더미에서 구슬 1개를 꺼내던지, 6개 더미에서 구슬 2개를 꺼내면 된다.