🔢 mathematics

The Nim-Sum of a Random Integer Partition

Este artigo determina o comportamento assintótico de primeira ordem da proporção de posições de perda em partições inteiras de $N$ . A proporção tende a zero na escala $1/(\sqrt{N}\log N)$ , mas, após a normalização por sua escala natural, ela não converge; em vez disso, exibe um padrão de dente de serra diádico com uma transição de paridade de Poisson próximo a fronteiras diádicas.

Autores originais: Daewon Kim

Publicado 2026-08-28✓ Author reviewed ⓘ

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Daewon Kim

Artigo original sob licença CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um jogo jogado com pilhas de pedras, onde dois jogadores alternam turnos removendo qualquer número de pedras de uma única pilha. O objetivo é ser o último a realizar um movimento ou, inversamente, forçar o oponente a uma posição onde ele não tenha um movimento vencedor. Este é o jogo de Nim, um clássico enigma de estratégia que tem sido estudado por mais de um século. O segredo para vencer não reside em contar o número total de pedras, mas em uma forma específica de combinar os tamanhos das pilhas usando uma regra que mistura adição e subtração de uma maneira binária. Se essa combinação resultar em zero, o jogador cujo turno é mover-se está destinado a perder, assumindo que seu oponente jogue perfeitamente. Por décadas, matemáticos sabem como identificar essas posições de derrota para qualquer arranjo específico de pilhas. Mas uma questão mais profunda e elusiva permanecia: se você simplesmente reunir um número fixo de pedras e as dividisse em pilhas aleatoriamente, com que frequência esse arranjo acabaria sendo um de derrota?

Esta questão situa-se na interseção entre a teoria dos jogos e o estudo das partições de inteiros, que é o campo matemático preocupado com como um número pode ser decomposto em números inteiros menores. Embora as regras para vencer um único jogo sejam precisas e determinísticas, o comportamento desses jogos quando a posição inicial é escolhida aleatoriamente é surpreendentemente complexo. Uma questão natural é se a frequência dessas posições de derrota se estabiliza em um padrão assintótico simples à medida que o número total de pedras cresce. No entanto, o novo trabalho de Daewon Kim, da Universidade do Havaí em Mānoa, revela que a resposta é muito mais intrincada do que uma simples estabilização. À medida que o número de pedras aumenta, a probabilidade bruta de encontrar uma posição de derrota diminui, aproximando-se de zero. No entanto, se ajustarmos essa probabilidade para compensar essa queda natural, descobrimos que a densidade normalizada não se estabiliza. Em vez de suavizar-se em uma média constante, essa densidade oscila em um padrão dentado e repetitivo que nunca se estabiliza verdadeiramente, não importa quão grande o número de pedras se torne.

A pesquisa de Kim foca no caso específico onde o número total de pedras é par, pois as regras do jogo tornam impossível que um total ímpar forme uma posição de derrota. Ao realizar contagens exatas para cada tamanho total de pilha, o estudo determina exatamente como a densidade de uma posição de derrota se comporta conforme o número total de pedras aumenta. Os achados mostram que esta densidade normalizada não se aproxima de um único valor constante. Em vez disso, ela flutua violentamente, subindo e descendo em um padrão de dente de serra que se repete cada vez que a escala natural associada ao tamanho do problema cruza uma potência de dois. Se você fosse grafar a densidade contra o tamanho da pilha, veria uma linha que sobe constantemente de um ponto baixo para um ponto alto, depois cai bruscamente de volta, apenas para começar a subir novamente. Este ciclo se repete indefinidamente, o que significa que a densidade normalizada pode estar em qualquer lugar entre um e dois vezes um valor de base específico, dependendo inteiramente de onde você está neste ciclo.

