Baltic Way 1991 · Problem 3
Combinatorics
There are 20 cats priced from $12 to $15 and 20 sacks priced from 10 cents to $1 for sale (all prices are different). Prove that each of two boys, John and Peter, can buy a cat in a sack paying the same amount of money.
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Pigeonhole and extremal arguments
Solutions
Solution
Solution:
The number of different possibilities for buying a cat and a sack is while the number of different possible prices is . Thus by the pigeonhole principle there exist two combinations of a cat and a sack costing the same amount of money. Note that the two cats (and also the two sacks) involved must be different as otherwise the two sacks (respectively, cats) would have equal prices.