4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $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. $\endgroup$ Dec 18, 2013 at 22:18

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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