🔢 mathematics

Structural Conjectures for 4 x n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry

Este artigo apresenta um estudo computacional extensivo do jogo Chomp 4 x n, tabulando mais de 4,3 milhões de posições P para propor quatro conjecturas estruturais relativas a extensões únicas, razões assintóticas, padrões modulares de período 112 e geometria de cone linear que revelam uma estrutura determinística mais rica no jogo do que anteriormente suspeitava-se.

Autores originais: Arnav Garg

Publicado 2026-04-30

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Arnav Garg

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

Imagine um jogo chamado Chomp jogado em uma barra de chocolate retangular. A barra é composta por uma grade de quadrados. Dois jogadores se alternam. Em sua vez, você escolhe um quadrado e "come" ele, junto com tudo que está acima e à direita dele. O problema? O quadrado do canto superior esquerdo é envenenado. Se você for forçado a comer esse último quadrado, você perde.

Matemáticos descobriram a estratégia vencedora para barras de chocolate muito pequenas ou muito específicas, mas para uma barra com 4 quadrados de largura e n quadrados de comprimento, o padrão era um mistério até agora.

Este artigo é como uma história de detetive massiva e de alta velocidade, onde o autor usou um computador super-rápido para mapear cada única "posição perdedora" (um ponto onde o jogador da vez perderá se o oponente jogar perfeitamente) para barras de chocolate com até 500 quadrados de comprimento.

Aqui está o que o autor descobriu, explicado de forma simples:

1. A Regra "Um e Pronto" (Extensão Única)

Pense na barra de chocolate como tendo quatro fileiras. As três fileiras superiores têm certos comprimentos (vamos chamá-los de A, B e C).

A Descoberta: O autor descobriu que, para qualquer combinação específica de comprimentos das três fileiras superiores, há no máximo uma comprimento específico para a quarta fileira que cria uma "posição perdedora".
A Analogia: Imagine que você está construindo uma torre com três blocos de tamanhos específicos. Se você quiser que a torre seja "instável" (uma posição perdedora), há apenas um tamanho específico para o quarto bloco que a tornará instável. Você não pode escolher qualquer quarto bloco; a matemática força uma única resposta única. Isso sugere que o jogo é muito mais previsível e "determinístico" do que qualquer um pensava.

2. A "Proporção Áurea" do Chocolate (Razões Assintóticas)

À medida que a barra de chocolate fica cada vez mais longa (imagina esticá-la até o infinito), o autor observou que as fileiras se estabilizam em uma forma específica.

A Descoberta: Os comprimentos das fileiras param de mudar aleatoriamente e começam a seguir um padrão fixo. Se a fileira superior tem comprimento 100, a segunda fileira terá sempre cerca de 76 unidades de comprimento, a terceira cerca de 50 e a quarta cerca de 22.
A Analogia: É como uma árvore crescendo. Não importa o quanto a árvore cresça, os galhos sempre crescem nas mesmas proporções relativas. O autor calculou essas "taxas de crescimento", mas ainda não conseguiu encontrar uma fórmula matemática simples (como uma fração) para descrevê-las exatamente. Elas estão próximas de alguns números famosos, mas o segredo exato permanece oculto.

3. O "Ritmo Oculto" (Período-112)

O autor procurou por um padrão repetitivo nos dados, como uma batida em uma música.

A Descoberta: Os dados repetem um padrão específico a cada 112 passos.
A Analogia: Imagine um relógio que não tiquetaqueia a cada segundo, mas tem um ritmo complexo que se reinicia a cada 112 tiques. O autor descobriu que esse ritmo é provavelmente uma mistura de dois ritmos menores: um que se repete a cada 7 passos (herdado da versão do jogo com 3 fileiras) e outro misterioso que se repete a cada 8 passos. O número 112 é apenas o "mínimo múltiplo comum" onde esses dois ritmos sincronizam perfeitamente.

4. A Forma de "Funil" (Geometria de Cone Linear)

Se você plotar todas as possíveis "posições perdedoras" em um gráfico, elas não parecem uma nuvem aleatória de pontos.

