Question

Show that among all collections with 2n-1 natural numbers in them there are
exactly n numbers whose sum is divisible by n.

Answer 1

Let the numbers be denoted by aiai. As we are dealing with divisibility by nn, we may assume that 0?ai<n0?ai<n for all ii. Furthermore, let the aiai be in ascending order.

Now, if ai=ai+n?1ai=ai+n?1 for some ii, then we are done: simply pick the nn numbers aiaithrough ai+n?1ai+n?1. Therefore, we may assume that ai?ai+n?1ai?ai+n?1 for all ii.

Consider the following subsets of ?nZn: Ai={ai,ai+n?1}Ai={ai,ai+n?1} for 1?i<n1?i<n and An=a2n?1An=a2n?1. Define the sum of two sets XX and YY as follows:

X+Y={z:z=x+y,x?X?y?Y}X+Y={z:z=x+y,x?X?y?Y}

With this definition, define the following sets SiSi:

Si=?k=1iAkSi=?k=1iAk

It is easy to see that mi=m(Si)mi=m(Si) (mm denotes the number of elements) is a nondecreasing sequence. We strengthen this result as follows:

Lemma. For i<ni<n, mi?i+1mi?i+1.

Proof. Assume the contrary. Then, there must be some i<n?1i<n?1 such that mi=mi+1mi=mi+1 (this follows from the fact that mimi is nondecreasing and m1=2m1=2). In other words, denoting Si+1={x,y}Si+1={x,y}, the two sets Si+xSi+x and Si+ySi+y must be identical (as x?yx?y). This means that the set SiSi is invariant under the addition of

z=x?yz=x?y. Recalling how we defined addition, this means that if aa is some element of SiSi, then every number of the form a+kza+kz where k??k?Z must also be an element of SiSi. However, these numbers are distinct for 0?k<n0?k<n, as nn is prime. Therefore, SiSi must have nn elements, from which a contradiction follows easily.

Now, we simply note that mn?mn?1?nmn?mn?1?n and therefore mn=nmn=n, which means that the set SnSn contains all possible remainders modulo n, in particular, it contains 0. This means that we can choose nn elements from A1,A2,...,AnA1,A2,...,Anrespectively whose sum will be 0 modulo n.

To obtain the result for the case when n=abn=ab is composite, simply partition the set into 2b?12b?1 mutually exclusive subsets and apply the result twice.