16
$\begingroup$

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.

$\endgroup$
8
  • $\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, 2015 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, 2015 at 12:30
  • $\begingroup$ @Alan, I think $\frac{k(k+1)}2$ must be even. $\endgroup$
    – Empy2
    Dec 4, 2015 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, 2015 at 12:33
  • $\begingroup$ @Alan or $k$ could be congruent to $3$ modulo $4$. $\endgroup$
    – Arthur
    Dec 4, 2015 at 12:46

1 Answer 1

11
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .