March 17–March 30, 2009
Problem
(This was an unofficial problem during spring break.)
Warmup:
- Prove that any set of 3 integers contains a pair whose sum is even.
- Prove that any set of 5 integers contains a triplet whose sum is divisible by 3.
The problem: Let m be any positive integer. Is it always true that any set of 2m - 1 integers contains a subset of size m whose sum is divisible by m?
Solution
The warmup problems can be solved by brute force, considering every possiblility of 3 numbers mod 2 (for warmup 1) and 5 numbers mod 3 (for warmup 2). The general problem is harder to prove. The paper Zero-sum sets of prescribed size (2008), by Noga Alon and Moshe Dubiner gives five different proofs. This theorem was first proved by Erdös, Ginzburg and Ziv in 1961.
List of solvers
Steve Wilmarth completed the warmup problems. Lloyd Sakazaki found a complete solution and provided the reference above—kudos!.
There was no prize for this puzzle.