O que é o jogo da subtração e como jogá-lo corretamente
O jogo da subtração é um conceito de teoria dos jogos combinatórios onde dois jogadores alternadamente subtraem um divisor próprio de um número inteiro positivo. O jogador que reduz o número a zero vence. Parece simples na descrição, mas a análise estratégica por trás exige um entendimento claro de números primos, divisores próprios e posições vencedoras versus perdedoras. Vou explicar o método primeiro porque a definição sozinha não ajuda muito. A estratégia gira em torno de identificar as posições P (perdedoras para o jogador que está para mover) e as posições N (vencedoras). Uma posição é P se todos os movimentos possíveis levam a uma posição N. Uma posição é N se existe pelo menos um movimento que leva a uma posição P. Começando do zero — que é uma posição P, já que quem chega lá já ganhou no turno anterior — você constrói a tabela para cima.
Jogo da subtração: análise prática e armadilhas comuns
Na prática, o que a maioria das pessoas não percebe imediatamente é que números primos criam uma dinâmica totalmente diferente de números compostos. Quando o número atual é primo, o único divisor próprio é 1, então o jogador é forçado a subtrair 1. Isso significa que em qualquer posição prima, o controle do turno praticamente sai das mãos. Eu já vi gente gastar horas tentando encontrar padrões em números primos quando a solução real era simplesmente aceitar que oprimos impõem movimento obrigatório e focar em como explorar isso. O problema específico que eu encontrei — e que resolveu com uma gambiarra digna de um debug às 3h da manhã — foi com números muito grandes, acima de 10.000. A abordagem recursiva clássica trava porque o número de subproblemas cresce exponencialmente. A solução foi usar programação dinâmica com memoização, preenchendo um array de menor para maior, e armazenando apenas os resultados P e N. Isso reduziu o tempo de cálculo de algo em torno de minutos para frações de segundo.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Aqui está um exemplo concreto. Começamos com o número 6. Os divisores próprios de 6 são 1, 2 e 3. Se o primeiro jogador subtrair 3, sobra 3. O segundo jogador, diante do 3 (que é primo), só pode subtrair 1, restando 2. O primeiro jogador então subtrai 1, restando 1. O segundo subtrai 1 e chega a 0, vencendo. Mas se o primeiro jogador tivesse escolhido subtrair 2 de 6, sobraria 4. Do 4, os divisores próprios são 1 e 2. Se o segundo subtrair 2, sobra 2, e o primeiro pode subtrair 1 deixando 1, depois o segundo subtrai 1 e perde. Esse tipo de análise em árvore é viável para números pequenos, mas rapidamente fica ingovernável sem a tabela dinâmica. O que os tutoriais geralmente omitem é que a configuração inicial dos movimentos permitidos muda completamente o jogo. No jogo da subtração padrão, qualquer divisor próprio é permitido. Mas se você restringir a apenas divisores ímpares, ou apenas a potências de 2, as posições P e N se reorganizam de forma contra-intuitiva. Por exemplo, com a restrição de divisores ímpares, o número 4 se torna uma posição P (perdedora para quem move), enquanto no jogo padrão ele é N. Pequenas alterações nas regras criam análises completamente distintas.
Uma limitação séria que ninguém enfatiza o suficiente: esse método funciona bem para números até algumas centenas de milhares com memória suficiente. Acima disso, o array de memoização consome RAM demais. Para números da ordem de milhões ou bilhões, a única saída viável é procurar padrões periódicos nos resultados P/N, o que ainda é um problema aberto em muitos casos. Não existe fórmula fechada conhecida para o jogo da subtração geral. Se você quer implementar isso, a abordagem mais prática é um script Python simples com um array booleano. Inicialize o índice 0 como True (posição P). Para cada número i a partir de 1, verifique todos os divisores próprios d de i. Se qualquer divisor levar a uma posição False (N), então i é True (P). Senão, i é False. Esse código roda instantaneamente para i até 100.000 em uma máquina comum.
O jogo da subtração é um dos melhores exercícios para entender como teoria dos jogos e teoria dos números se encontram. A parte divertida não é decorar a tabela de posições — é perceber como pequenas variações nas regras produzem comportamentos qualitativamente diferentes. E a parte útil é saber quando desistir da análise exata e partir para heurísticas ou padrões aproximados.
