🔢 mathematics

Partitioning set $[n] = \{1, \dots, n\}$ into subsets of size at most $m$ such that all sums are powers of $m$

Este artigo investiga a existência e a unicidade de partições do conjunto $\{1, \dots, n\}$ em subconjuntos de tamanho no máximo $m$ com somas que são potências de $m$ , provando que, embora tais partições falhem para infinitos $n$ quando $m > 3$ , elas provavelmente existem para todo $n$ quando $m = 3$ (sujeito a restrições específicas sobre potenciais contraexemplos) e estabelecendo contagens exatas para o número de tais partições para vários valores de $n$ .

Autores originais: Vladimir Gurvich, Mariya Naumova

Publicado 2026-07-17

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Vladimir Gurvich, Mariya Naumova

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 que você é um arquiteto mestre encarregado de construir uma cidade usando exatamente $n$ tijolos únicos, numerados de 1 a $n$ . Seu objetivo não é apenas empilhá-los; você deve agrupá-los em bairros (chamados de "partes") onde duas regras estritas se aplicam. Primeiro, nenhum bairro pode estar muito lotado; ele pode conter no máximo $m$ tijolos. Segundo, o "peso" total dos tijolos em qualquer bairro deve ser uma potência perfeita de um número mágico específico $m$ (como $m^0=1$ , $m^1=m$ , $m^2$ , e assim por diante). Este enigma pertence ao mundo da combinatória, um ramo da matemática que estuda como as coisas podem ser arranjadas, contadas ou agrupadas. É como resolver um Sudoku gigante e infinito onde as regras mudam conforme o tamanho da grade. Os matemáticos se importam com isso porque entender como os números podem ser decompostos e remontados revela segredos profundos sobre a estrutura da matemática, muito parecido com entender como os átomos se ligam ajuda a construir novos materiais.

O artigo que você está prestes a ler aborda uma versão específica e complicada deste enigma, onde os autores, Vladimir Gurvich e Mariya Naumova, definiram o número mágico $m$ como 3. Isso significa que eles estão tentando dividir os números de 1 a $n$ em grupos de tamanho 1, 2 ou 3, onde a soma de cada grupo é uma potência de 3 (1, 3, 9, 27, etc.). Eles já sabiam que para $m=2$ , sempre existe exatamente uma maneira de fazer isso para qualquer $n$ . Eles também sabiam que para $m$ maior que 3, o enigma é impossível para infinitos valores de $n$ . Mas para $m=3$ , a resposta era um mistério. Os autores suspeitam fortemente (conjecturam) que uma solução existe para todo $n$ , não importa o quão grande seja.

Para testar isso, eles não apenas adivinharam; eles construíram uma rede de segurança matemática. Eles provaram que, se uma solução não existir para algum número $n$ , esse número "ruim" deve ter uma forma muito específica e estranha. Ele deve ser do tipo $n = 3t + 3k + 2$ e deve evitar outros padrões específicos. Pense nisso como um detetive dizendo: "Se um crime aconteceu, o suspeito deve estar usando um chapéu vermelho, mancar e ser canhoto". Se você encontrar um suspeito que não se encaixa nessa descrição, sabe que ele não é o culpado. Os autores usaram essa lógica para eliminar enormes blocos de números. Eles também executaram simulações de computador para verificar cada número até 844 e, em todos os casos, uma solução foi encontrada. Eles até exploraram uma versão um pouco mais flexível do enigma chamada "quasi-partição", onde um número é permitido ser usado duas vezes, e provaram que soluções existem lá também. Embora não tenham provado que o enigma é solucionável para todo $n$ ainda, eles restringiram a busca por um contraexemplo a uma lista de números muito pequena e específica, e estão confiantes de que, para quase todos os outros números, a solução não só é possível, mas frequentemente única.

O Grande Jogo de Agrupamento de Números

Imagine que você tem uma bolsa de peças numeradas, de 1 até um grande número $n$ . Seu trabalho é separar essas peças em pilhas. Mas existem regras!

A Regra do Tamanho: Cada pilha pode ter no máximo 3 peças.
A Regra da Soma: Os números em cada pilha devem somar uma "potência de 3". Isso significa que a soma deve ser 1, 3, 9, 27, 81 e assim por diante.

Este é o problema da "partição 3-boa". Os autores fazem uma pergunta simples, mas persistente: Podemos sempre fazer isso, não importa quantos números comecemos com?

Por muito tempo, os matemáticos souberam a resposta para partições "2-boas" (onde as pilhas têm no máximo 2 peças e as somas são potências de 2). Acontece que sempre há exatamente uma maneira de fazer isso. Mas para 3, as regras ficam complicadas. Os autores suspeitam que a resposta seja "Sim, é sempre possível", mas precisavam provar isso.

