Maths WorkshopMaths problems with full solutions
Exercise 1105Combinatorics › Pigeonhole principleL1Added 3 Nov 2026

Subset sums

#pigeonhole#subset sums#olympiad

Statement

Show that among any n+1n+1 integers from {1,…,2n}\{1,\ldots,2n\}, some subset has sum divisible by n+1n+1.

Hint

Consider partial sums. Or use a stronger argument with residues.

Show solutionHide solution

Solution

Simpler version. Among any n+1n+1 integers, two have difference divisible by nn (as shown previously). Let these be a,ba,b with b−a=knb-a=kn. Then the subset {a,b}\{a,b\}... but that's a difference, not a sum.

Corrected version. Among any n+1n+1 integers, there exist some whose sum is divisible by n+1n+1: consider partial sums Sk=a1+⋯+akS_k=a_1+\cdots+a_k for k=1,…,n+1k=1,\ldots,n+1, mod n+1n+1. If some Sk≡0S_k\equiv 0, done. Otherwise two Si,SjS_i,S_j have the same residue, and Sj−SiS_j-S_i is a subset sum divisible by n+1n+1.

Conclusion. A nonempty subset has sum divisible by n+1n+1.