O jogo dos Palitinhos/Nim

O jogo dos palitinhos, também conhecido como jogo de Nim, é uma competição entre dois jogadores, regidas pelas seguintes regras:

• Há 16 palitos distribuídos em quatro fileiras, contendo, respectivamente, 1, 3, 5 e 7 palitos.

• Os participantes jogam alternadamente. Uma jogada consiste em retirar qualquer quantidade positiva de palitos, desde que todos eles sejam retirados de uma única fileira.

• O jogador que retirar o último palito da mesa é considerado o perdedor do jogo!

A questão que se coloca é: Qual dos jogadores consegue garantir a vitória?

Além disso, se a condição de vitória fosse modificada para “Quem retirar o último palito do tabuleiro VENCE o jogo”, como isso afetaria a estratégia dos jogadores?

Estudemos o jogo em uma versão genérica simples.

Nesta versão, temos um número P arbitrário de palitos organizados em uma única fileira. Cada jogador, alternadamente, retira no máximo n palitos em sua vez (naturalmente, n deve ser suficiente menor que P para haver algumas rodadas).

Perguntas a serem respondidas:

• Qual a estratégia vencedora em função dos parâmetros P e n ?

• Sob que condições o vencedor será o primeiro (segundo) a jogar?

Abaixo, uma simulação com P=21 e n=3.

Qual a estratégia nesse exemplo?

Para saber um pouco mais sobre a matemática por trás de jogos finitos – Estratégias vencedoras.