28 Jan
Where Is the Pigeonhole?
Here is a problem from an old Russian collection of problems offered at an evening math school. At the time - now, about 50 years ago - I have not seen anything strange about it. Now I do. Does it come with age?
Here's the problem:
A Math Circle has 31 participant. Their ages are all different and sum up to 434 years. Prove that it is possible to find 20 participants whose total age is at least 280.
No related posts.
After having visited the original problem at cut-the-knot and reading your comments in the solution. The problem would be more reasonable if the condition "their ages are all different" was removed. Is there a reason it's there? The condition doesn't seem integral to the problem or the solution.
Is the reasonableness factor what you're referring to, or is there something else that's bothering you about the problem? Does it have to do with the pigeonhole principle? I'm not sure I'd consider this a pigeonhole problem. But perhaps its a more divergent application of the principle? Looking forward to your insights.
January 28th, 2011 at 5:52 pmJohn, you are right of course. The requirement that the ages should be different is unnecessary and is rather misleading - on two counts. But where is the pigeonhole?
I have this book from my school days with checkmarks and some remarks to remind me of the solutions I came up with at the time. This one comes with a marginal note "Pigeonhole". However, the solution I posted at my site did not refer to the pigeonhole at all. So I decided to post the problem at the blog in the hope somebody will turn up to refresh my memory.
Now I got it. This is in the spirit of Dijkstra's view: the maximum is at least the average. So, in a sense, when averages pop up the pigeonhole is near by next. And there is definitely an average to consider: 434/31 = 14 an 14×20 = 280. Still where is the pigeonhole?
There are C(31, 20) ways to choose 20 numbers out of 31 (this is assuming they are all different. Modification is needed if they are not.) Let S be the maximum sum of any 20 numbers. Each of the elements is included in C(30, 19) sums. Therefore,
434×C(30, 19) ≤ S×C(31, 20).
But C(31, 20) / C(30, 19) = 31/20. Assuming S < 280, we get
434 = S×31/20 < 280×31/20 = 434. A contradiction.
To sum up: if there are 434×C(30, 19) pigeons nesting in C(31, 20) holes then at least one hole contains at least 280 pigeons.
If the composers of the problem had this solution in mind, then it is clear why they imposed the "unnecessary" condition.
January 28th, 2011 at 8:05 pmOn second thought, it does not matter even for this solution whether the numbers are different or not. For the purpose of counting we may color them all in individual colors.
January 28th, 2011 at 8:52 pm