O mecanismo que impulsiona este comportamento está enraizado na natureza binária da regra de vitória do jogo. Quando um grande número é decomposto em partes menores, as partes menores agem como uma fonte de aleatoriedade que embaralha os bits inferiores dos números binários, fazendo com que pareçam uniformes e imprevisíveis. As partes maiores são tão raras que raramente influenciam o resultado. No entanto, existe uma faixa específica de tamanhos de partes intermediários que atua como um gargalo crítico. Nesta faixa, as partes são grandes o suficiente para serem significativas, mas não tão grandes a ponto de desaparecerem. O número de partes caindo nesta faixa específica determina o resultado. Como essa faixa de tamanhos muda conforme o número total de pedras cresce, o equilíbrio do jogo inclina-se para trás e para frente. Quando a escala natural cruza o limiar de uma potência de dois, o equilíbrio inverte-se, fazendo com que a densidade salte.

Para entender isso, pode-se comparar o processo a um relógio que se reinicia toda vez que atinge uma certa hora, mas cujos ponteiros se movem a uma velocidade que muda com o próprio tamanho do relógio. À medida que o número total de pedras aumenta, a faixa crítica de tamanhos de partes move-se para cima. A densidade de uma posição de derrota depende de se esta faixa móvel contém um número par ou ímpar de partes. A paridade do número de partes nesta faixa crítica é o principal motor dessa oscilação. Como a distribuição das partes é governada por uma lei que se assemelha a uma distribuição de Poisson, a chance de ter um número par ou ímpar de partes nesta faixa oscila. Esta oscilação cria o padrão de dente de serra. A pesquisa confirma que, à medida que o número total de pedras cresce, a densidade normalizada não converge para um único número. Em vez disso, o conjunto de todos os valores possíveis que ela se aproxima preenche todo o intervalo entre um e dois vezes um fator de escala específico.

O estudo também se estende além das posições de derrota. Ele mostra que para cada alvo fixo de nim-sum, a densidade tem o mesmo decaimento de primeira ordem e, após a mesma normalização, segue o mesmo perfil de dente de serra diádico. Isso sugere que a estrutura binária do jogo deixa uma assinatura permanente na distribuição aleatória das pilhas, uma assinatura que se recusa a ser suavizada pela magnitude dos números envolvidos.

Para verificar estas previsões teóricas, o autor realizou cálculos exatos para cada possível arranjo de pedras até um total de vinte mil. Em vez de apenas amostrar arranjos aleatórios, ele utilizou uma abordagem computacional sofisticada que tratou o problema como um enorme exercício de contagem, utilizando algoritmos especializados para lidar com os bilhões de combinações possíveis sem precisar enumerar cada partição individualmente. Os resultados destes cálculos coincidiram com as previsões teóricas com uma precisão notável, confirmando que o padrão de dente de serra é real e não um artefato do modelo matemático. Os dados mostraram que a densidade sobe e desce exatamente como a teoria previu, com as transições nítidas ocorrendo nos momentos precisos em que a escala natural cruza uma potência de dois.

A pesquisa também investiga a natureza da transição entre estes picos e vales. Embora o gráfico pareça ter saltos nítidos e descontínuos, a análise de tamanhos finitos indica que estes saltos não são instantâneos, mas sim suavizados dentro de uma janela cada vez menor, sendo o movimento governado pela paridade do número de partes na faixa crítica. À medida que o número total de pedras aumenta, a janela na qual este suavizamento ocorre torna-se mais estreita, fazendo com que os saltos pareçam cada vez mais nítidos ao olhar nu, embora permaneçam matematicamente contínuos. Este fenômeno explica por que o padrão parece tão serrilhado nos dados, mesmo que a matemática subjacente seja suave.

