Ten two-digit numbers and two equal sums

Question

You are given ten distinct two-digit numbers (each between 10 and 99). Prove that there are always two groups of these numbers, using none of the same numbers, each group non-empty, whose totals are equal. For example, from 12, 25, 37 and others you might find 12 + 25 = 37. But the claim is that this is unavoidable for any ten two-digit numbers.

Accepted Answer

It is always possible, by the pigeonhole principle applied to subset sums. Count the groups. From ten numbers you can form 2 to the power 10 = 1,024 different subsets (including the empty subset and the whole set). Count the possible totals. The largest possible total of a subset is the sum of the ten largest two-digit numbers, 90 + 91 + ... + 99 = 945. So every subset total is a whole number between 0 and 945: at most 946 possible values. Pigeonhole. 1,024 subsets share at most 946 totals, so some two different subsets, call them A and B, have the same total. Make them disjoint. A and B may …

Ten two-digit numbers and two equal sums

Your answer

Discussion

Learn the concepts

Related questions