Os Suspeitos "Críticos"

Em vez de tentar provar que funciona para todo número (o que é difícil), os autores decidiram procurar pelos "vilões" — os números onde o processo falha. Eles raciocinaram que, se existe um número $n$ onde você não consegue fazer as pilhas, ele deve ser um número "crítico".

Eles provaram que, se tal número crítico existir, ele não pode ser qualquer número aleatório. Ele deve usar um disfarce muito específico. Deve ser da forma:
$n = 3t + 3k + 2$
E deve satisfazer algumas condições extras sobre o quão grande $k$ é em relação a $t$ .

Pense nisso como um segurança em um clube. O segurança diz: "Se você está tentando entrar sem ingresso, deve estar usando um chapéu verde e carregando uma bolsa azul". Se você vir alguém de chapéu vermelho, sabe que essa pessoa não é o intruso sorrateiro. Os autores provaram que qualquer número que não se encaixe nessa descrição de "chapão verde" está seguro; nós sabemos como agrupar esses números. Isso elimina uma quantidade massiva de possibilidades.

A Verificação do Computador

Mesmo com sua matemática astuta, ainda restavam alguns números que se encaixavam na descrição do "chapéu verde". Para ter certeza, os autores (com a ajuda do programador Dmitry Rybin) escreveram um programa para verificar cada número até 844.

O Resultado: Para cada número de 1 a 844, eles encontraram uma maneira de agrupar as peças perfeitamente.
A Conclusão: O computador não encontinou um único número "ruim". Isso apoia fortemente a ideia de que o enigma é solucionável para todos.

A Reviravolta das "Quasi-Partições"

Os autores também tentaram um jogo ligeiramente diferente. E se permitíssemos que um número fosse usado duas vezes? Eles chamam isso de "quasi-partição". Imagine que você tem uma peça extra do número 3, então pode usá-la em duas pilhas diferentes.
Eles provaram que, para um intervalo específico de números, você sempre pode resolver esta versão do enigma, e o número 3 (especificamente $3^t$ ) é o que será usado duas vezes. Isso foi um degrau útil para entender o problema mais difícil.

Quantas Maneiras Existem?

Uma das partes mais interessantes do artigo é contar quantas maneiras diferentes existem de agrupar os números.

Para alguns números (como 1, 2, 3, 4 e muitos outros), existe exatamente uma maneira de fazer isso. É como uma fechadura com apenas uma chave.
Para o número 13, e para números como $3t - 3$ , existem exatamente duas maneiras.
Para quase todos os outros números, eles suspeitam que existam mais de duas maneiras.

Eles até encontraram uma regra especial (Proposição 2) que diz que, se você souber quais grupos de três números (trincas) estão na solução, você pode deduzir o enigma inteiro. É como dizer: "Se você conhece os três melhores amigos em uma sala, você conhece toda a dinâmica social".

A Conclusão Final

Os autores ainda não resolveram o enigma para cada número do universo. Ainda existem alguns números complicados (como 35, 38, 89 e 101) que ainda não foram totalmente limpos por sua matemática. No entanto, eles mostraram que, se uma solução não existir, ela deve ser um desses números muito específicos e raros.

Eles estão confiantes de que a "partição 3-boa" existe para todo número $n$ . Eles eliminaram as falhas fáceis, verificaram os primeiros 844 números com um computador e descobriram que o enigma sempre tem uma solução. O mistério não é se podemos agrupar os números, mas sim quantas maneiras podemos fazer isso para os números realmente grandes. A jornada para provar isso para cada número continua, mas o caminho agora está muito mais claro.

Resumo Técnico: Sobre a Partição do Conjunto [n] em Subconjuntos de Tamanho no Máximo m Tal Que Todas as Somas Sejam Potências de m

Enunciado do Problema
O artigo aborda um problema de partição combinatória definido sobre o conjunto dos primeiros $n$ números naturais, $[n] = \{1, \dots, n\}$ . Dados inteiros $m > 1$ e $n > 0$ , um subconjunto de $[n]$ é definido como $m$ -bom se sua cardinalidade é no máximo $m$ e a soma de seus elementos é uma potência de $m$ (ou seja, $m^t$ para algum inteiro $t \ge 0$ ). Uma partição de $[n]$ é $m$ -boa se cada parte na partição for um conjunto $m$ -bom.

Os autores investigam a existência e a unicidade de tais partições. Estabelece-se que:

Para $m=2$ , uma partição 2-boa única existe para todo $n$ .
Para $m > 3$ , existem infinitos $n$ para os quais não existe uma partição $m$ -boa (especificamente, para $n = 2(m^t + 1)$ ).
O caso $m=3$ é o foco principal, onde a existência de uma partição 3-boa para todo $n$ não é imediatamente óbvia e permanece sendo objeto de conjectura.

