Additive Subtraction Games

Este artigo determina a estrutura completa dos valores nim para jogos de subtração aditiva no regime quadrático primitivo, fornecendo uma prova definitiva para uma fórmula fechada clássica envolvendo expressões de Brakets do tipo Beatty que caracteriza as posições P e demonstrando que cada sequência de valores nim reside em um deslocamento linear dessas posições.

O essencial

Imagine que você está jogando um jogo de tabuleiro com duas pessoas, onde o objetivo é o último a fazer uma jogada válida vence (ou, dependendo da regra, o último a não conseguir mover perde). Neste jogo específico, chamado de "Jogo de Subtração Aditiva", vocês têm uma pilha de pedras e, em cada turno, podem remover um número específico de pedras: $a$, $b$ ou $a+b$.

O grande mistério da matemática é: quais são as posições seguras? Ou seja, se você deixar a pilha com um certo número de pedras, você garante a vitória, não importa o que o oponente faça?

Os autores deste artigo, Urban Larsson e Hikaru Manabe, resolveram um caso muito específico e complicado desse jogo. Eles descobriram uma "receita secreta" (uma fórmula matemática) que diz exatamente onde estão essas posições de vitória.

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Jogo e o Problema

Pense no jogo como uma corrida em uma estrada de pedras.

• Você pode pular $a$ pedras, $b$ pedras ou $a+b$ pedras.
• Existe um padrão escondido: se você estiver em uma posição "segura" (chamada de P-posição ou posição de Perdedor para quem começa), qualquer pulo que você fizer levará a uma posição "perigosa" (onde o oponente pode te vencer).
• O problema é que, para certos valores de $a$ e $b$, esse padrão de posições seguras é muito difícil de prever. Ele não é simples como "todos os números pares". Ele é "quadrático", o que significa que a distância entre as posições seguras muda de forma irregular, como se a estrada tivesse buracos de tamanhos variados.

2. A "Fórmula Mágica" (A Expressão de Colchetes)

Os matemáticos já sabiam, desde 1982, que existe uma fórmula para encontrar essas posições seguras. A fórmula parece estranha, mas imagine-a como um filtro de peneira:

$$w_n = n + a \cdot \lfloor \frac{n}{a} \rfloor + b \cdot \lfloor \frac{n}{\delta} \rfloor$$

• O que isso faz? Imagine que você tem uma régua com marcas. A fórmula diz: "Pegue o número $n$, e adicione um extra baseado em quantas vezes $n$ cabe em $a$ e em $\delta$".
• O problema: Ninguém tinha provado por que essa fórmula funcionava para o caso mais difícil (chamado de "regime quadrático primitivo"). Era como ter a receita de um bolo perfeito, mas ninguém sabia explicar por que os ingredientes se misturavam daquela forma específica.

3. A Descoberta: O Padrão de 4 Cores

Os autores provaram que, neste jogo, todos os números naturais (todas as posições possíveis da pilha) podem ser divididos em 4 grupos de cores, e cada cor tem um significado:

1. Cor 0 (Posições de Vitória para quem joga depois): São as posições seguras calculadas pela fórmula mágica acima. Se você deixar a pilha aqui, você venceu.
2. Cor 1 (Posições de Vitória para quem joga agora): São as posições seguras + um pulo de tamanho $a$. Se você estiver aqui, você pode pular $a$ e deixar o oponente na Cor 0.
3. Cor 2: São posições onde você pode forçar o oponente a cair na Cor 0, mas de uma forma diferente (subtraindo $b$).
4. Cor 3: Um grupo especial e mais raro, que surge de uma "colisão" matemática entre os padrões.

A grande sacada do artigo é mostrar que esses 4 grupos cobrem todos os números possíveis. Não sobra nenhum número sem cor. É como se o jogo fosse um mosaico perfeito feito de 4 tipos de azulejos.

4. A Analogia do "Tráfego de Carros" (A Parte Difícil)

A parte mais complexa do artigo (Seção 4) trata de como esses grupos se encaixam.
Imagine que as posições seguras (Cor 0) são carros em uma estrada. A fórmula diz onde eles estão.

