# Partitioning $\{1,\cdots,k\}$ into $p$ subsets with equal sums

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.

• 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. – Alan Dec 4 '15 at 12:28
• $p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions. – Empy2 Dec 4 '15 at 12:30
• @Alan, I think $\frac{k(k+1)}2$ must be even. – Empy2 Dec 4 '15 at 12:31
• @michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True. – Alan Dec 4 '15 at 12:33
• @Alan or $k$ could be congruent to $3$ modulo $4$. – Arthur Dec 4 '15 at 12:46

## 1 Answer

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.