# Partitioning $\{1,2,\ldots,k\}$ into $p$ subsets with equal sums, where $p$ is prime

Let $$p$$ be a prime natural number. For which positive integer $$k$$ can the set $$\{1,2,\ldots,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

Definition. 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 $$\text{k\equiv 0\pmod{4} or k\equiv -1\pmod{4}}\,.$$ For an odd prime $$p$$, we have $$\text{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 $$\text{\{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 $$\text{\{6r+1,12r+2\}, \{6r+2,12r+1\}, \ldots, \{9r+1,9r+2\}}\,,$$ $$\text{\{1,2,3,6r-2,6r-1,6r\}, \{4,5,6,6r-5,6r-4,6r-3\}}\,,$$ $$\text{\ldots, \{3r-2,3r-1,3r,3r+1,3r+2,3r+3\}}\,.$$
• If $$k=3p=12r+3$$, then consider the partition $$\text{\{6r+3,12r+3\}, \{6r+4,12r+2\}, \ldots, \{9r+2,9r+4\}}\,,$$ $$\text{\{1,2,3,6r-1,6r,6r+1\}, \{4,5,6,6r-4,6r-3,6r-2\}}\,,$$ $$\text{\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 $$\text{\{6r-2,12r-4\}, \{6r-1,12r-5\}, \ldots, \{9r-4,9r-2\}}\,,$$ $$\text{\{1,2,3,6r-5,6r-4,6r-3\}, \{4,5,6,6r-8,6r-7,6r-6\}}\,,$$ $$\text{\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 $$\text{\{6r,12r-3\}, \{6r+1,12r-4\}, \ldots, \{9r-2,9r-1\}}\,,$$ $$\text{\{1,2,3,6r-4,6r-3,6r-2\}, \{4,5,6,6r-7,6r-6,6r-5\}}\,,$$ $$\text{\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 \dfrac{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.