• Às vezes, dois carros parecem estar muito perto um do outro.
• O jogo tem regras que dizem: "Você não pode pular de um carro para o outro se a distância for exatamente $a$, $b$ ou $a+b$".
• Os autores estudaram o que acontece quando tentamos mover a fila de carros inteira para trás (subtraindo um valor $\delta$).
• Eles descobriram que, em certos momentos, um carro da nova fila vai bater (colidir) com um carro da fila original.
• A descoberta: Eles contaram exatamente quantas dessas "colisões" acontecem em um ciclo completo do jogo. É como contar quantos carros estacionados em uma rua de um bairro específico vão se sobrepor se você mover a rua inteira para a esquerda.

Eles provaram que o número de colisões segue uma regra simples e elegante: $a \times (\delta - a)$.

5. Por que isso importa?

• Para os Jogadores: Se você jogar esse jogo, agora sabe exatamente como vencer. Basta calcular a fórmula e ver em qual "cor" a pilha está.
• Para a Matemática: Este jogo é um "laboratório" para entender problemas muito mais complexos. Resolver esse caso "quadrático" é como desvendar o núcleo de uma cebola. Se entendermos como essas fórmulas funcionam aqui, podemos entender jogos com regras ainda mais estranhas no futuro.
• A Prova: Eles preencheram a lacuna de 40 anos, provando matematicamente que a fórmula antiga estava correta e explicando a estrutura oculta por trás dela.

Resumo em uma frase

Os autores desvendaram o segredo de um jogo de pedras complexo, provando que as posições de vitória seguem um padrão matemático preciso que pode ser dividido em quatro grupos interligados, como se o jogo fosse um mosaico perfeito onde cada peça tem seu lugar exato.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Additive Subtraction Games" de Urban Larsson e Hikaru Manabe, apresentado em português.

Resumo Técnico: Jogos de Subtração Aditivos no Regime Quadrático Primitivo

1. O Problema

O artigo aborda os jogos de subtração aditivos, uma classe de jogos combinatórios de dois jogadores jogados com pilhas de contadores.

• Regras: Os jogadores alternam removendo um número $s$ de contadores, onde $s$ pertence a um conjunto fixo $S$. O jogador que não consegue realizar uma jogada (porque todas as subtrações levariam a números negativos) perde.
• Objetivo: Determinar os valores de Nim (ou nimbers) para cada posição do jogo. As posições com valor 0 são chamadas de posições P (posições perdedoras para o jogador que começa), enquanto as demais têm valores positivos.
• Foco Específico: O estudo concentra-se no conjunto de subtração $S = \{a, b, a+b\}$, onde $b = a + \delta$. A análise é restrita ao regime quadrático primitivo, definido pelas condições:
  • $a < \delta < 2a$
  • $\gcd(a, \delta) = 1$
• Contexto Histórico: O problema foi mencionado em Winning Ways (Berlekamp et al., 1982), que propôs uma fórmula fechada para as posições P baseada em expressões do tipo Beatty (envolvendo funções piso). No entanto, uma prova completa dessa fórmula nunca havia sido publicada na literatura até este trabalho. Estudos anteriores (Miklós e Post, 2024) estabeleceram a periodicidade dos resultados, mas não forneceram a estrutura completa dos valores de Nim nem a fórmula fechada.

2. Metodologia

Os autores utilizam uma abordagem híbrida combinando teoria dos jogos combinatórios e teoria dos números elementar.

• Fórmula Candidata para Posições P:
  A sequência de posições P é definida pela fórmula fechada:
  $$w_n = n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$$
  onde $W_0 = \{w_n : n \ge 0\}$.

• Estrutura de Partição:
  O artigo demonstra que o conjunto dos números naturais $\mathbb{N}_0$ é particionado em quatro conjuntos disjuntos, correspondentes aos valores de Nim 0, 1, 2 e 3:

  • $W_0$: Valores de Nim 0 (Posições P).
  • $W_1 = W_0 + a$: Valores de Nim 1.
  • $W_2 = W_0 - b$: Valores de Nim 2.
  • $W_3 = (W_0 - \delta) \setminus W_0$: Valores de Nim 3.

