# Understanding Ziv's proof of zero sum problem .

I was going through the proof of zero sum problem in one dimension as provided by Abraham Ziv. The problem statement is to prove that given a set of $2n+1$ integers, we can find at least $n$ integers whose sum is divisible by $n$. The author first proved for the cases where $n$ is prime.

He chooses $\ s$ integers which are coprime to $p$, such that for no two $\ i , \ j \ \in \ N$ , $(\ a_i -\ a_j \ ) \equiv \ mod \ p$.

He starts up by proving in a set $\ A$, where any $x \in A$ is of the form $\sum_{i=1}^s \ c_i \ a_i$, where $\ c_i$ is either 1 or 0. The number of congruence classes modulo $\ p$ in $A$ are at least $\ s + 1$ congruent classes .

The proof is by induction. Now when he is trying to prove for $\ s +1$, he assumes there are minimum $k$ congruent classes, $b_1 , b_2 , ... b_k$. By a particular congruence class modulo $\ p$ , I understand to be the set of numbers which leave the a same particular remainder when divided by $\ p$. What exactly are the integers $b_1, b_2, ... b_k$ here? Are they the remainders that are obtained after dividing by $\ p$?

Given the lack of clarity about these numbers, I am also confused by what he means when he says that "at least one of the integers $\ b_i + \ a_s$ is not congruent to all the $b$ 's." How can he ascertain this?

I hope someone can explain this to me.

• Is there any particular reason you read the original paper? There are write ups that are easier to follows. – quid May 7 '16 at 20:59
• What do you mean by $(\ a_i -\ a_j \ ) \equiv \ mod \ p$? Did you want to write $a_i-a_j \equiv 0 \pmod p$ $a_i-a_j \equiv 0 \pmod p$? – Martin Sleziak May 8 '16 at 3:54

What exactly are the integers $b_1, b_2, ... b_k$ here?

You can think of them as one representative of the class.

Are they the remainders that are obtained after dividing by $\ p$?

If you want you can take it to be the remainder.

Given the lack of clarity about these numbers, I am also confused by what he means when he says that "at least one of the integers $\ b_i + \ a_s$ is not congruent to all the $b$ 's." How can he ascertain this?

Suppose that $b_i + a_s$ equals some $b_j$ for all $i$.

This would yield that you have $b_1 + j a_s$ for $j=0,\dots, s$ in the set of residue classes formed by the $b_i$. Yet these are all distinct modulo $p$ so this is impossible, as there are $s+1$.

If you know the Cauchy—Davenport theorem you can use that instead.