2005 IMO Shortlist Problems/C2

Problem

(Iran) Let $\displaystyle k$ 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 $\displaystyle k$ persons buy sombreros (directly or indirectly), then that someone wins a free instructional video. Prove that if $\displaystyle n$ persons bought sombreros, then at most $\displaystyle n/(k+2)$ of them got videos.

This was also Problem 3, Day 2, of the 2006 Australia TST.

Solution

Suppose $\displaystyle m$ persons receive videos. We wish to prove $n \ge m(k+2)$ . We will prove the stronger bound

$n \ge (m+1)(k+1) + m$

by induction on $\displaystyle m$ .

We say a person $\displaystyle A$ is a direct successor of $\displaystyle B$ if $\displaystyle B$ directly convinced $\displaystyle A$ to buy a sombrero. We say $\displaystyle A$ is an indirect successor of $\displaystyle B$ if $\displaystyle B$ caused $\displaystyle A$ 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 $\displaystyle k$ indirect successors. Hence $\displaystyle n \ge 2k+3 = (m+1)(k+1)+m$ .

Now, suppose there are $\displaystyle m$ 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 $\displaystyle 2+k$ people, and we have removed one blossom. If there are $\displaystyle n'$ people remaining, then the inductive hypothesis now tells us

$n - (2+k) \ge n' \ge (m)(k+1) + (m-1)$ ,

or $\displaystyle n \ge n' + k+2 \ge (m+1)(k+1) + m$ . Therefore for all $\displaystyle m$ , we have

$n \ge (m+1)(k+1) + m = m(k+2) + k+1 > m(k+2)$ ,

as desired.

We note that the bound $n \ge (m+1)(k+1) +m$ is sharp, for it is possible to have blossoms $A_1, \ldots, A_m$ , with $\displaystyle A_{i+1}$ a direct successor of $\displaystyle A_i$ , and all buds having exactly $\displaystyle k$ indirect successors.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Page

Toolbox

Search

2005 IMO Shortlist Problems/C2

Problem

Solution

Resources