A Descoberta: Elas formam uma forma organizada, semelhante a um funil (um cone). À medida que as fileiras ficam mais longas, a "largura" das posições perdedoras válidas cresce em uma linha reta e previsível.
A Analogia: Imagine despejar areia em um funil. A areia não se acumula aleatoriamente; ela forma um cone suave e alargado. O autor descobriu que as posições perdedoras "válidas" neste jogo se encaixam em uma forma suave e alargada semelhante, com uma pequena oscilação causada por aquele ritmo de 112 passos mencionado anteriormente.

Por Que Isso Importa?

Antes deste artigo, a versão de 4 fileiras do Chomp era uma caixa preta. Sabíamos que o primeiro jogador geralmente vence, mas não sabíamos por que ou como as posições perdedoras estavam dispostas.

O autor encontrou 4,3 milhões de posições perdedoras específicas.
Eles provaram que o jogo é provavelmente governado por regras estritas (a "Extensão Única") em vez de caos.
Eles encontraram um ritmo oculto (112) que controla a estrutura do jogo.

O que o artigo NÃO diz:

Não afirma que isso ajuda a resolver outros jogos (como Xadrez ou Go).
Não afirma que isso tem aplicações médicas ou do mundo real.
Não prova que essas regras são 100% verdadeiras para tabuleiros infinitos; prova apenas que elas se mantêm verdadeiras para a faixa de 500 passos que testaram. O autor chama-as de "conjecturas" (suposições fortes baseadas em evidências) em vez de leis comprovadas.

Em resumo, o autor pegou um jogo bagunçado e complexo, executou uma simulação massiva em computador e descobriu que, sob o caos, há uma estrutura muito ordenada, rítmica e previsível aguardando para ser totalmente compreendida.

1. Formulação do Problema

O artigo investiga o jogo combinatório Chomp jogado em uma grade retangular $4 \times n$ .

Regras do Jogo: Os jogadores alternam removendo um quadrado e todos os quadrados acima e à direita dele. O quadrado superior esquerdo $(1,1)$ é "envenenado"; o jogador forçado a pegá-lo perde.
Objetivo: Identificar as posições-P (posições vencedoras para o jogador anterior, ou posições perdedoras para o jogador da vez).
Contexto: Enquanto os casos $1 \times n$ e $2 \times n$ estão totalmente resolvidos, e o caso $3 \times n$ possui soluções algorítmicas parciais, o caso $4 \times n$ carecia de análise computacional sistemática. O artigo visa preencher essa lacuna tabulando as posições-P e identificando padrões estruturais subjacentes.

2. Metodologia

O autor desenvolveu um solver retroativo otimizado em C++ para calcular posições-P para larguras de tabuleiro até $n = 500$ .

Representação de Estados:
- As posições são representadas como tuplas não decrescentes $(a, b, c, d)$ onde $a \ge b \ge c \ge d \ge 0$ , denotando o número de quadrados em cada linha.
- Empacotamento de Bits: Cada tupla é codificada em um único inteiro uint64 usando quatro campos de 16 bits para minimizar o uso de memória e maximizar a velocidade de hash.
Design do Algoritmo:
- Armazenamento Esparsos: Apenas as posições-P são armazenadas em um conjunto hash. O solver encerra a avaliação de posições-N (vencedoras para o jogador atual) assim que uma jogada para uma posição-P conhecida é encontrada.
- Avaliação de Baixo para Cima: Os estados são processados em ordem crescente de contagem total de células, garantindo que todos os sucessores sejam resolvidos antes de avaliar um estado.
Desempenho:
- Calculou 4.316.097 posições-P para $n \le 500$ .
- Tempo de execução: ~70 minutos em um processador Apple M4.
- Uso de memória: Pico de 45 MB.
Verificação:
- Validado contra a fórmula conhecida para $2 \times n$ (onde $c=d=0$ implica $b=a-1$ ).
- Verificado cruzadamente com um solver independente em Python para o subcaso $3 \times n$ ( $d=0$ ) até $n=50$ .
- Corrigido um bug inicial de alinhamento de colunas na saída de dados.

3. Contribuições e Resultados Principais

A análise do conjunto de dados calculado levou a quatro conjeturas estruturais primárias:

A. Conjetura 1: Propriedade de Extensão Única

