# A partition problem

This question is motivated by an old math contest problem, and is a generalization of the original problem. I will write out the original problem as motivation.

Let us say that $n$ is $p$-Savage, for a prime $p$, if it is possible to partition $\{1, \cdots, n\}$ into $p$ sets $A_1, \cdots, A_{p}$ such that the following holds:

i) $\displaystyle \sum_{x \in A_i} x = D$, a constant, for $1 \leq i \leq p$;

ii) $x \in A_i$ implies that $x \equiv i-1 \pmod{p-1}$ for $1 \leq i \leq p-1$; and

iii) $x \equiv 0 \pmod{p}, 1 \leq x \leq n$ imply that $x \in A_p$.

Do there exist $p$-Savage numbers for every prime $p$? If so, can one estimate how many $p$-savage number there are say in $[1, N]$?

This is motivated by an old Canadian math contest problem (Euclid 2003), where the question asks about 3-Savage numbers following the above definition (originally just called savage numbers). It asked in particular to show that 8 is (3-)savage, and that every even savage number $n$ satisfies $n \equiv 8 \pmod{12}$. These questions are fairly simply to answer by doing some simple (but tedious) modular arithmetic. The contest did not ask for any sufficient conditions for $n$ to be savage, nor did it ask for whether the exist infinitely many savage numbers. It also only focused on even savage numbers. One can show by modular arithmetic that if $n$ is an odd savage number, then $n \equiv 11 \pmod{12}$. 35 is an odd savage number.

-
$A_3$ needs to contain all multiples of 3 but may contain other numbers, while $A_1$ can only contain even numbers and $A_2$ can only contain odd numbers. If you consider the (legal) partition $A_3 = \{1, 2, 3, 6\}$, $A_2 = \{5,7\}$ and $A_1 = \{4,8\}$ you see that their sums are equal. – Stanley Yao Xiao Dec 18 '13 at 22:18
Ok, that makes sense. Thanks. – Douglas Zare Dec 18 '13 at 22:19

The answer is that for large enough $n$, it is a $p$-savage if and only if $p|n+1$ and $(p-1)|\frac{n(n+1)}{2}$.
You must have $p-1|D$ because all elements of $A_1$ are divisible by $p-1$. And so we must have $p-1|\frac{n(n+1)}{2}=pD$. To show that $p|n+1$ we have to rule out the case $p|n$. This is easily ruled out because $$p+2p+\cdots+p\cdot\frac{n}{p}=\frac{n(n+p)}{2p}>D.$$
Now if you assume that the divisibility conditions above are satisfied and $n$ is large enough, I claim that you can always find an admissible partition. Start by letting $A_p=\lbrace p,2p,\dots n-p+1\rbrace$, and distribute the rest among the $A_i$'s. Then let $f_i=\sum_{x\in A_i}x-D$. It's not hard to check that $f_i\approx \frac{n}{p(p-1)}$, but then if $f_i$ is large enough it can be written as a sum of distinct elements from $A_i$. We collect all such elements from the $A_i$'s and put them in $A_p$.