돌줍기 게임 2
- Pick stone game
쌓아 놓은 돌 무더기에서 서로 돌을 줍습니다.
마지막으로 돌을 줍는 사람이 이기는 것입니다.
단, 상대가 주운 돌의 두배이상 주울 수 없습니다.
또, 처음 시작할 때 모든 돌을 주울 수 없습니다.
예를 들면 처음에 32개의 돌이 있다면 먼저 줍는 것은 처음 1 개부터 31 개까지 줍게 됩니다.
컴퓨터는 Fibonacci 수열 (1, 1, 2, 3, 5, 8, 13, 21, 34, .....)을 사용하여 남길 돌의 수를 계산합니다.
 |
| Fibonacci 수열 |
(만들어진 원리) |
| |
1
1
2
3
5
8
13
21
34
…
n1
n2
n3 |
=1
=1+1
=1+2
=2+3
=3+5
=5+8
=8+13
=13+21
…
…
…
=n1+n2 |
| |
예를 들면 돌이 32 개이면 32 이하의 최대 Fibonacci 수는 21이며, 32-21=11 이하의 최대 Fibonacci 수는 8 이며, 32-21-8=3 은 Fibonacci 수 이므로 32 = 21+8+3으로 나타납니다. 이렇게 하면 인접하는 Fibonacci 수 (예를 들면, 21과 13)를 합속에 나타내는 것은 부득이합니다. 왜냐하면 21+13=34 도 Fibonacci 수이기 때문에 먼저 34를 사용하면 21과 13을 동시에 사용하는 것이 부득이 하기 때문입니다. 이것으로부터 합 21+8+3의 각 항은 그 오른쪽에 인접하는 항의 두 배보다 큰 것을 알 수 있습니다. 즉 21은 8의 두 배보다 크고, 8은 3의 두 배보다 큽니다. 따라서 돌의 수가 21+8+3 개이면, 컴퓨터가 세 개이면 상대는 여덟개 주울 수는 없으므로, 합 속의 Fibonacci 수의 개수를 줄일 수 있습니다. 따라서 마지막에 돌을 줍는 것은 컴퓨터입니다. 이 전략을 사용하지 않는 것은 처음 돌의 수가 우연히 Fibonacci 수였을 때이고 이 때는 방법이 없으므로 한 개 줍고 우연히 상대의 패배를 기다립니다.