Difference between revisions of "2011 AIME I Problems/Problem 12"
(→Solution) |
(→Solution) |
||
| Line 41: | Line 41: | ||
<cmath>\begin{align*}\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1)&=\dfrac{(n+1)!}{3!(n-2)!}+3\dfrac{(n+1)!}{2!(n-1)!}+(n+1)\\ | <cmath>\begin{align*}\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1)&=\dfrac{(n+1)!}{3!(n-2)!}+3\dfrac{(n+1)!}{2!(n-1)!}+(n+1)\\ | ||
&=\dfrac{(n+1)(n)(n-1)}{6}+3\dfrac{(n+1)(n)}{2}+(n+1)\\ | &=\dfrac{(n+1)(n)(n-1)}{6}+3\dfrac{(n+1)(n)}{2}+(n+1)\\ | ||
| − | &=(n+1)\left[\dfrac{n^2-n}{6}+\dfrac{3n}{2}+(n+1) | + | &=(n+1)\left[\dfrac{n^2-n}{6}+\dfrac{3n}{2}+1\right]\\ |
| − | &=\dfrac{1}{6}(n+1) | + | &=\dfrac{1}{6}(n+1)(n^2-n+9n+6)\\ |
| + | &=\dfrac{1}{6}(n+1)(n^2+8n+6) | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
Revision as of 11:18, 2 March 2016
Problem
Six men and some number of women stand in a line in random order. Let 
be the probability that a group of at least four men stand together in the line, given that every man stands next to at least one other man. Find the least number of women in the line such that does not exceed 1 percent.
Solution
Let 
be the number of women present, and let _ be some positive number of women between groups of men. Since the problem states that every man stands next to another man, there cannot be isolated men. Thus, there are five cases to consider, where 
refers to a consecutive group of 
men:
_(2)_(2)_(2)_
_(3)_(3)_
_(2)_(4)_
_(4)_(2)_
_(6)_
For the first case, we can place the three groups of men in between women. We can think of the groups of men as dividers splitting up the women. Since there are 
possible places to insert the dividers, and we need to choose any three of these locations, we have 
ways.
The second, third, and fourth cases are like the first, only we need to insert two dividers among the possible locations. Each gives us 
ways, for a total of 
.
The last case gives us 
ways.
Therefore, the total number of possible ways where there are no isolated men is
![\[\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1).\]](http://latex.artofproblemsolving.com/f/6/3/f6383b2dabb90e94611319f0f73a54db18dc6c4b.png)
The total number of ways where there is a group of at least four men together is the sum of the third, fourth, and fifth case, or
![\[2\dbinom{n+1}{2}+(n+1).\]](http://latex.artofproblemsolving.com/a/e/4/ae4886fdbc0b72678b3c988958e9a1c3706ba4f3.png)
Thus, we want to find the minimum possible value of where is a positive integer such that
![\[\dfrac{2\dbinom{n+1}{2}+(n+1)}{\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1)}\le\dfrac{1}{100}.\]](http://latex.artofproblemsolving.com/9/8/a/98af23f5ba1bb01345d036d77bcfc0955452f1fd.png)
The numerator is equal to
![\[2\cdot\dfrac{(n+1)!}{2!(n-1)!}+(n+1)=2\cdot\dfrac{(n+1)(n)}{2}+(n+1)=n(n+1)+1(n+1)=(n+1)^2.\]](http://latex.artofproblemsolving.com/2/a/c/2acf5268975f80ed789b5209d37dfb3384571a7f.png)
For the denominator, we get
![\begin{align*}\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1)&=\dfrac{(n+1)!}{3!(n-2)!}+3\dfrac{(n+1)!}{2!(n-1)!}+(n+1)\\ &=\dfrac{(n+1)(n)(n-1)}{6}+3\dfrac{(n+1)(n)}{2}+(n+1)\\ &=(n+1)\left[\dfrac{n^2-n}{6}+\dfrac{3n}{2}+1\right]\\ &=\dfrac{1}{6}(n+1)(n^2-n+9n+6)\\ &=\dfrac{1}{6}(n+1)(n^2+8n+6) \end{align*}](http://latex.artofproblemsolving.com/b/2/1/b211b4ddceeea26a16cd91b58a4ca9e4585bee55.png)
so the whole faction simplifies to 
Since 
is slightly less than 1 when is large, 
will be close to 
. They equal each other when 
.
If we let 
or 
, we will notice that the answer is 
See also
| 2011 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 11 |
Followed by Problem 13 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
