Solução – Jogo do NIM

A estratégia que apresentamos a seguir é considerada da forma que o segundo jogador sempre ganhe. Uma forma de representar cada estágio do jogo é  considerando uma quádrupla de números, estes representam o número de palitos em cada fileira. Está quádrupla será dada por (f_1,f_2 ,f_3 , f_4),tal que f_1+f_2+f_3+f_4 = N, onde N representa o número total de palitos naquele estágio do jogo.  Na configuração da figura 1, temos N=16, f_1=1, f_2=3, f_3=5 e f_3 =7. Agora, vamos escrever o número de palitos, em cada fileira, na base 2:

Somando (normalmente), temos 224. Este valor será denominado chave do jogo e sempre que este valor for composto apenas por algarismos pares, diremos que é uma posição segura e quando algum dos algarismos for ímpar, diremos que é uma posição insegura.  

Observemos que se retirarmos um palito da última fileira, passamos a ter 

Cuja soma é 223 e daí o jogador que fez esta retirada terminou sua jogada em uma posição insegura. Agora observemos que se retirarmos dois palitos da última fileira, temos  

e a soma será 214 e assim este jogador também termina sua jogada em uma posição insegura. Assim, concluiremos que independente da quantidade de palitos que o jogador que está em uma posição segura faça, ele terminará sua jogada em uma posição insegura. 

Exemplo de jogo:

Suponha que Patrícia e Vitória serão as jogadoras e que Patrícia começará jogando. Ou seja, Patrícia começa o jogo em uma posição segura e pelo que já observamos acima, podemos concluir que ela sempre terminará sua jogada em uma posição insegura. 

É importante observar que, se o jogador começa sua jogada em uma posição insegura, então com uma jogada conveniente ele pode terminar sua jogada em uma posição segura. Logo, podemos supor que Vitória terminará sua jogada em uma posição segura. Novamente, independente da quantidade de palitos que Patrícia retire, ela terminará sua jogada em uma posição insegura e mais uma vez, com uma jogada conveniente, Vitória terminará sua jogada em uma posição segura. Sucessivamente, teremos que Patrícia sempre terminará sua jogada em uma posição insegura e que Vitória sempre terminará sua jogada em uma posição segura. O jogo termina quando o último palito é retirado da mesa, isto é, a soma das fileiras deve ser 000. Assim, concluímos que a vencedora terminará sua jogada em uma posição segura. Portanto, seguindo esta estratégia, apenas Vitória pode vencer. 

Se alterarmos a regra do jogo de tal modo que o vencedor seja aquele que obrigar o adversário a tirar o último palito, o raciocínio é o mesmo, mas o objetivo agora é chegar na soma 001. Neste caso, a estratégia consiste em manter todos os algarismos pares, exceto o último, que deve ser mantido ímpar. 

Solução Alternativa: Soma \mathbb{Z}_2 (pdf).