2005 IMO Shortlist Problems/C2
Problem
(Iran) Let be a fixed positive integer. A company has a special method to sell sombreros. Each customer can convince two persons to buy a sombrero after he/she buys one; convincing someone already convinced does not count. Each of these new customers can convince two others and so on. If each one of the two customers convinced by someone makes at least persons buy sombreros (directly or indirectly), then that someone wins a free instructional video. Prove that if persons bought sombreros, then at most of them got videos.
This was also Problem 3, Day 2, of the 2006 Australia TST.
Solution
Suppose persons receive videos. We wish to prove . Since this is clear for , let us WLOG assume that is positive. Under this assumption, we will now prove the stronger bound
by induction on .
We say a person is a direct successor of if directly convinced to buy a sombrero. We say is an indirect successor of if caused to buy a sombrero, directly or indirectly. We will call a person who receives a video a blossom. We will call direct successor of a blossom who is not a blossom him- or her-self a bud.
For the base case of our induction, when there is only one blossom, that blossom must have at least two buds, each of which must have at least indirect successors. Hence .
Now, suppose there are blossoms. Since there are only finitely many blossoms, there exists at least one blossom which has no blossoms as indirect successors. We remove this blossom, one of its buds, and all indirect successors of that bud; we then make the disconnected bud a direct successor of whatever person was a direct successor of the blossom we removed, if there was such a person. All other blossoms stay blossoms; all other buds stay buds. We have thus removed at least people, and we have removed one blossom. If there are people remaining, then the inductive hypothesis now tells us
or . Therefore for all , we have
as desired.
We note that the bound is sharp, for it is possible to have blossoms , with a direct successor of , and all buds having exactly indirect successors.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.