피보나치 ‘돌 줍기 게임

심심할 때 돌멩이 몇 개 준비하여 무더기로 쌓아두기만 하면, 둘이서 즐길 수 있는 놀이를 하나 소개하자. 돌멩이는 서로 크기나 모양이 같지 않아도 상관 없다. 바둑돌이나 장기알 등 뭐든지 좋다.돌 줍기 게임의 규칙은 다음과 같다.

돌 줍기 게임: 규칙

1. 갑부터 시작하여 갑과 을이 번갈아 가며, 쌓여 있는 돌멩이 무더기에서 돌을 한 개 이상 집어 온다.
2. 차례가 되어 돌을 집어 올 때는 반드시 상대방이 조금 전에 집어 간 돌의 개수의 두 배 이하로 집어 와야 한다. 예를 들어 갑이 2개를 집은 뒤였다면, 을은 1개부터 4개까지의 범위에서 돌을 집어 와야 한다. 이때, 을이 3개를 집어 갔다면, 다시 갑은 1개부터 6개까지의 사이에서 마음대로 돌을 집어 가면 된다.
3. 마지막 돌을 집어 간 사람이 승리한다.
4. 맨 처음 시작하는 사람은, 돌을 다 집어 가면 안 된다.

서로 번갈아 돌을 주워가는 게임. 누가 이길까? <출처: Gettyimage>

돌 줍기 게임에 필승 전략은 없나?

이런 놀이도 되는 대로 하는 사람보다는, 잘 생각하고 평소에 분석해 보는 습관이 있는 사람이 승리가능성이 높다는 것은 당연하다. 당연하지만 돌멩이 개수가 적을 때가 분석하기도 쉽고, 감을 익히는데 도움이 된다.

1. 돌멩이가 1 개인 경우, 게임 자체가 성립하지 않는다.
2. 2 개인 경우 무조건 을이 이기는 건 자명하다.
3. 3 개인 경우도 져주기로 작정하지만 않으면 을이 이긴다.
4. 4 개인 경우에는 갑이 처음에 한 개를 집으면, 이길 수 있다는 것이 명백하다.
5. 5 개인 경우 갑은 두 개 이상 집으면 바로 패하므로, 무조건 한 개만 집어야 한다. 하지만 이 경우, 을이 한 개를 집으면 그 뒤는 사실상 외길 수순이다. 승자는 을이다.
6. 6 개인 경우 역시 갑은 맨 처음에 두 개 이상은 못 집는다. 한 개만 집어야 하므로 다섯 개가 남았는데, 위에서 갑과 을이 바뀐 경우다. 따라서 승자는 갑이다.
7. 7 개인 경우, 갑이 한 개를 집는다면 여섯 개가 남아 바로 위에서 보듯 승자는 을이다. 그렇다고 세 개 이상을 집으면 당연히 지므로, 갑은 두 개를 집어야만 한다. 다섯 개가 남은 상황을 역으로 생각하면, 전략을 잘 세울 경우 승자는 갑이라는 뜻이다.
8. 8 개인 경우, 갑은 3 개 이상을 집으면 곧바로 진다. 1 개나 2 개를 집어야 하는데, 앞서 두 경우를 뒤집어 생각하면 최선의 대응을 할 경우, 승자가 을임을 알 수 있다.

조금 더 생각할 수 있으나 일단 이 정도에서 멈추자. 처음 돌멩이의 개수가 2, 3, 5, 8 개인 경우 최선의 전략을 세우면 을이 이긴다는 것을 알 수 있다. 이 숫자들에서 기시감(déjà vu)이 든다면, IQ 테스트 점수가 약간 높거나 교양 수학책을 한두 권 이상 봤을 가능성이 있다. 규칙이 보이는가? 인접한 두 수를 더하면 다음 항이 된다는 규칙을 갖는다. 개수가 많지 않기 때문에, 정말로 큰 숫자일 때도 이런 규칙으로 결정되는지 의심하는 건 당연하다. 실제로 13 개로 시작한 경우 귀찮기는 하지만 최선의 전략을 따를 경우 을이 이김을 확인할 수 있다. 이 정도면 뭔가 그럴 듯한데… 실제로도 이런 규칙으로 만든 수열에서만 을이 이긴다는 것을 증명할 수 있다!

2, 3, 5, 8, 13, 21, 34, …

이처럼 앞의 두 항을 더해 다음 항이 나오는 수열을 가리켜 피보나치 수열이라 부르므로, 이 게임을 '피보나치 돌 줍기 게임(Fibonacci Nim)’이라 부른다. 그런데 피보나치는 도대체 누구일까?

피보나치는 누구?

서양 수학사에서 그리스 시대의 수학 및 수학자는 어렵지 않게 찾아볼 수 있는데, 1500년 가까이 존속했던 로마 시대의 수학 얘기는 거의 찾아볼 수 없다는 건 의외다. 모르긴 해도 로마 시대의 수학자 이름을 한 명이라도 댈 수 있는 사람은 별로 없을 것이다. 증명과 논리를 토대로 하는 정신적 산물로서의 수학을 도외시하고, 극단적으로 실용적인 목적의 수학만을 했고, 그나마 실용적인 수학도 정복에 의한 지식 흡수에 그친 때문이라는 평가가 많다.