Em última análise, este trabalho fornece uma descrição completa de como as posições de derrota estão distribuídas no jogo de Nim quando a configuração inicial é escolhida ao acaso. Ele resolve uma questão de longa data sobre a frequência destas posições, mostrando que elas não seguem uma tendência simples e constante. Em vez disso, são governadas por uma interação complexa entre o tamanho das pilhas e a estrutura binária do jogo. As descobertas destacam um princípio mais amplo na matemática: mesmo em sistemas que parecem aleatórios e suaves, estruturas aritméticas profundas podem criar padrões nítidos e persistentes que resistem à média. A natureza binária do jogo garante que um bloco específico de informação permaneça visível e influente, não importa quão grande o sistema se torne, criando um ritmo que se repete para sempre à medida que os números aumentam.

Resumo Técnico: A Soma de Nim de uma Partição Inteira Aleatória

Enunciado do Problema
O artigo investiga as propriedades enumerativas de posições ordinárias de Nim com um número total fixo de fichas, $N$ . No Nim, uma posição é definida por um multiconjunto de tamanhos de pilhas. Pelo teorema de Bouton, uma posição é perdedora se, e somente se, o OU exclusivo (XOR) bit a bit dos tamanhos das pilhas for zero. Quando a ordem das pilhas é ignorada, essas posições correspondem a partições inteiras de $N$ .

O problema central é determinar o comportamento assintótico da razão $a_N / p(N)$ , onde $p(N)$ é o número total de partições de inteiros de $N$ , e $a_N$ é o número de tais partições onde o XOR das partes é zero. Embora a restrição de paridade seja imediata ( $a_N = 0$ para $N$ ímpar porque a soma e o XOR compartilham o mesmo bit menos significativo), para $N$ par a densidade bruta tende a zero, enquanto a densidade apropriadamente normalizada apresenta um comportamento oscilatório não convergente e complexo que as assintóticas de partições padrão não capturam.

Metodologia
O autor emprega uma abordagem multifacetada combinando decomposição combinatória, modelagem probabilística e teoria analítica dos números:

Decomposição Combinatória: O artigo decompõe uma partição $\lambda$ em dois componentes baseados nas multiplicidades de suas partes. Se uma parte $j$ aparece $c_j$ vezes, ela é escrita como $c_j = 2r_j + \varepsilon_j$ , onde $\varepsilon_j \in \{0, 1\}$ . As cópias pares ( $2r_j$ ) se cancelam na soma XOR, deixando apenas o "núcleo ímpar" (partes com $\varepsilon_j=1$ ). Isso reduz o problema à análise do XOR de uma partição em partes distintas.
Amostragem de Boltzmann: Para explorar a independência, o estudo muda para o modelo de Boltzmann onde o tamanho total é aleatório. Neste modelo, os indicadores para a inclusão de partes distintas são variáveis de Bernoulli independentes. A probabilidade de uma soma XOR zero é analisada particionando os inteiros em três intervalos diádicos em relação a uma escala crítica $J$ $J$ :
- Bloco Inferior ( $[1, J)$ ): Estas partes pequenas aleatorizam os dígitos binários inferiores, criando uma distribuição quase uniforme sobre os bits baixos.
- Bloco Crítico ( $[J, 2J)$ ): Cada inteiro em $[J, 2J)$ possui o mesmo bit de maior ordem $J$ ; esse bit de maior ordem do XOR do bloco é zero se, e somente se, o número de partes selecionadas neste intervalo for par, e, condicionado a isso, o bloco inferior deve corresponder ao resíduo restante dos bits baixos.
- Bloco Superior ( $[2J, \infty)$ ): Estas partes grandes são raras e contribuem de forma negligenciável para o termo de primeira ordem.
Hierarquia Diádica e Análise de Walsh: O autor utiliza a análise de Walsh (ortogonalidade de caracteres sobre $\mathbb{F}_2$ ) para derivar fórmulas finitas exatas e para refinar a aproximação. A hierarquia diádica refina a aproximação de Boltzmann a uma ordem algébrica arbitrária, enquanto a transferência para partições de tamanho fixo é estabelecida apenas em primeira ordem.
Análise de Ponto de Sela: Para transferir os resultados do modelo de Boltzmann (tamanho aleatório) de volta para partições de tamanho fixo, o artigo utiliza métodos de ponto de sela nas funções geratrizes. Ele identifica dois pontos de sela iguais (próximos a $q = e^{-t_N}$ e $q = -e^{-t_N}$ ) devido à paridade da função geratriz para posições perdedoras.
Computação Exata: Um algoritmo exato baseado na fórmula de Walsh e no Teorema Chinês dos Restos (CRT) é implementado para computar $a_N$ até $N=20.000$ . Isso serve para verificar as fórmulas assintóticas e analisar correções de tamanho finito.

