Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 IMO Shortlist Problems/C2"

 
(→‎Solution: see my remark on http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=104152)
 
Line 8: Line 8:
 
== Solution ==
 
== Solution ==
  
−
Suppose <math> \displaystyle m </math> persons receive videos.  We wish to prove <math> n \ge m(k+2) </math>. We will prove the stronger bound
+
Suppose <math>m </math> persons receive videos.  We wish to prove <math> n \ge m(k+2) </math>. Since this is clear for <math>m=0</math>, let us WLOG assume that <math>m</math> is positive. Under this assumption, we will now prove the stronger bound
−
<center> <math> n \ge (m+1)(k+1) + m </math> </center> by induction on <math> \displaystyle m </math>.
+
<center> <math> n \ge (m+1)(k+1) + m </math> </center> by induction on <math>m </math>.
  
−
We say a person <math> \displaystyle A </math> is a '' direct successor'' of <math> \displaystyle B </math> if <math> \displaystyle B </math> directly convinced <math> \displaystyle A </math> to buy a sombrero.  We say <math> \displaystyle A </math> is an ''indirect successor'' of <math> \displaystyle B  </math> if <math> \displaystyle B </math> caused <math> \displaystyle A </math> 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''.
+
We say a person <math>A </math> is a '' direct successor'' of <math>B </math> if <math>B </math> directly convinced <math>A </math> to buy a sombrero.  We say <math>A </math> is an ''indirect successor'' of <math>B  </math> if <math>B </math> caused <math>A </math> 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 <math> \displaystyle k </math> indirect successors.  Hence <math> \displaystyle n \ge 2k+3 = (m+1)(k+1)+m </math>.
+
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 <math>k </math> indirect successors.  Hence <math>n \ge 2k+3 = (m+1)(k+1)+m </math>.
  
−
Now, suppose there are <math> \displaystyle m </math> 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 <math> \displaystyle 2+k </math> people, and we have removed one blossom.  If there are <math> \displaystyle n' </math> people remaining, then the inductive hypothesis now tells us
+
Now, suppose there are <math>m </math> 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 <math>2+k </math> people, and we have removed one blossom.  If there are <math>n' </math> people remaining, then the inductive hypothesis now tells us
 
<center> <math> n - (2+k) \ge n' \ge (m)(k+1) + (m-1) </math>, </center>
 
<center> <math> n - (2+k) \ge n' \ge (m)(k+1) + (m-1) </math>, </center>
−
or <math> \displaystyle n \ge n' + k+2 \ge (m+1)(k+1) + m </math>.  Therefore for all <math> \displaystyle m </math>, we have
+
or <math>n \ge n' + k+2 \ge (m+1)(k+1) + m </math>.  Therefore for all <math>m </math>, we have
 
<center>
 
<center>
 
<math> n \ge (m+1)(k+1) + m = m(k+2) + k+1 > m(k+2) </math>, </center>
 
<math> n \ge (m+1)(k+1) + m = m(k+2) + k+1 > m(k+2) </math>, </center>
 
as desired.
 
as desired.
  
−
We note that the bound <math> n \ge (m+1)(k+1) +m </math> is sharp, for it is possible to have blossoms <math> A_1, \ldots, A_m </math>, with <math> \displaystyle A_{i+1} </math> a direct successor of <math> \displaystyle A_i </math>, and all buds having exactly <math> \displaystyle k </math> indirect successors.
+
We note that the bound <math> n \ge (m+1)(k+1) +m </math> is sharp, for it is possible to have blossoms <math> A_1, \ldots, A_m </math>, with <math>A_{i+1} </math> a direct successor of <math>A_i </math>, and all buds having exactly <math>k </math> indirect successors.
  
 
{{alternate solutions}}
 
{{alternate solutions}}
−
 
  
 
== Resources ==
 
== Resources ==

Latest revision as of 08:12, 29 August 2011

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 $m$ persons receive videos. We wish to prove $n \ge m(k+2)$. Since this is clear for $m=0$, let us WLOG assume that $m$ is positive. Under this assumption, we will now prove the stronger bound

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

by induction on $m$.

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

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

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

or $n \ge n' + k+2 \ge (m+1)(k+1) + m$. Therefore for all $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 $A_{i+1}$ a direct successor of $A_i$, and all buds having exactly $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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_IMO_Shortlist_Problems/C2&oldid=42032"