그리스 수학의 전통은 유럽이 아니라 아랍 세계가 계승하였다. 현재 남아 있는 그리스 수학에 대한 문서, 예를 들어 유클리드의 ‘기하학 원론’도 아랍어 번역본을 라틴어로 다시 번역한 덕택에 현대까지 살아 남은 것이다. 어쨌거나, 13세기에 접어 들며 유럽 수학계에는 변화의 바람이 분다. 아랍 세계에 수출됐던 수학을 역수입하고, 인도-아라비아 숫자 체계를 받아들여 유럽에 새로운 수학을 일으킨 사람이 바로 이탈리아의 수학자 ‘피사의 레오나르도’(Leonardo of Pisa, 1170?-1250?)이다. 레오나르도라는 이름보다는 보나치의 아들, 즉 피보나치(Fibonacci)로 더 잘 알려져 있다. 그가 저술한 ‘산반서 (Liber abbaci)’는 이후 300년 가량 대단히 큰 영향력을 미친 수학 교재였는데, 서양이 극도로 불편한 숫자 체계인 로마 숫자를 버리게 만들었다는 점에서도 중요하다.

피보나치 수열이란?

산반서의 12장에는 ‘토끼 한 쌍은 태어난 지 두 달째부터 매달 새끼를 암수 한 쌍씩 낳는다. 갓 태어난 토끼 암수 한 쌍이 있을 때, 12개월 후 토끼가 몇 쌍인지 구하라’는 문제가 제시돼 있다. 1개월, 2개월, 3개월, 차근차근 토끼의 수를 구해서 답을 구하는 문제인데, 책의 성공과 함께 유명세를 타서 피보나치 수열이라는 이름으로 굳어졌다. 영원히, 암수 공히 같은 비율로 태어나며, 두 달 만에 꼬박꼬박 새끼만 낳는다는 둥 비현실적인 가정이 많아서 별로 좋은 문제는 아니라 본다. 그나마 피보나치 수열을 일상에서 쉽게 접할 수 있는 것은 징검다리가 아닐까 생각한다.

징검돌이 n개 놓여있다. 다음 징검돌을 밟거나, 징검돌을 한 개씩은 건너 뛸 수 있다고 할 때,
건너는 방법의 수는 몇 개인가? 단, 되돌아가지 말 것.

징검돌 사이의 간격이 너무 가까우면 돌을 많이 놓아야 하는 데다 물의 흐름을 방해하는 반면, 너무 멀면 노약자가 건너기 힘들고 한두 개쯤 유실되거나 물에 잠겼을 때 개울을 건너는데 문제가 생기므로, 위의 문제에 주어진 가정은 나름 현실적이다. 예를 들어 돌이 다섯 개인 경우, 아래 그림처럼 모두 다섯 가지 방법이 있다.

n개의 돌이 남아 있을 때 건너가는 방법의 수를 f_n이라 하면,

임을 확인할 수 있다. 왜 그런지는 어렵지 않게 설명할 수 있다. 예를 들어 위의 그림에서 처음 세 가지 방법은 ‘일단 한 칸을 전진한 뒤, 남은 네 개를 건너가는 방법의 수’인데 이는 네 개를 건너가는 방법의 f₄ = 3 만큼의 방법이 있다. 뒤의 두 가지 방법은 ‘일단 두 칸을 전진한 뒤 남은 세 개를 건너가는 방법의 수’이므로 f₃ = 2 가지 방법이 있기 때문이다. 몇 항을 구해 보면 다음과 같다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

그렇다면 피보나치의 원래 문제의 답은 얼마일까?

피보나치 수가 ‘돌 줍기 게임 승리’의 열쇠

돌 줍기 게임과 관련하여 나오는 당연한 질문은 이렇다. “돌멩이가 n개인 경우 갑이 이길까? 을이 이길까?” 예를 들어 돌멩이가 90 개인 경우라면 어떨까? 위에서 보듯 피보나치 수열을 앞에서부터 차례로 계산해 보면 90은 등장하지 않으므로, 최선의 전략을 택할 경우 갑이 이긴다는 것을 알 수 있다.

피보나치 수열에 어떤 수가 등장하는지 일일이 더하여 알아보기 귀찮다면, 아래와 같은 간단한 판별법을 이용할 수도 있다.

5N² + 4 나 5N²-4가 완전제곱수일 때만, N이 피보나치 수열에 등장한다.

예를 들어보자. 21을 제곱한 뒤 다섯 배를 한 뒤 4를 더한 2209는 47의 제곱이다. 따라서 21은 피보나치 수열에 등장한다. (N=1인 경우에만 둘 다 완전제곱수라는 사실도 흥미롭지 않은가!)

그런데 돌 줍기 게임의 필승 전략은?

피보나치 수열을 알았다고 해서, 돌 줍기 게임의 필승 전략을 알았다고 생각하면 오산이다. 실제로 돌을 많이 쌓아 놓고, 이기려고 노력해 보라. 생각보다 쉽게 이길 수는 없을 것이다. 예를 들어 12개의 돌이 있다고 하자. 위의 설명에서 피보나치 수열에 등장하는 수를 남기면 ‘을’이 이길 수 있다고 했다. 따라서 갑은 역으로 을에게 피보나치 수열에 등장하는 수를 주려고 할 것이다. 그러면 자기가 ‘을’으로 입장이 바뀌고 게임을 이길 수 있으니까. 그러나 그렇게 단순하게 생각하여 12개의 돌 중 8개를 남기려고 4개의 돌을 가져가면 한방에 진다.

필자는 최선의 전략을 알고 있다. 실제로 학생들을 가르치면서 이 놀이를 해 본 적이 있다. 나중에는 작전이 노출되어 결국 지고 말았지만, 처음 일주일 정도는 한 번도 지지 않은 전력(前歷)을 갖고 있다. 그 전략이 뭐냐고? 여백도 좁거니와, 전략을 노출하여 게임을 망치고 싶지는 않으므로 여기서는 적지 않는다.

네이버캐스트