Resultados Principais
O artigo estabelece o comportamento assintótico de primeira ordem da densidade de posições perdedoras. Seja $\tau_N = \pi/\sqrt{6N}$ e $B_N = \log(1/\tau_N)/\tau_N$ . Seja $J_N$ a potência de dois mais próxima de $B_N$ em distância multiplicativa, e defina $\Lambda_N = e^{-\tau_N J_N}/\tau_N$ .

Para $N$ par, a razão é dada por:
$\frac{a_N}{p(N)} = \frac{1 + e^{-2\Lambda_N} + o(1)}{J_N}$

As principais descobertas incluem:

Não Convergência: A densidade normalizada $B_N \frac{a_N}{p(N)}$ não converge, e seu conjunto de limites subsequentes é o intervalo completo $[1, 2]$ .
Dente de Serra Diádico: O comportamento segue um padrão de "dente de serra diádico". À medida que $N$ aumenta, o valor sobe de 1 para 2 durante cada fase binária (conforme $B_N$ cruza potências de dois) e cai de volta para 1 quando a escala cruza uma nova potência de dois.
Suavização de Poisson: A descontinuidade aparente nos limites diádicos é suavizada em uma escala decrescente pela lei de paridade de uma variável aleatória de Poisson. Especificamente, se $N$ se aproxima de um limite tal que $\tau_N K - \log(1/\tau_N) \to c$ (onde $K$ é uma potência de dois), o limite é $1 + e^{-2e^{-c}}$ .
Nim-Somas Gerais: O resultado não é exclusivo para a soma XOR zero. Para qualquer soma de Nim alvo fixa $x$ , a densidade de partições com soma de Nim $x$ segue o mesmo perfil de primeira ordem ao longo da classe de paridade $N \equiv x \pmod 2$ .
Contagens Exatas: O artigo estende a sequência OEIS A048833 para o índice 10.000 (tamanho total $N=20.000$ ), fornecendo dados exatos que confirmam a escala prevista e a estrutura dos erros de tamanho finito.

Significância e Alegações
O artigo afirma fornecer a descrição assintótica completa de primeira ordem das posições de Nim perdedoras para partições inteiras irrestritas. Sua significância reside em revelar que uma estrutura aleatória "suave" (partições inteiras) retém um recurso aritmético nítido (paridade binária) devido à existência de um único bloco diádico crítico que permanece visível após os bits baixos serem aleatorizados e os bits altos tornarem-se negligenciáveis.

O trabalho demonstra que a densidade de posições perdedoras é da ordem de $\Theta(1/(\sqrt{N} \log N))$ , mas carece de uma constante assintótica única. O autor enfatiza que a "hierarquia diádica" permite refinamentos de ordem algébrica arbitrária, explicando por que as correções de tamanho finito são significativas mesmo quando o teorema de primeira ordem é válido. O artigo conclui que a não convergência é um recurso estrutural do problema, não uma falha da aproximação, e que a transição entre fases é governada pela paridade de uma variável de Poisson.

O artigo não pretende resolver o problema geral para somas de Nim alvo crescentes ou partições restritas, apontando-os como questões abertas naturais. Também evita alegar que a análise de correção de tamanho finito constitui um teorema completo de segunda ordem, pois depende de expansões formais em vez de limites uniformes para derivadas superiores.

Mais como este