2011 AIME I Problems/Problem 12
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 that we need to insert two dividers among the possible locations. Each gives us ways, for a total of ways.
The last case gives us ways.
Therefore, the total number of possible ways where there are no isolated men is
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
Thus, we want to find the minimum possible value of where is a positive integer such that
The numerator is equal to
For the denominator, we get
So, we get
We know that is positive since 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
Thus we seek the smallest positive integer value of such that . Since the quadratic function's discriminant, or , 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 we want must be either slightly larger than the positive root (if the other, smaller root is less than ) or equal to (if the smaller root is greater than or equal to ). We see that does not satisfy the inequality, so the smaller root is irrelevant.
The solution to the polynomial is
We want the larger solution and to find the smallest integer greater than that solution. So, we will look only at the case, not the .
Let's look at the discriminant:
So .
Let .
Therefore, we're looking for
Since we have , we get
Since , .
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.