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 \leq k < \frac{3^{t-1}-1}{2}$; moreover, (iii) $k \neq \frac{3^\ell - 1}{2}$ for all nonnegative integers $\ell < t$.
Obviously, these conditions can be equivalently rewritten as:
(i$'$) $n \equiv 2 \; \pmod 3$, (ii$'$) $3k + 2 < \frac{3^{t+1} + 1}{2}$, and (iii$'$) $3k + 2 \neq \frac{3^{\ell + 1} + 1}{2}$ for $0 \leq \ell < t$.
By computations, the above conjecture was verified for $n \leq 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} \;\; % \mid t \geq 2\}$},
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.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요