O que é Jogo da subtração?
O jogo da subtração é o Nim com um limite em cada jogada. Você ainda tira objetos de uma pilha à sua escolha, mas pelo menos um e no máximo k, em que k é 2, 3, 4 ou 5, escolhido na configuração da mesa (3 por padrão). Você só pode tirar uma pilha inteira quando ela tem k objetos ou menos.
Todo o resto é como no jogo padrão: as pilhas iniciais vêm da mesma opção da configuração (1, 3, 5 e 7 por padrão), e a chave misère decide se tirar o último objeto faz perder (o padrão aqui) ou vencer. O teto muda a aritmética do jogo. Uma pilha grande não pode mais ser esvaziada de uma vez, então não serve para acertar a posição num só golpe, e o que importa em cada pilha é o resto da divisão do seu tamanho por k + 1.
Mudanças nas regras
| Regra | Nim padrão | Jogo da subtração |
|---|---|---|
| Jogadas | Nim padrãoTire um ou mais objetos de uma pilha, quantos quiser, até a pilha inteira. | Jogo da subtraçãoTire pelo menos 1 e no máximo k objetos de uma pilha; k é 2, 3, 4 ou 5, escolhido na configuração da mesa (3 por padrão). |
| Pilhas | Nim padrãoVárias pilhas: 1, 3, 5 e 7 objetos por padrão, ou outro conjunto escolhido na configuração da mesa. | Jogo da subtraçãoAs mesmas pilhas, escolhidas com a mesma opção. |
| 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. | Jogo da subtraçãoO mesmo, com a mesma chave misère. |
| Como jogar para vencer | Nim padrãoJogo normal: deixe as pilhas com soma nim (o XOR bit a bit dos tamanhos) igual a zero. Misère: o mesmo, até que só fossem sobrar pilhas de um objeto; então deixe um número ímpar delas. | Jogo da subtraçãoJogo normal: cada pilha conta como o resto da divisão do seu tamanho por k + 1, e você deixa esses restos com soma nim zero; uma pilha única está perdida para quem joga exatamente quando seu tamanho é múltiplo de k + 1. Misère: uma pilha única está perdida para quem joga exatamente quando seu tamanho é um a mais que um múltiplo de k + 1. |
História
Jogos de contagem com um teto em cada jogada são antigos. Os Problèmes plaisants et délectables de Claude-Gaspard Bachet de Méziriac, uma coletânea de recreações matemáticas publicada pela primeira vez em Paris em 1612, descrevem um jogo em que dois jogadores somam alternadamente um número de 1 a 10 a um total corrente, e quem chegar primeiro a 100 vence. O plano vencedor é atingir os totais 12, 23, 34 e assim por diante até 89, de 11 em 11: a mesma aritmética de uma pilha única de 100 da qual cada jogada tira de 1 a 10.
O próprio Nim recebeu nome e teoria completa de Charles L. Bouton em 1901. O trabalho de Roland Sprague (1935) e Patrick Grundy (1939) mostrou que todo jogo desse tipo, incluindo o jogo da subtração, se comporta como uma pilha de Nim de certo tamanho, e é assim que se resolve a versão com várias pilhas. Os jogos de subtração são um exemplo clássico na teoria dos jogos combinatórios, por exemplo em Winning Ways for your Mathematical Plays, de Elwyn Berlekamp, John Conway e Richard Guy.