Declaração: Para qualquer tripla válida de comprimentos de linha $(a, b, c)$ , existe no máximo um inteiro $d$ tal que $(a, b, c, d)$ seja uma posição-P.
Implicação: O mapa de projeção $\pi: (a, b, c, d) \to (a, b, c)$ é injetivo no conjunto de posições-P.
Significado: Isso sugere que o jogo $4 \times n$ é um "levantamento determinístico" do jogo $3 \times n$ . Embora nem toda $(a, b, c)$ se estenda a uma posição-P (apenas ~20% o fazem), se uma extensão existir, o comprimento da quarta linha $d$ é unicamente forçado. Isso contrasta com o caso $3 \times n$ , onde nenhum mapeamento injetivo simples desse tipo havia sido estabelecido anteriormente.

B. Conjetura 2: Razões Assintóticas

Declaração: À medida que a largura do tabuleiro $a \to \infty$ $a \to \infty$ , as razões dos comprimentos das linhas nas posições-P convergem para constantes fixas:
- $b/a \to L_1 \approx 0,762$
- $c/a \to L_2 \approx 0,499$
- $d/a \to L_3 \approx 0,224$
Metodologia: Estimadas via medianas em janelas, janelas rolantes e ajuste de curvas de lei de potência.
Observação: Nenhuma identidade algébrica exata foi encontrada para essas constantes. No entanto, $L_3 \approx 0,224$ é notavelmente próxima de $\cos(3\pi/7) \approx 0,2225$ , sugerindo uma possível relação algébrica oculta.

C. Conjetura 3: Estrutura Modular de Período-112

Declaração: O conjunto de triplas $(a, b, c)$ que se estendem a posições-P exibe uma estrutura modular com um período fundamental de 112.
Evidência:
- Análise de autocorrelação da sequência de valores de $d$ mostra um pico agudo no atraso 112.
- Um classificador logístico usando apenas $c$ e $(a-b) \pmod{112}$ prevê a extensibilidade com 79% de precisão.
- Testes de qui-quadrado confirmam que o módulo 112 fornece a separação estatística mais forte ( $\chi^2 = 12.433$ ) em comparação com outros módulos.
Interpretação: $112 = \text{mcm}(7, 8) \times 2$ . O fator 7 provavelmente decorre da periodicidade do sub-jogo $3 \times n$ , enquanto o fator 8 permanece sem explicação (excluindo artefatos de empacotamento de bits).

D. Conjetura 4: Geometria de Cone Linear

Declaração: O conjunto de triplas extensíveis $(a, b, c)$ forma um cone linear em $\mathbb{R}^3$ .
Geometria: Para um $c$ fixo, a faixa válida de $(a, b)$ forma uma banda contígua. A largura dessa banda cresce linearmente com $c$ :
$\text{largura}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$
onde $f$ é uma função periódica limitada. A inclinação $11/8 = 1,375$ foi derivada de medições baseadas em fatias.

4. Significado e Direções Futuras

Insight Estrutural: As descobertas sugerem que o Chomp $4 \times n$ possui uma estrutura mais rica e determinística do que o suspeitado anteriormente, potencialmente mais simples que o caso $3 \times n$ devido à propriedade de "Extensão Única".
Generalização: O autor hipotetiza que a propriedade de Extensão Única pode generalizar-se para o Chomp $k \times n$ para todo $k$ , implicando que todos os jogos de Chomp são recursivamente determinados pelo caso resolvido $2 \times n$ .
Questões Abertas:
1. Prova: A propriedade de Extensão Única pode ser provada combinatorialmente?
2. Limites Algébricos: As razões assintóticas são raízes de um polinômio comum?
3. Dimensões Superiores: Isso vale para $5 \times n$ ? (Requer espaço de estados $O(n^5)$ ).
4. Origem do Período: Qual é a fonte do componente de período-8 no ciclo de 112?
5. Forma Fechada: As ~20% de triplas extensíveis podem ser descritas por uma máscara de forma fechada?

O artigo também nota o envio da sequência de valores de $d$ à Enciclopédia On-Line de Sequências de Inteiros como A395126. O código e os dados estão publicamente disponíveis no repositório GitHub do autor.