Difference between revisions of "2011 AIME I Problems/Problem 12"

(Solution)
(Solution)
 
(31 intermediate revisions by 12 users not shown)
Line 1: Line 1:
== Problem ==
+
== Problem ==
Six men and some number of women stand in a line in random order. Let <math>p</math> be the probability that a group of at least four men stand together in the line, given that everyman stands next to at least one other man. Find the least number of women in the line such that <math>p</math> does not exceed 1 percent.
+
Six men and some number of women stand in a line in random order. Let <math>p</math> 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 <math>p</math> does not exceed 1 percent.
  
 
== Solution ==
 
== Solution ==
Denote (n) be n consecutive men and a space between (n) and (m) be some number of women between the mens(it can be zero).
+
Let <math>n</math> 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 <math>(k)</math> refers to a consecutive group of <math>k</math> men:
  
There are five cases to consider:
+
_(2)_(2)_(2)_
  
  (2) (2) (2)
+
  _(3)_(3)_
  
  (3) (3)
+
  _(2)_(4)_
  
  (2) (4)
+
  _(4)_(2)_
  
  (4) (2)
+
  _(6)_
  
  (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 <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 first two cases gives us all the possible ways to arrange the people. Let there be <math>k</math> women. For the first case, if we think of (n) as dividers, we get <math>\dbinom{n+3}{3}</math> ways. For the second cases, we get <math>\dbinom{n+2}{2}</math> cases.
+
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 third to fifty cases counts the cases we desires.
+
The last case gives us <math>\dbinom{n+1}{1}=n+1</math> ways.
The third and fourth cases give us <math>2\dbinom{n+1}{2}</math> if we put 1 woman between (2) and (4) before we count.
 
  
the last case gives us <math>\dbinom{n+1}{1}</math>
+
Therefore, the total number of possible ways where there are no isolated men is
  
so the probability is <math>\dfrac{  2\dbinom{n+1}{2} + \dbinom{n+1}{1}}{\dbinom{n+3}{3}+\dbinom{n+2}{2}}</math>
+
<cmath>\dbinom{n+1}{3}+3\dbinom{n+1}{2}+(n+1).</cmath>
  
the numerator simplifies into <math>(n+1)^2</math>.
+
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
  
The denominator simplifies into <math>\dfrac{(n+6)(n+2)(n+1)}{6}</math>
+
<cmath>2\dbinom{n+1}{2}+(n+1).</cmath>
  
so the whole faction simplifies into <math>\dfrac{6(n+1)}{(n+6)(n+2)}</math>
+
Thus, we want to find the minimum possible value of <math>n</math> where <math>n</math> is a positive integer such that
  
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 equals to each other when <math>n = 594</math>.
+
<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>
  
If we let <math>n= 595</math> or <math>593</math>, we will notices that the answer is <math>\boxed{594}</math>
+
After simplification, we arrive at <cmath>\dfrac{6(n+1)}{n^2+8n+6}\le\dfrac{1}{100}.</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.
 +
 
 +
== See also ==
 +
{{AIME box|year=2011|n=I|num-b=11|num-a=13}}
 +
{{MAA Notice}}

Latest revision as of 10: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 (ProblemsAnswer KeyResources)
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

Invalid username
Login to AoPS