Waste less time on Facebook — follow Brilliant.

Divisible by 10

There is a set S={a1, a2, ...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.

Note by Daniel Liu
4 years, 8 months ago

No vote yet
6 votes


Sort by:

Top Newest

This 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.

Jacob Gurev - 4 years, 8 months ago

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)

Zi Song Yeoh - 4 years, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...