🔢 mathematics

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

This paper investigates the existence and uniqueness of partitions of the set $\{1, \dots, n\}$ into subsets of size at most $m$ with sums that are powers of $m$ , proving that while such partitions fail for infinitely many $n$ when $m > 3$ , they likely exist for all $n$ when $m = 3$ (subject to specific constraints on potential counter-examples) and establishing exact counts for the number of such partitions for various values of $n$ .

Original authors: Vladimir Gurvich, Mariya Naumova

Published 2026-07-17

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Vladimir Gurvich, Mariya Naumova

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master architect tasked with building a city using exactly $n$ unique bricks, numbered 1 through $n$ . Your goal isn't just to stack them; you must group them into neighborhoods (called "parts") where two strict rules apply. First, no neighborhood can be too crowded; it can hold at most $m$ bricks. Second, the total "weight" of the bricks in any neighborhood must be a perfect power of a specific magic number $m$ (like $m^0=1$ , $m^1=m$ , $m^2$ , and so on). This puzzle belongs to the world of combinatorics, a branch of mathematics that studies how things can be arranged, counted, and grouped. It's like solving a giant, infinite Sudoku where the rules change based on the size of the grid. Mathematicians care about this because understanding how numbers can be broken down and reassembled reveals deep secrets about the structure of mathematics itself, much like understanding how atoms bond helps us build new materials.

The paper you are about to read tackles a specific, tricky version of this puzzle. The authors, Vladimir Gurvich and Mariya Naumova, set the magic number $m$ to 3. This means they are trying to split the numbers $1$ through $n$ into groups of size 1, 2, or 3, where the sum of each group is a power of 3 (1, 3, 9, 27, etc.). They already knew that for $m=2$ , there is always exactly one way to do this for any $n$ . They also knew that for $m$ larger than 3, the puzzle is impossible for infinitely many values of $n$ . But for $m=3$ , the answer was a mystery. The authors strongly suspect (conjecture) that a solution exists for every number $n$ , no matter how large.

To test this, they didn't just guess; they built a mathematical safety net. They proved that if a solution doesn't exist for some number $n$ , that "bad" number must have a very specific, weird shape. It must look like $n = 3t + 3k + 2$ , and it must avoid certain other specific patterns. Think of it like a detective saying, "If a crime happened, the suspect must be wearing a red hat, have a limp, and be left-handed." If you find a suspect who doesn't fit that description, you know they aren't the culprit. The authors used this logic to rule out huge chunks of numbers. They also ran computer simulations to check every number up to 844, and in every single case, a solution was found. They even explored a slightly looser version of the puzzle called a "quasi-partition," where one number is allowed to be used twice, and proved that solutions exist there too. While they haven't proven the puzzle is solvable for every $n$ yet, they have narrowed down the search for a counter-example to a very tiny, specific list of numbers, and they are confident that for almost all other numbers, the solution is not only possible but often unique.

The Great Number Grouping Game

Imagine you have a bag of numbered tiles, from 1 up to some big number $n$ . Your job is to sort these tiles into piles. But there are rules!

The Size Rule: Each pile can have at most 3 tiles.
The Sum Rule: The numbers in each pile must add up to a "power of 3." That means the sum must be 1, 3, 9, 27, 81, and so on.

This is the "3-good partition" problem. The authors ask a simple but stubborn question: Can we always do this, no matter how many tiles we start with?

For a long time, mathematicians knew the answer for "2-good" partitions (where piles have at most 2 tiles and sums are powers of 2). It turns out there is always exactly one way to do it. But for 3, the rules get messy. The authors suspect the answer is "Yes, it's always possible," but they needed to prove it.

The "Critical" Suspects

Instead of trying to prove it works for every number (which is hard), the authors decided to look for the "bad guys"—the numbers where it fails. They reasoned that if there is a number $n$ where you cannot make the piles, it must be a "critical" number.

They proved that if such a critical number exists, it can't just be any random number. It has to wear a very specific disguise. It must be of the form:
$n = 3t + 3k + 2$
And it has to satisfy some extra conditions about how big $k$ is compared to $t$ .

Think of this like a security guard at a club. The guard says, "If you are trying to sneak in without a ticket, you must be wearing a green hat and carrying a blue bag." If you see someone in a red hat, you know for sure they aren't the sneaky intruder. The authors proved that any number that doesn't fit this "green hat" description is safe; we know how to group those numbers. This eliminates a massive amount of possibilities.

The Computer Check

Even with their clever math, there were still some numbers that fit the "green hat" description. To be sure, the authors (with help from a computer programmer named Dmitry Rybin) wrote a program to check every single number up to 844.

The Result: For every single number from 1 to 844, they found a way to group the tiles perfectly.
The Conclusion: The computer didn't find a single "bad" number. This strongly supports their guess that the puzzle is solvable for everyone.

The "Quasi-Partitions" Twist

The authors also tried a slightly different game. What if we allowed one number to be used twice? They call this a "quasi-partition." Imagine you have a spare tile of the number 3, so you can use it in two different piles.
They proved that for a specific range of numbers, you can always solve this version of the puzzle, and the number 3 (specifically $3^t$ ) is the one that gets used twice. This was a helpful stepping stone to understanding the harder problem.

How Many Ways Are There?

One of the most fun parts of the paper is counting how many different ways you can group the numbers.

For some numbers (like 1, 2, 3, 4, and many others), there is exactly one way to do it. It's like a lock with only one key.
For the number 13, and for numbers like $3t - 3$ , there are exactly two ways.
For almost all other numbers, they suspect there are more than two ways.

