돌줍기 게임 2

돌줍기 게임 2

돌을 서로 줍습니다. 돌을 마지막으로 줍는 사람이 게임에서 이깁니다. 단, 상대가 가져간 돌의 2배를 초과하여 주울 수 없습니다.

돌줍기 퍼즐과 피보나치 수열

예를 들면 처음에 32개의 돌이 있다면 먼저 줍는 것은 처음 1 개부터 31 개까지 줍게 됩니다.
컴퓨터는 Fibonacci 수열 (1, 1, 2, 3, 5, 8, 13, 21, 34, …..)을 사용하여 남길 돌의 수를 계산합니다.

Fibonacci 수열(만들어진 원리)
1
1 = 1
2 = 1 + 1
3 = 1 + 2
5 = 2 + 3
8 = 3 + 5
13 = 5 + 8
21 = 8 + 13
34 = 13 + 21
… …
n1 …
n2 …
n3 = n1 + n2

예를 들면 돌이 32 개이면 32 이하의 최대 Fibonacci 수는 21이며, 32-21=11 이하의 최대 Fibonacci 수는 8 이며, 32-21-8=3 은 Fibonacci 수 이므로 32 = 21+8+3으로 나타납니다.
이렇게, 모든 수는 Fibonacci 수의 합으로 나타낼 수 있으며, 수열 각 단계의 아래쪽 수는 위쪽 수의 두 배보다 큽니다. 이 점을 이용하면 컴퓨터를 이길 수 있습니다.
즉, 21은 8의 두 배보다 크고, 8은 3의 두 배보다 큽니다.

따라서 돌의 수가 21+8+3 개라고 하면, 컴퓨터는 3 개를 주워서 Fibonacci 합을 유지시키려 합니다. 이런 경우 유저는 8 개를 주울 수 없게 됩니다. 컴퓨터가 Fibonacci 수의 합을 유지시키면, 마지막에 돌을 줍는 승자는 컴퓨터가 됩니다. 이 전략을 사용하지 않는 것은 처음 돌의 수가 우연히 Fibonacci 수였을 때이고, 이 때 컴퓨터는 방법이 없으므로 한 개 줍고 우연히 상대의 패배를 기다립니다.

* 승리전략: 컴퓨터 대신 유저가 Fibonacci 합을 유지시켜 나가면 됩니다. 자세한 것은 직접 해보시면서 알아내시길…