Metodologia
Os autores empregam uma combinação de provas construtivas, reduções recursivas e verificação computacional.

Técnicas de Redução: A metodologia central envolve "reduções", onde uma partição de $[n]$ é construída adicionando partes específicas a uma partição conhecida de um conjunto menor $[n']$ . Os autores definem fórmulas de redução específicas para várias formas de $n$ (por exemplo, $n = 3t + 3k$ , $n = 3t + 3k + 1$ ) que permitem a construção de uma partição 3-boa para $n$ baseada em uma partição para um $n'$ menor.
Intervalos Simétricos: O artigo utiliza partições de intervalos inteiros simétricos $[-\ell; \ell]$ para facilitar as reduções. O Lema 1 demonstra que tais intervalos admitem partições 3-boas (usando tripletos que somam 0) quando $\ell \equiv 0, 1 \pmod 3$ .
Quase-partições: Para lidar com casos em que as partições padrão são difíceis de construir, os autores introduzem 3-boas quase-partições. Estas são famílias de subconjuntos que cobrem todos os números em $[n]$ exatamente uma vez, exceto por um número específico (especificamente $3^t$ ) que é coberto duas vezes.
Algoritmos Recursivos: Para provas de unicidade, os autores utilizam um algoritmo recursivo (atribuído a Oleg Polubasoff) que determina o posicionamento do maior número livre $i$ . Se $i$ for uma potência de 3, deve ser um singleton; caso contrário, deve ser pareado com $3^j - i$ (onde $3^{j-1} < i < 3^j$ ).

Contribuições Principais e Resultados

Conjectura de Existência (Conjectura 1): Os autores conjecturam que uma partição 3-boa de $[n]$ existe para todo inteiro positivo $n$ .
Caracterização de Contraexemplos Mínimos (Teorema 1): Assumindo que um contraexemplo exista, os autores provam que o contraexemplo mínimo $n$ $n$ deve satisfazer condições estritas:
- $n = 3^t + 3k + 2$ para $t > 0$ .
- $0 \le k < \frac{3^{t-1}-1}{2}$ .
- $k \neq \frac{3^\ell-1}{2}$ para qualquer inteiro não negativo $\ell < t$ .
- Equivalentemente, $n \equiv 2 \pmod 3$ , $3k+2 < \frac{3^{t+1}+1}{2}$ e $3k+2 \neq \frac{3^{\ell+1}+1}{2}$ .
- Isso reduz significativamente o espaço de busca para potenciais contraexemplos.
Existência de Quase-partições (Teorema 2): Os autores provam que, para qualquer $n$ que satisfaça as condições do Teorema 1 (ou seja, a forma potencial de um contraexemplo), existe uma quase-partição 3-boa onde o número $3^t$ é coberto duas vezes. Isso sugere que a obstrução a uma partição padrão é mínima.
Resultados de Unicidade (Teorema 3): O artigo estabelece a unicidade das partições 3-boas para intervalos específicos de $n$ $n$ :
- Partições únicas existem para $n \in \{1, 2, 3, 4\}$ e para $n$ da forma $3^t - 4, 3^t - 2, 3^t - 1, 3^t, 3^t + 1, 3^t + 2, 3^t + 3, 3^t + 5$ (para $t \ge 2$ ).
- Exatamente duas partições 3-boas existem para $n = 3^t - 3$ e para $n = 13$ .
- Os autores conjecturam que para todos os outros $n$ (excluindo 13), o número de partições 3-boas é maior que 2.
Verificação Computacional: Usando código escrito por Dmitry Rybin, as conjecturas relativas à existência e à contagem de partições foram verificadas para todos os $n \le 844$ .

Significância e Alegações
O artigo afirma fornecer os primeiros resultados parciais rigorosos relativos à existência de partições 3-boas para todo $n$ . Ao caracterizar a forma de qualquer potencial contraexemplo mínimo, os autores restringem significativamente o espaço do problema. A introdução de quase-partições serve como um passo intermediário crítico, demonstrando que mesmo nos casos mais difíceis (onde uma partição padrão pode falhar), uma estrutura muito próxima de uma solução existe.

Os autores reconhecem que, embora os métodos de redução generalizados (sugeridos por Oleg Polubasoff) estendam o alcance dos casos prováveis, permanece uma questão em aberto se esses métodos são suficientes para provar totalmente a Conjectura 1 para todo $n$ . O artigo não pretende ter resolvido o problema geral de existência, mas sim fornece um arcabouço estrutural e evidências fortes que apoiam a conjectura.