# Sum of $n$ numbers dividable by $n$ from $(n-1)^2-1$ numbers.

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.

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

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

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