2

If $p$ is a prime, which integers $n$ is it possible to split the set consisting of $\{1,2,...,n\}$ into $p$ disjoint (meaning they have no element in common) subsets where the sum of the integers in each subset has the exact same value?

Yiyuan Lee
  • 14,435
  • At minimum, we must have $p|\frac{n(n+1)}{2}$. – vadim123 Mar 22 '14 at 04:20
  • Nevermind, I understand why this is true. Any other ideas? –  Mar 22 '14 at 04:21
  • For $p=2$, I believe that my necessary condition is also sufficient. – vadim123 Mar 22 '14 at 05:05
  • I completely agree. 2 isnt divisible by 3. But how about for other values of p? Do we make them the prime factorization of n(n+1)/2? –  Mar 22 '14 at 05:14
  • I don't understand either of your comments, but yes, the condition $p \mid \frac{n(n+1)}{2}$ is necessary and sufficient for $p=2$, but for $p>2$ we also require (at least) $n\geq 2p-1$, as $n=p-1,p$ are clear counterexamples. – Andrew Dudzik Mar 22 '14 at 05:38

1 Answers1

1

I'll leave $p=2$ as an exercise: all $n\equiv3,0\pmod4$ work. From now on assume $p$ is odd. Partial answer/conjecture below:

The sum of all the integers from $1$ to $n$ is $n(n+1)/2$. So we need $p$ to divide $n(n+1)/2$, which means $$ n\equiv-1\pmod p \qquad\text{or}\qquad n\equiv0\pmod p.\tag{$*$} $$But we also need $n(n+1)/2p \ge n$, or else the single element $n$ is already larger than the required common sum. This simplifies to $$n+1\ge 2p;\tag{$**$}$$ in other words, $n=p-1$ and $n=p$ are impossible.

Observation: if $n$ works for $p$, then so does $n+2p$, because the additional integers can be inserted into the existing sets in pairs $\{n+1,n+2p\},\{n+2,n+2p-1\},\dots,\{n+p,n+p+1\}$ while preserving the equal sums property. Therefore, if we want to show that the two conditions ($*$) and ($**$) are sufficient, it suffices to show that $n=2p-1,2p,3p-1,3p$ work for $p$.

  • $n=2p-1$: the sets are $\{1,2p-2\},\{2,2p-3\},\dots,\{p-1,p\},\{2p-1\}$.
  • $n=2p$: the sets are $\{1,2p\},\{2,2p-1\},\dots,\{p,p+1\}$.
  • $n=3p-1$: I don't know the answer
  • $n=3p$, if $p\equiv3\pmod 4$: some of the sets are $\{\frac{3p+3}2,3p\},\{\frac{3p+5}2,3p-1\},\dots,\{\frac{9p+1}4,\frac{9p+5}4\}$. The other sets are of the form $\{j,\frac{p-1}2-j,\frac{p+1}2+j,p-j,p+1+j,\frac{3p+1}2-j\}$ for $0\le j\le\frac{p-3}4$ (leave $0$ out of the $j=0$ set).
  • $n=3p$, if $p\equiv1\pmod 4$: I don't know the answer
Greg Martin
  • 78,820