O que é Nim de Fibonacci?
O Nim de Fibonacci é jogado com uma única pilha. O primeiro jogador pode tirar qualquer quantidade de objetos, menos a pilha inteira. Depois disso, cada jogada tira pelo menos um objeto e no máximo o dobro do que o adversário acabou de tirar. Quem tirar o último objeto vence: o jogo é sempre jogado da forma normal, então a chave misère e a opção de pilhas iniciais do jogo padrão não se aplicam.
A pilha tem 10 (pequeno), 15 (médio, o padrão) ou 20 (grande) objetos, escolhidos como tamanho na configuração da mesa. O limite cresce e diminui com o jogo: uma retirada grande deixa o adversário tirar ainda mais, enquanto uma pequena o mantém na rédea curta, então a disputa é tanto pelo tamanho do próximo limite quanto pela pilha.
Mudanças nas regras
| Regra | Nim padrão | Nim de Fibonacci |
|---|---|---|
| Pilhas | Nim padrãoVárias pilhas: 1, 3, 5 e 7 objetos por padrão, ou outro conjunto escolhido na configuração da mesa. | Nim de FibonacciUma pilha de 10, 15 (padrão) ou 20 objetos, escolhida como tamanho na configuração da mesa. |
| Primeira jogada | Nim padrãoTire qualquer quantidade de objetos de uma pilha, inclusive a pilha inteira. | Nim de FibonacciTire qualquer quantidade de objetos, menos a pilha inteira. |
| Jogadas seguintes | Nim padrãoTire qualquer quantidade de objetos de uma pilha, a cada vez. | Nim de FibonacciTire pelo menos 1 e no máximo o dobro do que o adversário tirou na jogada anterior, e não mais do que resta. |
| Objetivo | Nim padrãoMisère por padrão: quem tira o último objeto perde. A configuração pode mudar para o jogo normal, em que tirar o último objeto vence. | Nim de FibonacciSempre jogo normal: quem tira o último objeto vence. |
| Como jogar para vencer | Nim padrãoDeixe as pilhas com soma nim (o XOR bit a bit dos tamanhos) igual a zero, com um detalhe no final misère. | Nim de FibonacciEscreva a pilha como uma soma de números de Fibonacci, sem dois deles vizinhos na sequência, e tire o menor deles quando o limite permitir. O primeiro jogador perde com o melhor jogo exatamente quando a pilha inicial é um número de Fibonacci; 10, 15 e 20 não são, então o primeiro jogador pode vencer. |
História
Michael J. Whinihan descreveu o Nim de Fibonacci em 1963 no The Fibonacci Quarterly e atribuiu o jogo a Robert E. Gaskell, matemático da Oregon State University. O nome vem do papel que os números de Fibonacci 1, 2, 3, 5, 8, 13, 21 e assim por diante têm na solução.
O método vencedor se baseia no que hoje se chama teorema de Zeckendorf: todo número inteiro positivo é uma soma de números de Fibonacci, sem dois deles consecutivos, de exatamente uma maneira. O teorema leva o nome de Édouard Zeckendorf, embora Gerrit Lekkerkerker já o tivesse publicado em 1952.