유리그릇 속 구슬 꺼내기…마지막 한 알의 주인은?

클래스온 수석연구원 박동훈

창의적 문제해결 연습 /

■ 생각해보자

몇 개의 투명한 유리그릇에 구슬이 몇 개씩 들어 있다. 각각 구슬의 개수는 같을 수도, 다를 수도 있다. 유리그릇에 들어 있기 때문에 항상 그릇에 구슬이 몇 개인지 확인할 수 있다. 두 사람이 다음의 규칙을 따르는 게임을 한다.

규칙 1. 서로 번갈아 가면서 시행한다.

규칙 2. 시행을 하는 사람은 유리그릇 가운데 꼭 하나를 선택해 그 안에 든 구슬을 자신이 원하는 만큼 꺼낼 수 있다. 단, 반드시 한 개 이상 꺼내야 한다.

규칙 3. 가장 마지막 구슬을 꺼내는 사람이 이긴다.

이런 게임을 할 때 필승의 전략을 구성하는 것이 과제다. 필승 전략에는 먼저 시행하는 사람이 필승 전략을 구사할 수 있는 형태를 포함해야 한다. 아이디어를 떠올리기가 매우 까다롭기 때문에 ‘이진법’이라는 힌트를 준다.

■ 문제풀이 과정

이런 게임을 ‘님게임’(Nim-Game)이라고도 한다. 이 게임에서 중요한 것은 마지막 것을 꺼내는 사람이 이기는 경우에 다음의 방식을 적용할 수 있으므로, 마지막 것을 꺼내는 사람이 이기는지의 여부가 중요하다.

예를 들어, A, B, C, D, E 다섯 개의 유리그릇에 각각 5, 8, 7, 9, 6 개의 구슬이 들어 있다고 하고 진행한다. 각각의 수를 이진수로 바꾸면 다음의 표를 쉽게 얻을 수 있다.

1의 개수가 2, 3, 2, 3으로 나타났다. 이 숫자들이 모두 짝수인 상태를 ‘평형 상태’라고 하고, 평형 상태가 아닌 것을 ‘비평형 상태’라고 한다면, 다음의 두 가지가 성립한다.

1. 모든 비평형 상태는 평형 상태로 바꿀 수 있다.

2. 평형 상태는 유지될 수 없다.

이 두 가지 사실이 성립한다는 것은 뒤에서 설명할 것이고, 우선 이 두 가지 사실이 성립하면 필승 전략을 구성할 수 있다는 것을 살펴본다.

내 순서에 비평형 상태라면, 이를 평형 상태로 바꾼다. 평형 상태는 유지될 수 없으므로, 상대방은 이를 다시 비평형 상태로 바꾸게 된다. 그러면, 나는 다시 이를 평형 상태로 바꾼다. 그러면, 상대방을 이를 다시 비평형 상태로 바꾸게 된다. 이를 반복하면, 모든 평형 상태는 내가 만들어내는 것이 된다. 이는 상대방은 평형 상태를 만들어낼 수 없다는 뜻이기도 하다. 가장 마지막 상황에 1의 개수는 0, 0, 0, 0으로 이는 평형 상태다. 따라서, 마지막 상황은 내가 만들어내는 것이 되므로 내가 이기게 된다.

이제 위의 두 가지 사실이 성립한다는 것을 설명하겠다.

1. 모든 비평형 상태는 평형 상태로 바꿀 수 있다.

이는 비평형 상태를 평형 상태로 바꾸는 방법을 설명하는 것으로 하겠다. 1의 개수 중 가장 왼쪽에 있는 홀수를 찾아 그 열에 존재하는 1을 포함하는 그릇 중 하나만을 선택한다.

위의 예를 가지고 살펴보자.

A, C, E 중 하나의 그릇을 선택한다. E를 선택하면, 이제 1의 개수 중 홀수인 열과 E의 열이 교차하는 곳에 1이 있으면 없애고 1이 없으면 채운다.

그러면, 평형 상태가 되는 것을 확인할 수 있다. 항상 이런 방법으로 모든 비평형 상태는 평형 상태로 바꿀 수 있다.

2. 평형 상태는 유지될 수 없다.

이제 바로 위의 평형 상태를 가지고 보자.

그릇은 반드시 하나만을 선택하므로 시행을 할 때 반드시 하나의 행에 있는 숫자들에만 변화를 줄 수 있다. 각 숫자는 1 또는 비어 있는 상태이므로 변화라고 하는 것이 1이 없어지거나 없던 1이 생기거나 둘 중 하나다. 그런데 이는 열에서 보면, 1의 개수가 하나 줄어들거나 늘어나는 것이다. 그러면 짝수가 홀수로 바뀌는 것이다. 따라서, 평형 상태는 유지될 수 없다. 예를 들어, D에서 1개를 꺼낸다면,

이처럼 그릇에서 한 개 이상을 꺼내면 1의 개수가 모두 짝수인 것은 유지될 수 없다는 것을 알 수 있다.

따라서, 필승의 전략은 자신의 순서에 ‘평형 상태’를 만드는 것이다. 이는 자신의 순서에 비평형 상태여야 한다. 즉, 먼저 시행하는 사람이 필승의 전략을 구사할 수 있으려면, 비평형 상태여야 한다. 물론 이 전략을 알고 있는 사람에 한해서다. 오늘 아빠와 한번 해보는 건 어떨까?

※ 매주 목요일 클래스온 누리집(www.class-on.com)에서는 문제 출제자가 직접 풀이한 동영상을 제공합니다. 문제에 대해 궁금한 점은 1644-0020으로 문의하면 됩니다.