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

Abstract

Given integers $m>1$ and $n>0$, we say that a partition of the set $[n]=\{1,\dots ,n\}$ is {\em $m$-good} if the number of elements in each part is at most $m$ and their sum is a power of $m$. It is easily seen that for every $n$ there is a unique 2-good partition of $[n]$ and for each $m>3$ there is no $m$-good partition for infinitely many $n$. Less is known for $m=3$. We conjecture that a 3-good partition of $[n]$ exists for each $n$ and prove that a minimal counter-example, if any, must be of the form: (i) $n=3^t+3k+2$, where $t>0$ and (ii) $0\le k<\frac{3^{t-1}-1}{2}$; moreover, (iii) $k\ne \frac{3^{\ell }-1}{2}$ for all nonnegative integers $\ell <t$. Obviously, these conditions can be equivalently rewritten as: (i${}^{\prime }$) $n\equiv 2(\mathrm{mod}3)$, (ii${}^{\prime }$) $3k+2<\frac{3^{t+1}+1}{2}$, and (iii${}^{\prime }$) $3k+2\ne \frac{3^{\ell +1}+1}{2}$ for $0\le \ell <t$. By computations, the above conjecture was verified for $n\le 844$. We also modify the statement slightly and prove it for the 3-good quasi-partitions, which cover all numbers of $[n]=\{1,\dots ,3^t+3k+2\}$ once, except $3^t$, which is covered twice. Finally, we prove that a 3-good partition of $[n]$ is unique if {\centering $n\in \{1,2,3,4,3^t-4,3^t-2,3^t-1,3^t,3^t+1,3^t+2,3^t+3,3^t+5\text{for}$}, and there are exactly two 3-good partitions of $[n]$ for $n=3^t-3$. We conjecture that the number of 3-good partitions is greater than 2 for any other $n$, except 13.