IntegerSolution AdditionPrinciple AIME Difficult
2011


Problem - 251
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.

Let $n$ be the number of women in the group. 

By the given condition, there is no isolated man in the line. Therefore, five different cases are possible depending on how these six men are standing together in groups: $(2)(2)(2)$, $(2)(4)$, $(3)(3)$, $(4)(2)$, and $(6)$. Let $x_i$, $i=1,\ 2,\ \cdots$, be the number of woman standing before the first man, between two adjacent men's groups, and after the last men. Then we have $5$ possible equations: $$\begin{align*}(2)(2)(2)&\implies x_1+x_2+x_3+x_4=n\\ (2)(4)&\implies x_1+x_2+x_3=n\\(3)(3)&\implies x_1+x_2+x_3=n\\(4)(2)&\implies x_1+x_2+x_3=n\\(6)&\implies x_1+x_2=n\end{align*}$$

In these equations, the first $x_1$ and the last $x_i$ can be $0$ or positive (a value of $0$ means no girl standing at that end), all the middle $x_i$ must be positive integers. These are all basic pattern of counting integer solutions. Their solutions are $\binom{n+1}{3}$, $\binom{n+1}{2}$, $\binom{n+1}{2}$, $\binom{n+1}{2}$ and $\binom{n+1}{1}$, respectively.

Therefore, the desired answer is the smallest integer $n$ satisfying: $$\frac{2\times \binom{n+1}{2}+\binom{n+1}{1}}{\binom{n+1}{3}+3\times \binom{n+1}{2}+\binom{n+1}{1}}\le\frac{1}{100}$$

This relation can be simplified to $$n(n-592)\ge 594$$

It follows that $n \ge 593$ in order to make the left side be positive. Then it can be determined that $n=\boxed{594}$ is the desired answer.

report an error