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.
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
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.
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)