Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Ten different two-digit numbers are written on cards, for example 13, 27, 31, 44, 52, 68, 70, 85, 91, 99. Prove that, whatever the ten numbers are, you can always make two groups of cards with no card in both groups and with equal totals.
Count the groups (non-empty subsets) of the ten cards, and find the largest total that a group can have. Compare the two counts with the pigeonhole principle. Then explain how to remove the cards that two equal-total groups share.
Remainders on division by are boxes. The prefix sums give a block with a sum divisible by . Cut a figure into pieces: two points in one piece are close.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. There are more groups than possible totals, so two groups share a total. Then make them disjoint.
Step 1. Count the groups. Ten cards have subsets, so non-empty groups.
Step 2. The possible totals. A group's total is at least and at most . So there are at most possible totals.
Step 3. Pigeonholes. groups and at most totals: two different groups and have the same total.
Step 4. Make them disjoint. Remove from both the cards they share. Both totals drop by the same amount, so they stay equal. Neither group becomes empty: if lost all its cards, would lie inside , and then would have a larger total, because and all numbers are positive.
Answer: groups but at most as a total, so two disjoint groups with equal totals always exist. Proof complete.
Log in to join the discussion.
Loading…