14
$\begingroup$

Let $p$ be a prime. For which $k$ can the set $\{1,\cdots,k\}$ be partitioned into $p$ subsets with equal sums of elements ?

Obviously, $p\mid k(k+1)$. Hence, $p\mid k$ or $p\mid k+1$. All we have to do now is to show a construction. But I can't find one. I have tried partitioning the set and choose one element from each set but that hasn't yielded anything.

Any hint will be appreciated.

$\endgroup$
  • $\begingroup$ Well, I'd eliminate the trivial case when $p=2$ first....then you're just looking at dividing it into 2 sets with equal sums, which should be possible iff $k$ is even. $\endgroup$ – Alan Dec 4 '15 at 12:28
  • 1
    $\begingroup$ $p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions. $\endgroup$ – Empy2 Dec 4 '15 at 12:30
  • $\begingroup$ @Alan, I think $\frac{k(k+1)}2$ must be even. $\endgroup$ – Empy2 Dec 4 '15 at 12:31
  • 1
    $\begingroup$ @michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True. $\endgroup$ – Alan Dec 4 '15 at 12:33
  • $\begingroup$ @Alan or $k$ could be congruent to $3$ modulo $4$. $\endgroup$ – Arthur Dec 4 '15 at 12:46
9
$\begingroup$

For a prime natural number $p$, we say that a positive integer $k$ is $p$-splittable if $\{1,2,\ldots,k\}$ can be partitioned into $p$ subsets with the same sum. If $p=2$, then it follows that $k\equiv 0\pmod{4}$ or $k\equiv -1\pmod{4}$. For an odd prime $p$, we have $k\equiv 0\pmod{p}$ or $k\equiv-1\pmod{p}$. It can be easily seen that, for $k\in\mathbb{N}$ and for any prime natural number $p$, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable (by adding $\{k+1,k+2p\}$, $\{k+2,k+2p-1\}$, $\ldots$, $\{k+p,k+p+1\}$ to the $p$ partitioning sets of $\{1,2,\ldots,k\}$).

Since $k=3$ and $k=4$ are $2$-splittable, any natural number of the form $4t-1$ or $4t$, where $t\in\mathbb{N}$, is $2$-splittable, and no other number is $2$-splittable. Also, for any odd prime natural number $p$, $k=2p-1$ and $k=2p$ are $p$-splittable, which means that any natural number of the form $2pt-1$ or $2pt$, where $t\in\mathbb{N}$, is $p$-splittable. Clearly, $k=p-1$ and $k=p$ are not $p$-splittable for odd $p$. We, however, claim that $k=3p-1$ or $k=3p$ are $p$-splittable for odd $p$, which would then imply that any natural number of the form $pt-1$ or $pt$ where $t\geq 2$ is an integer is $p$-splittable, and nothing else is $p$-splittable.

First, assume that $p\equiv 1\pmod{4}$, say $p=4r+1$ for some $r\in\mathbb{N}$. If $k=3p-1=12r+2$, then consider the partition of $\{1,2,\ldots,k\}$ into $\{6r+1,12r+2\}$, $\{6r+2,12r+1\}$, $\ldots$, $\{9r+1,9r+2\}$, $\{1,2,3,6r-2,6r-1,6r\}$, $\{4,5,6,6r-5,6r-4,6r-3\}$, $\ldots$, $\{3r-2,3r-1,3r,3r+1,3r+2,3r+3\}$. If $k=3p=12r+3$, then consider the partition $\{6r+3,12r+3\}$, $\{6r+4,12r+2\}$, $\ldots$, $\{9r+2,9r+4\}$, $\{1,2,3,6r-1,6r,6r+1\}$, $\{4,5,6,6r-4,6r-3,6r-2\}$, $\ldots$, $\{3r-2,3r-1,3r,3r+2,3r+3,3r+4\}$, $\{3r+1,6r+2,9r+3\}$.

Now, assume that $p\equiv -1\pmod{4}$, say $p=4r-1$ for some $r\in\mathbb{N}$. If $k=3p-1=12r-4$, then consider the partition $\{6r-2,12r-4\}$, $\{6r-1,12r-5\}$, $\ldots$, $\{9r-4,9r-2\}$, $\{1,2,3,6r-5,6r-4,6r-3\}$, $\{4,5,6,6r-8,6r-7,6r-6\}$, $\ldots$, $\{3r-5,3r-4,3r-3,3r+1,3r+2,3r+3\}$, $\{3r-2,3r-1,3r,9r-3\}$. If $k=3p=12r-3$, then consider the partition $\{6r,12r-3\}$, $\{6r+1,12r-4\}$, $\ldots$, $\{9r-2,9r-1\}$, $\{1,2,3,6r-4,6r-3,6r-2\}$, $\{4,5,6,6r-7,6r-6,6r-5\}$, $\ldots$, $\{3r-5,3r-4,3r-3,3r+2,3r+3,3r+4\}$, $\{3r-2,3r-1,3r,3r+1,6r-1\}$.

Question: What if $p$ is not prime? I conjecture the following:

(1) If $p$ is odd, then, for any $j\in\{-1,0,1,2,\ldots,p-2\}$ such that $p\mid j(j+1)$, every integer of the form $tp+j$, where $t\geq 2$ is an integer, is $p$-splittable, and nothing else is $p$-splittable.

(2) If $p$ is even, then, for any $j\in\{-1,0,1,2,\ldots,2p-2\}$ such that $p\mid \frac{j(j+1)}{2}$, every integer of the form $2tp+j$, where $t\in\mathbb{N}$, is $p$-splittable, and nothing else is $p$-splittable.

This question is also posted here: $p$-Splittable Integers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.