They even found a special rule (Proposition 2) that says if you know which groups of three numbers (triplets) are in the solution, you can figure out the whole puzzle. It's like saying, "If you know who the three best friends are in a room, you know the whole social dynamic."

The Bottom Line

The authors haven't solved the puzzle for every number in the universe yet. There are still a few tricky numbers (like 35, 38, 89, and 101) that haven't been fully cleared by their math. However, they have shown that if a solution doesn't exist, it must be one of these very specific, rare numbers.

They are confident that the "3-good partition" exists for every number $n$ . They have ruled out the easy failures, checked the first 844 numbers with a computer, and found that the puzzle always has a solution. The mystery isn't if we can group the numbers, but rather how many ways we can do it for the really big numbers. The journey to prove it for every single number continues, but the path is now much clearer.

Technical Summary: On Partitioning the Set [n] into Subsets of Size at Most m Such That All Sums Are Powers of m

Problem Statement
The paper addresses a combinatorial partitioning problem defined on the set of the first $n$ natural numbers, $[n] = \{1, \dots, n\}$ . Given integers $m > 1$ and $n > 0$ , a subset of $[n]$ is defined as $m$ -good if its cardinality is at most $m$ and the sum of its elements is a power of $m$ (i.e., $m^t$ for some integer $t \ge 0$ ). A partition of $[n]$ is $m$ -good if every part in the partition is an $m$ -good set.

The authors investigate the existence and uniqueness of such partitions. It is established that:

For $m=2$ , a unique 2-good partition exists for every $n$ .
For $m > 3$ , there are infinitely many $n$ for which no $m$ -good partition exists (specifically, for $n = 2(m^t + 1)$ ).
The case $m=3$ is the primary focus, where the existence of a 3-good partition for every $n$ is not immediately obvious and remains a subject of conjecture.

Methodology
The authors employ a combination of constructive proofs, recursive reductions, and computational verification.

Reduction Techniques: The core methodology involves "reductions," where a partition of $[n]$ is constructed by adding specific parts to a known partition of a smaller set $[n']$ . The authors define specific reduction formulas for various forms of $n$ (e.g., $n = 3t + 3k$ , $n = 3t + 3k + 1$ ) that allow the construction of a 3-good partition for $n$ based on a partition for a smaller $n'$ .
Symmetric Intervals: The paper utilizes partitions of symmetric integer intervals $[-\ell; \ell]$ to facilitate reductions. Lemma 1 demonstrates that such intervals admit 3-good partitions (using triplets summing to 0) when $\ell \equiv 0, 1 \pmod 3$ .
Quasi-Partitions: To handle cases where standard partitions are difficult to construct, the authors introduce 3-good quasi-partitions. These are families of subsets that cover all numbers in $[n]$ exactly once, except for one specific number (specifically $3^t$ ) which is covered twice.
Recursive Algorithms: For uniqueness proofs, the authors utilize a recursive algorithm (attributed to Oleg Polubasoff) that determines the placement of the largest free number $i$ . If $i$ is a power of 3, it must be a singleton; otherwise, it must be paired with $3^j - i$ (where $3^{j-1} < i < 3^j$ ).

Key Contributions and Results

Existence Conjecture (Conjecture 1): The authors conjecture that a 3-good partition of $[n]$ exists for every positive integer $n$ .
Characterization of Minimal Counter-Examples (Theorem 1): Assuming a counter-example exists, the authors prove that the minimal counter-example $n$ $n$ must satisfy strict conditions:
- $n = 3^t + 3k + 2$ for $t > 0$ .
- $0 \le k < \frac{3^{t-1}-1}{2}$ .
- $k \neq \frac{3^\ell-1}{2}$ for any non-negative integer $\ell < t$ .
- Equivalently, $n \equiv 2 \pmod 3$ , $3k+2 < \frac{3^{t+1}+1}{2}$ , and $3k+2 \neq \frac{3^{\ell+1}+1}{2}$ .
- This narrows the search space for potential counter-examples significantly.
Existence of Quasi-Partitions (Theorem 2): The authors prove that for any $n$ satisfying the conditions of Theorem 1 (i.e., the potential form of a counter-example), a 3-good quasi-partition exists where the number $3^t$ is covered twice. This suggests that the obstruction to a standard partition is minimal.
Uniqueness Results (Theorem 3): The paper establishes the uniqueness of 3-good partitions for specific ranges of $n$ $n$ :
- Unique partitions exist for $n \in \{1, 2, 3, 4\}$ and for $n$ of the form $3^t - 4, 3^t - 2, 3^t - 1, 3^t, 3^t + 1, 3^t + 2, 3^t + 3, 3^t + 5$ (for $t \ge 2$ ).
- Exactly two 3-good partitions exist for $n = 3^t - 3$ and for $n = 13$ .
- The authors conjecture that for all other $n$ (excluding 13), the number of 3-good partitions is greater than 2.
Computational Verification: Using code written by Dmitry Rybin, the conjectures regarding existence and the count of partitions were verified for all $n \le 844$ .

Significance and Claims
The paper claims to provide the first rigorous partial results regarding the existence of 3-good partitions for all $n$ . By characterizing the form of any potential minimal counter-example, the authors significantly constrain the problem space. The introduction of quasi-partitions serves as a critical intermediate step, demonstrating that even in the most difficult cases (where a standard partition might fail), a structure very close to a solution exists.

The authors acknowledge that while the generalized reduction methods (suggested by Oleg Polubasoff) extend the range of provable cases, it remains an open question whether these methods are sufficient to fully prove Conjecture 1 for all $n$ . The paper does not claim to have solved the general existence problem but rather provides a structural framework and strong evidence supporting the conjecture.