• Método de Prova:
  A validação é feita por indução forte no tamanho da posição, verificando a consistência da regra mex (Minimum Excluded value):

  1. Anti-colisão: Provar que não existem jogadas válidas entre posições do mesmo conjunto $W_i$ (garantindo que o valor não se repita indevidamente).
  2. Alcançabilidade: Provar que de qualquer posição em $W_i$ ($i > 0$), é possível mover para posições que cobrem todos os valores de Nim menores que $i$.

• Análise Numérica (Seção 4):
  O cerne da prova técnica reside na contagem de "colisões" $\delta$. Os autores analisam a estrutura das lacunas (gaps) na sequência $w_n$. Eles definem janelas de colisão onde a soma de lacunas consecutivas é igual a $\delta$. A prova envolve:

  • Classificar as lacunas com base nas classes residuais de $n$ módulo $a$ e $\delta$.
  • Definir parâmetros $L$ e $R$ (número de lacunas de tamanho 1 à esquerda e à direita de uma lacuna especial de tamanho $a+1$).
  • Contar o número de janelas de colisão válidas para cada resíduo, dividindo o problema em três regiões (restrita à esquerda, irrestrita, restrita à direita).

3. Contribuições e Resultados Chave

• Prova da Fórmula Fechada: O artigo fornece a primeira prova completa e rigorosa da fórmula de Winning Ways para as posições P no regime quadrático primitivo.
• Teorema Principal (Teorema 1): Estabelece que, sob as condições $a < \delta < 2a$ e $\gcd(a, \delta)=1$:
  • $W_0$ são exatamente as posições com valor de Nim 0.
  • $W_0 + a$ são as posições com valor 1.
  • $W_0 - b$ são as posições com valor 2.
  • $(W_0 - \delta) \setminus W_0$ são as posições com valor 3.
  • A união desses quatro conjuntos cobre todos os números naturais.
• Estrutura de Periodicidade:
  • O período de índice (contagem de $n$) é $a\delta$.
  • O período de pilha (tamanho do número $w_n$) é $(3\delta + a)a$.
  • O artigo demonstra que apenas quatro tamanhos de lacunas aparecem na sequência: $\{1, a+1, b+1, a+b+1\}$.
• Contagem de Colisões (Teorema 7): Um resultado central é a contagem exata do número de colisões $\delta$ (onde $w_n - w_m = \delta$) em um período. O número de tais colisões é dado por $a \cdot d$, onde $d = \delta - a$. Isso é crucial para provar que o conjunto $W_3$ tem o tamanho exato necessário para completar a partição dos naturais.
• Complexidade Quadrática: O trabalho confirma que o regime quadrático primitivo captura a fonte da complexidade quadrática do problema. Fora desse regime, a complexidade reduz-se a linear ou mantém-se quadrática de forma trivial.

4. Significado e Implicações

• Resolução de um Problema Aberto: O artigo resolve uma questão aberta de décadas presente em Winning Ways, fornecendo não apenas a fórmula, mas a estrutura completa dos valores de Nim (incluindo os valores 2 e 3, que não eram totalmente caracterizados).
• Conexão com Teoria dos Números: O trabalho destaca a profunda ligação entre jogos combinatórios e propriedades de expressões de "bracket" (funções piso) com módulos racionais. A análise das "janelas de colisão" e a distribuição de resíduos oferece novas ferramentas para estudar sequências definidas por funções piso.
• Limites da Teoria de Beatty: O artigo distingue a sequência $w_n$ das sequências de Beatty clássicas (irracionais) e das conjecturas de Fraenkel (partições de $\mathbb{N}$). Mostra que a estrutura de densidade das posições P neste jogo não segue o padrão geométrico de Fraenkel, sugerindo que problemas de colisão em expressões de bracket com termos fixos constituem uma nova classe de problemas na teoria dos números.
• Futuro: Os autores levantam questões sobre a generalização para expressões com mais de três termos e para outros regimes de parâmetros, sugerindo que a complexidade deste regime primitivo é fundamental para a teoria geral de jogos de subtração.

Em suma, o artigo oferece uma solução completa e elegante para um problema clássico de jogos combinatórios, utilizando uma análise numérica sofisticada para desvendar a estrutura oculta das posições vencedoras e perdedoras.