Question

Let A = {a1, a2, a3, . . . , an} be a nonempty set of n distinct natural numbers. Prove that there exists a nonempty subset of A for which the sum of its elements is divisible by n.

Answer 1

Since the set A has n distinct numbers (integers), so they form a congruence class modulo n.

i.e if we consider the set, A(mod n) defined as,

A(mod n) := { a₁(mod n), a₂(mod n), a₃(mod n), ..., a_n(mod n) }

Since, A has n distinct elements so, A(mod n) is nothing but Z_n, which is the set of all congruence classes modulo n.

i.e. A(mod n) = Z_n = {0,1,2,3,...,n-1}

Now, let, S is a subset of A(mod n) such that, S = {1, 2, n-2, n-1}

Then, the sum of the 4 elements of S is, n+n = 2n = 0 (mod n)

Hence, if we get back to the set, B which is a 4-element subset of A such that, S = B(mod n)

Then, Suppose, B = { a_r, a_s, a_i, a_j } such that, r, s, i & j range between 1 to n and B(mod n) = S. Since, the sum of the elements of B(mod n) is 0 mod n, so, the sum of the elements of.B are divisible by n.

So, B is the desired subset of A whose sum of elements is divisible by n.

This is how we constructed B from A.