0
$\begingroup$

I'm trying to solve some problem in the past few days(by the way, my first question here is some sort of a direction for solution - or maybe not).

Problem: Suppose that we have a list of $(n-1)^2-1$ non negative integers, where $n$ is odd number. Then there are $n$ integers from that list that their sum is dividable by $n$.

\begin solution{

First case: where all remainders of these numbers divided by $n$ are obtained. Then, we sum these numbers, the sum is dividable by $n$ since

$$0+1+2+...+n-1=\frac{n(n-1)}{2}$$

Second case: where not all remainders of these numbers divided by $n$ are obtained. Suppose that only $k<n$ remainders obtained. Then I thought use Pigeonhole principle to show that there exist a remainder(as a set) which contains at lesat $n$ integers from the list given. But I can't find a way showing that.

$\endgroup$
  • 1
    $\begingroup$ For $n=3$, take $1,2,5$. The sum of these numbers are not divisible by $3$. Am I mistaken? $\endgroup$ – mathlove May 20 '15 at 17:26
1
$\begingroup$

As mathlove's comment shows, you must assume $n > 3$.

Suppose it was not true.

If you had one member of each of the $n$ congruence classes mod $n$, you could take their sum and it would be divisible by $n$. So if this is not the case, at least one congruence class is missing, and at most $n-1$ congruence classes are represented. If there were $n$ numbers in one of those congruence classes, their sum would be divisible by $n$. So there are at most $n-1$ members in each of those $n-1$ congruence classes. Now with $n-1$ members in each of $n-1$ classes, that would make $(n-1)^2$ numbers, one more than you actually have. Therefore what you have is $n-2$ classes with $n-1$ members, one with $n-2$ members, one with $0$ members.

Consider the congruence classes $a, a+1, a+2 \mod n$, where the missing class is none of these (this is where you need to assume $n > 3$). Take $(n-1)/2$ members of class $a$, $(n-1)/2$ of class $a+2$ and $1$ of class $a+1$. The sum $\equiv a (n-1)/2 + a+1 + (a+2)(n-1)/2 = (a+1) n \equiv 0 \mod n$.

$\endgroup$
  • $\begingroup$ Thank you, but I've lost you in your second paragraph. $\endgroup$ – roger May 20 '15 at 17:52
  • $\begingroup$ You don't understand "Suppose it was not true"? $\endgroup$ – Robert Israel May 20 '15 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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