Given any set of ten distinct numbers in the range 10, 11, ... , 99, prove that we can always find two disjoint subsets with the same sum.
Solution
The number of non-empty subsets is 210 - 1 = 1023. The sum of each subset is at most 90 + ... + 99 = 945, so there must be two distinct subsets A and B with the same sum. A \ B and B \ A are disjoint subsets, also with the same sum.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 1998
Last updated/corrected 14 Mar 03