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
, 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
, temos
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
pedras de uma das pilhas, o segundo jogador retira exatamente
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
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
, e o segundo jogador terá feito a última jogada, levando à sua vitória.
Resposta
O segundo jogador vence, pois a posição inicial
é P-posição
e ele pode usar a estratégia de espelho para manter sempre nim-sum zero.