보드게임에 숨겨진 이진법, 먼저 시작하는 사람이 무조건 이긴다!

게임을 하다 보면 무조건 이길 수 있는 비기가 있으면 좋겠다는 생각이 들 때가 있다. 리지니를 하는데 특정 몬스터에게 계속 당한다면, 어떤 상황에서도 그 몬스터를 잡을 수 있는 무기가 있으면 좋지 않을까?

이제 소개할 보드게임 ‘님(NIM)’에는 수학을 이용한 이런 천하무적의 무기가 하나 있다. 님 게임의 규칙은 간단하다.

책상 위에 바둑돌이 담긴 주머니를 몇 개 둔다. 두 명이 대결하는데, 주머니 중 딱 하나를 골라 그 안의 바둑돌 몇 개를 가져간다. 그러면 언젠가 모든 주머니에서 바둑돌이 사라질 텐데, 마지막 돌을 가져가는 사람이 이기는 것이다.

위와 같이 돌이 각각 3개와 4개인 주머니로 시작해 보자. 첫 번째 사람이 4개 있는 주머니에서 2개를 가져간다. 두 번째 사람은 3개인 주머니에서 2개를 가져간다. 첫 번째 사람이 다시 2개 남은 주머니에서 1개를 가져간다. 그러면 돌이 각각 1개씩 남기 때문에 첫 번째 사람이 이긴다. 두 번째 사람이 둘 중 어떤 것을 가져가도 첫 번째 사람은 남은 돌을 가져가면 되기 때문이다. 이제는 돌이 각각 4개, 7개 있는 주머니가 있다고 하자. 여러분이 먼저 시작하는 사람이라면, 무조건 이길 수 있다. 어떻게 하면 될까?

두 번째 주머니에서 돌 3개를 꺼내 양쪽 주머니의 돌 개수를 4개로 맞추는 것이다. 지금부터 상대가 어떤 주머니를 골라 돌을 가져가든, 다른 주머니에서 똑같은 개수만큼 돌을 가져가면 되기 때문이다.

그렇다면 주머니가 3개 이상일 때는 어떠한 전략을 쓰면 될까?

그 답은 컴퓨터가 수를 표현할 때 쓰는 이진법에 있다. 이진법은 0과 1만으로 수를 나타내는 방법이다. 예를 들어, 십진법에서 2는 이진법으로 10이고, 십진법으로 5는 이진법으로 101, 십진법으로 19는 이진법으로 10011이 된다.

기호 2개로 모든 수를 나타내기 때문에 켜짐/꺼짐 상태로 수를 나타내는 전자기기에서는 이진법을 애용한다. 리니지 클라이언트를 켤 때 컴퓨터는 캐릭터의 경험치나 체력, 생김새, 위치, 아이템 정보 등을 전부 이진법 수로 저장한다.

여기에 한 가지 개념을 더 알아야 한다. 바로 덧셈의 변형인 XOR 연산이다. XOR 연산은 덧셈에서 자릿수 올림을 무시하는 것이다. 5+6이 11이 아니라 1이 되는 식이다. 이진법에서 1+1은 10이지만, 1 XOR 1은 0이다.

이제 필승 전략을 이야기해보자. 모든 주머니의 돌 개수를 이진법으로 바꿔 XOR로 연산했을 때 그 값이 0이 되게 만들면 된다.

예를 들어, 3개, 5개, 7개로 시작했다고 하자. 2 XOR 5 XOR 7(10 XOR 101 XOR 111)=0이므로 3개짜리 주머니에서 돌을 1개 가져가면 무조건 이길 수 있다. 마찬가지로 3 XOR 4 XOR 7(11 XOR 100 XOR 111)도 0이므로 5개짜리 주머니에서 돌을 1개 가져가도 무조건 이길 수 있다.

간단히 할 수 있는 보드게임에 지금 우리가 쓰는 스마트폰이나 컴퓨터의 기본 원리인 이진법이 적용된다는 게 놀랍다. 이렇게 예상하지 못한 곳에서 쓰이는 모습을 찾을 수 있는 게 바로 수학의 매력이다.
동아사이언스