sum of one hundred numbers

Question

I saw this problem recently. It asks to prove that it is always possible to choose 100 numbers from 200 positive numbers such that their sum will be divisible by 100.

Attempt to solve: my first step was to take mod of each number. It helps because then we have to work only with numbers from 1 to 99 (200 in total). Then I have to prove that there is always a sum such that $a_1+a_2+a_3+...a_{100}$ where $a_i \le 99$ is divisible by 100. And here I stuck. A hint would be appreciated.

Answer 1

This result is a special case of the famous EGZ or Erdős Ginzburg Ziv theorem, which states that any set of $2n-1$ integers, must have some subset of size $n$ whose sum is a multiple of $n$. Hence we can even throw out one of the 200 numbers; out of any 199 integers, some 100 must sum to a multiple of 100.

You can find some lovely proofs of EGZ on mathoverflow.

Answer 2

The EGZ theorem can be proved through the Cauchy-Davenport theorem:

If $A$ and $B$ are subsets of $\mathbb{Z}_{/100\mathbb{Z}}$, $$ |A+B| \geq \min(100,|A|+|B|-1) $$

or the Kneser's theorem:

If $A,B$ are subsets of $\mathbb{Z}_{/100\mathbb{Z}}$ and $C$ is the restricted sumset $\{a+b:(a,b)\in A\times B, a\neq b\}$, then: $$ |C| \geq \min(100,|A|+|B|-3). $$

Both theorems can be proved through the Dirichlet box principle with quite sophisticated proofs, or through the combinatorial nullstellensatz as shown by Noga Alon in the eighties.

In any case, among $199$ integers there are for sure $100$ integers having sum $\equiv 0\pmod{100}$.

Answer 3

So I found a solution in an old russian magazine for high-school students (it is called "Kvant"). The statement is as follows:

It is always possible to choose from a set of $2n-1$ numbers $n$ numbers such their sum is divisible by n. In other words $\frac{a_1 + a_2 + ... + a_n}{n}$ is integer.

Apparently, to prove this statement in general is not very easy as one can see from the answers. But one can prove a lemma which is the key to solve the original problem.

Consider two sets of numbers with $2a-1$ and $2b-1$ numbers in each. Let these two sets satisfy the previous statement. Then a set with $2ab-1$ numbers will also satisfy the statement.

The proof of this lemma is easy:

Let's denote the sets with $2a-1$, $2b-1$, $2ab-1$ numbers as $S_a$, $S_b$, $S_{ab}$. As $2ab-1>2b-1$ we can choose $b$ numbers from $S_{ab}$ such that their sum is divisible by $b$. We can remove $b$ numbers from $S_{ab}$ $2a-1$ times because $2ab-1=b(2a-1)+(b-1)$. So now we have $2a-1$ sets of numbers with $b$ numbers in each. But we also know that $S_a$ satisfies the statement (and sum of numbers in the each set is divisible by $b$ ). Now replace the each of $2a-1$ sets by the corresponding sum. So we end up with a set which contains $2a-1$ numbers. Obviously, it is possible to choose $a$ numbers from this set such that their sum is divisible by $ab$.

Now to solve the problem we have to prove the statement for some small prime numbers simply by brute-force and then use the lemma.