Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
$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

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.