Mostre que se um jogo do nim começar com duas pilhas com o mesmo número de pedras, contanto que este número seja pelo menos dois, então o segundo jogador ganha quando ambos os jogadores seguirem estratégias ótimas.

Passo 1

O enunciado pede para mostrar que, num jogo de Nim normal com exatamente duas pilhas de mesmo tamanho n\ge2, o segundo jogador tem uma estratégia vencedora se ambos jogarem de forma ótima. Vamos usar a teoria de Nim, em particular as noções de nim-sum e de posições P (perdedoras para o jogador a mover) e N (vantajosas para o jogador a mover).

Passo 2

Calculemos o nim-sum da posição inicial. Para duas pilhas de tamanho igual n, temos
n \oplus n = 0.
Por definição, posições com nim-sum zero são P-posições, ou seja, o jogador que vai se mover a partir delas não consegue forçar a vitória contra um adversário que mantenha a estratégia ótima.

Passo 3

Qualquer jogada do primeiro jogador em uma P-posição leva a uma posição com nim-sum diferente de zero (uma N-posição). A chave é que, a partir de uma N-posição, existe sempre uma jogada que restaura o nim-sum para zero, voltando a uma P-posição.

Passo 4

Uma forma explícita de restaurar o nim-sum é a estratégia do “espelho”: sempre que o primeiro jogador retira k pedras de uma das pilhas, o segundo jogador retira exatamente k pedras da outra pilha. Como as pilhas começam iguais e permanecem iguais após cada par de jogadas, a pilha espelhada terá sempre pelo menos k pedras. Assim, depois da resposta do segundo jogador, as duas pilhas voltam a ser iguais e o nim-sum fica novamente zero.

Passo 5

Seguindo o espelhamento, o segundo jogador garante que, após sua jogada, a posição será sempre P. No final, quem fica sem movimento é o primeiro jogador, quando as pilhas chegarem a (0,0), e o segundo jogador terá feito a última jogada, levando à sua vitória.

Resposta

O segundo jogador vence, pois a posição inicial (n,n) é P-posição n\oplus n=0 e ele pode usar a estratégia de espelho para manter sempre nim-sum zero.

Exercícios de Livros Relacionados