There is a set S={a*1, a*2, ...a_n}, where each element of the set is a random integer. Prove that there exists at least one subset of S such that the sum of the elements of the subset is divisible by n.

Not sure where I heard this from, but I can't seem to solve it. Any help will be appreciated. Please show all your work.

No vote yet

6 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestThis is a pretty common nice problem. We consider the partial sums a1,a1+a2,...a1+a2+...+an. If one of these is 0mod n, then we are done. Otherwise, as there are only n-1 other possible residues, there must be two partial sums that are the same mod n by pigeonhole. Let these be the ith and jth partial sums, with i<j. Now, because these sums are the same mod n, their difference is divisible by n. But the ith partial sum is completely contained in the jth partial sum. So we can take the terms in the jth partial sum not in the ith, and the subset {a(i+1),a(i+2),...,a(j)} has sum divisible by n.

Log in to reply

A slight difficult problem :

Let F be a field with n integer elements such that the sum of any number of integers(except no integers) is divisible by n + 1. Find all fields F that satisfies the condition.

(I already solved this)

Log in to reply