Exercise 1105Combinatorics › Pigeonhole principleL1Added 3 Nov 2026
Subset sums
#pigeonhole#subset sums#olympiad
Statement
Show that among any integers from , some subset has sum divisible by .
Hint
Consider partial sums. Or use a stronger argument with residues.
Show solutionHide solution
Solution
Simpler version. Among any integers, two have difference divisible by (as shown previously). Let these be with . Then the subset ... but that's a difference, not a sum.
Corrected version. Among any integers, there exist some whose sum is divisible by : consider partial sums for , mod . If some , done. Otherwise two have the same residue, and is a subset sum divisible by .
Conclusion. A nonempty subset has sum divisible by .