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 "2011 AIME I Problems/Problem 12"

(→‎Solution)
(→‎Solution)
 
(11 intermediate revisions by 5 users not shown)
Line 17: Line 17:
 
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 <math>n</math> women.  Since there are <math>n+1</math> possible places to insert the dividers, and we need to choose any three of these locations, we have <math>\dbinom{n+1}{3}</math> ways.
 
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 <math>n</math> women.  Since there are <math>n+1</math> possible places to insert the dividers, and we need to choose any three of these locations, we have <math>\dbinom{n+1}{3}</math> ways.
  
−
The second, third, and fourth cases are like the first, only we need to insert two dividers among the <math>n+1</math> possible locations.  Each gives us <math>\dbinom{n+1}{2}</math> ways, for a total of <math>3\dbinom{n+1}{2}</math>.
+
The second, third, and fourth cases are like the first, only that we need to insert two dividers among the <math>n+1</math> possible locations.  Each gives us <math>\dbinom{n+1}{2}</math> ways, for a total of <math>3\dbinom{n+1}{2}</math> ways.
  
 
The last case gives us <math>\dbinom{n+1}{1}=n+1</math> ways.
 
The last case gives us <math>\dbinom{n+1}{1}=n+1</math> ways.
Line 33: Line 33:
 
<cmath>\dfrac{2\dbinom{n+1}{2}+(n+1)}{\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1)}\le\dfrac{1}{100}.</cmath>
 
<cmath>\dfrac{2\dbinom{n+1}{2}+(n+1)}{\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1)}\le\dfrac{1}{100}.</cmath>
  
−
The numerator is equal to
+
After simplification, we arrive at <cmath>\dfrac{6(n+1)}{n^2+8n+6}\le\dfrac{1}{100}.</cmath>
  
−
<cmath>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.</cmath>
+
Simplifying again, we see that we seek the smallest positive integer value of <math>n</math> such that <math>n(n-592)\ge594</math>. Clearly <math>n>592</math>, or the left side will not even be positive; we quickly see that <math>n=593</math> is too small but <math>n=\boxed{594}</math> satisfies the inequality.
−
 
 
−
For the denominator, we get
 
−
 
 
−
<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)\\
 
−
&=(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*}</cmath>
 
−
 
 
−
So, we get
 
−
 
 
−
<cmath>\dfrac{(n+1)^2}{\frac{1}{6}(n+1)(n^2+8n+6)}=\dfrac{6(n+1)}{n^2+8n+6}\le\dfrac{1}{100}.</cmath>
 
−
 
 
−
<math>100(n^2+8n+6)>0</math> since <math>n</math> must be positive.  So, when multiplying both sides of the inequality by that expression, it will not change the inequality sign.  After multiplying by it, we get
 
−
 
 
−
<cmath>\begin{align*}100\cdot6(n+1)&\le n^2+8n+6\\
 
−
600n+600&\le n^2+8n+6\\
 
−
0&\le n^2-592n-594.
 
−
\end{align*}</cmath>
 
−
 
 
−
Thus we seek the smallest positive integer value of <math>n</math> such that <math>n^2-592n-594\ge0</math>.  Since the quadratic function's discriminant, or <math>\sqrt{592^2-4(-594)}=\sqrt{592^2+4\cdot594}</math>, is positive, the polynomial has two distinct real roots.
 
−
 
 
−
Also, since the polynomial has a positive leading coefficient, the graph of the polynomial is concave up, and the value of <math>n</math> we want must be either slightly larger than the positive root (if the other, smaller root is negative) or equal to <math>1</math> (if the smaller root is positive).  We see that <math>n=1</math> does not satisfy the inequality, so there must be a positive and negative root.
 
−
 
 
−
The solution to the polynomial is
 
−
 
 
−
<cmath>\dfrac{592\pm\sqrt{592^2+4\cdot594}}{2}.</cmath>
 
−
 
 
−
We want the positive solution and find the smallest integer greater than that solution.  So, we will look only at the <math>+</math> case, not the <math>-</math>.
 
−
 
 
−
Let's look at the discriminant:
 
−
 
 
−
<cmath>\begin{align*}\sqrt{592^2+4\cdot594}&=\sqrt{593^2-1+4\cdot593-1}\\
 
−
&=\sqrt{593(593+4)-2}
 
−
\end{align*}</cmath>
 
−
 
 
−
So <math>593<\text{discriminant}<594</math>.
 
−
 
 
−
Let <math>k=\dfrac{592+\sqrt{592^2+4\cdot594}}{2}</math>.
 
−
 
 
−
Therefore, we're looking for
 
−
 
 
−
<cmath>n=\left\lceil\dfrac{592+\sqrt{592^2+4\cdot594}}{2}\right\rceil=\lceil n\rceil.</cmath>
 
−
 
 
−
Since we have <math>593<\sqrt{592^2+4\cdot594}<594</math>, we get
 
−
 
 
−
<cmath>\begin{align*}\dfrac{592+593}{2}<&k<\dfrac{592+594}{2}\\
 
−
592.5<&k<593
 
−
\end{align*}</cmath>
 
−
 
 
−
Since <math>n=\lceil k\rceil</math>, <math>n=\boxed{
 
−
 
 
−
Since </math>\dfrac{n+1}{n+2}<math> is slightly less than 1 when </math>n<math> is large, </math>\dfrac{6}{n+6}<math> will be close to </math>\dfrac{1}{100}<math>. They equal each other when </math>n = 594<math>.
 
−
 
 
−
If we let </math>n= 595<math> or </math>593<math>, we will notice that the answer is </math>\boxed{594}$
 
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2011|n=I|num-b=11|num-a=13}}
 
{{AIME box|year=2011|n=I|num-b=11|num-a=13}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 11:46, 17 February 2020

Problem

Six men and some number of women stand in a line in random order. Let $p$ 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 $p$ does not exceed 1 percent.

Solution

Let $n$ 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 $(k)$ refers to a consecutive group of $k$ 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 $n$ women. Since there are $n+1$ possible places to insert the dividers, and we need to choose any three of these locations, we have $\dbinom{n+1}{3}$ ways.

The second, third, and fourth cases are like the first, only that we need to insert two dividers among the $n+1$ possible locations. Each gives us $\dbinom{n+1}{2}$ ways, for a total of $3\dbinom{n+1}{2}$ ways.

The last case gives us $\dbinom{n+1}{1}=n+1$ 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).\]

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).\]

Thus, we want to find the minimum possible value of $n$ where $n$ 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}.\]

After simplification, we arrive at \[\dfrac{6(n+1)}{n^2+8n+6}\le\dfrac{1}{100}.\]

Simplifying again, we see that we seek the smallest positive integer value of $n$ such that $n(n-592)\ge594$. Clearly $n>592$, or the left side will not even be positive; we quickly see that $n=593$ is too small but $n=\boxed{594}$ satisfies the inequality.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_I_Problems/Problem_12&oldid=117857"