3
$\begingroup$

Source: Purple Comet Spring 2009 Problem 20

Five men and seven women stand in a line in random order. Let $m$ and $n$ be relatively prime positive integers so that $\frac{m}{n}$ is the probability that each man stands next to at least one woman. Find $m + n$

I've gotten an answer but for some reason it is incorrect. The correct answer is $287$. Here's what I've done: First, let us use complementary counting to find the number of ways to arrange the men and women such that there exists one man who is not adjacent to any women. Then, there must be a section of MMM (an M is a male), MMMM, or MMMMM. Now, let's count with PIE.

There are $10$ places to put the MMM in a string of 12 letters, and for the remaining men and women, there are $\binom{9}{2}$ ways to arrange them. So, we have $10 \cdot \binom{9}{2}$. However, this overcounts MMMM twice, so we subtract each MMMM once. There are $9$ places to put an MMMM and $\binom{8}{1}$ ways to place the remaining men and women, so we have $10 \cdot \binom{9}{2} - 9 \cdot \binom{8}{1} = 360 - 72 = 288$. MMMMM is counted correctly because we count it 3 - 2 = 1 time. There are $\binom{12}{5} = 792$ ways to arrange the men and women in total, so we have $1 - 288/792 = 504/792 = 7/11$. So, we get $7 + 11 = 18$, which is wrong.

$\endgroup$
1
  • 3
    $\begingroup$ Consider also MM at the beginning or end. $\endgroup$
    – RobPratt
    Mar 23 at 3:27

3 Answers 3

Reset to default
3
$\begingroup$

Inclusion-exclusion seems complicated here. A simpler approach with fewer cases is to use stars and bars to count the good arrangements. Suppose first that all men are isolated, and let $w_1,\dots,w_6$ be the number of women in each of the resulting blocks: $$w_1 \quad M \quad w_2 \quad M \quad w_3 \quad M \quad w_4 \quad M \quad w_5 \quad M \quad w_6$$ Then $w_1+\dots+w_6=7$ and $w_i\ge 1$ for $i\in\{2,3,4,5\}$. Equivalently, we want to count the nonnegative integer solutions to $y_1+\dots+y_6=7-4$, and by stars and bars this count is $\binom{7-4+6-1}{6-1}=\binom{8}{5}=56$. Perform similar computations for the cases with one or two MM. The resulting total turns out to be $356$, which yields probability $356/\binom{12}{5}=89/198$.

$\endgroup$
2
  • $\begingroup$ Oh, I had completely forgotten about stars and bars. I thought it would be too complicated to directly calculate the probability, so I just skipped the option entirely. $\endgroup$
    – CrazyVideoGamer
    Mar 23 at 16:02
  • $\begingroup$ For the cases with $w_1 \ MM \ w_2 \dots$, you need $w_1 \ge 1$, and for the cases with $MM$ at the right, you also need the rightmost $w_i \ge 1$. $\endgroup$
    – RobPratt
    Mar 23 at 17:07
2
$\begingroup$

The error in your attempt is here:

Then, there must be a section of MMM (an M is a male), MMMM, or MMMMM.

You have missed out the possibility that it starts or ends with MM.

Everything else you've done is correct, so $7/11$ is the probability that there are no three (or more) men in a row.

$\endgroup$
2
$\begingroup$

If men were to be all separate, there are clearly $8$ spots where they can be put to satisfy the given conditions.$\quad-W-W-W-W-W-W-W-$

But there are $6$ "non-edge" spots, where two men can be put while still satisfying conditions

You should be able to get the answer directly without taking recourse to inclusion-exclusion or stars and bars.

$\dfrac{\dbinom85 +\dbinom61\dbinom73+\dbinom62\dbinom61}{\dbinom{12}5} = \dfrac{89}{198}$

$\endgroup$
3
  • $\begingroup$ @RobPratt: Quite, but what if OP has not yet learnt stars and bars ? $\endgroup$
    – true blue anil
    Mar 23 at 14:19
  • $\begingroup$ By introducing decision variables $m_i$ for the number of men in spot $i$, this is equivalent to counting the nonnegative integer solutions to $\sum_{i=1}^8 m_i=5$ with $m_i \le 1$ for $i\in\{1,8\}$ and $m_i \le 2$ for $i\in\{2,\dots,7\}$. $\endgroup$
    – RobPratt
    Mar 23 at 14:57
  • $\begingroup$ Because of the upper bounds on $m_i$, the stars and bars approach doesn't directly apply, but the reformulation as counting nonnegative integer solutions is still a useful way to think about the problem. $\endgroup$
    – RobPratt
    Mar 23 at 15:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .