3
$\begingroup$

I've been having some difficulty with the following combinatorics/probability problem (which I made up myself to give to students on a test). I think I'll cut them some slack and give them an easier one, but I'm still dissatisfied with not having found an answer.

Question: Two dinner tables at Bistrot La Renaissance each sit eight people. Bistrot La Renaissance If eight couples arrive, and their seats are allocated at random, what is the probability that at least five of the couples share the same table (i.e. at least five pairs of partners are not on separate tables)?

I reasoned to myself this way:

  • The Denominator: This one is quite easy. Each distribution can be thought of as 16-digit long binary sequences, where each digit position represents each person, and the value of each digit represents the designated table ($0$ for the first table, $1$ for the second).

    For example, $1111111100000000$ represents the first 8 people sitting at table $1$, and the second 8 people sitting at table $0$. Thus we can just consider different permutations of this example word here -- since each one represents a possibility, and all the possibilities can be represented this way. Thus the denominator is

$$\frac{16!}{8!\times8!}={16\choose 8}=12870.$$

  • The Numerator: Here is where I got stuck. We can relabel our people so that their position in the binary sequence is

    $$\underbrace{\_\_~\_\_}_{\text{Couple 1}}~ \underbrace{\_\_~\_\_}_{\text{Couple 2}}~ \underbrace{\_\_~\_\_}_{\text{Couple 3}}~ \underbrace{\_\_~\_\_}_{\text{Couple 4}}~ \underbrace{\_\_~\_\_}_{\text{Couple 5}}~ \underbrace{\_\_~\_\_}_{\text{Couple 6}}~ \underbrace{\_\_~\_\_}_{\text{Couple 7}}~ \underbrace{\_\_~\_\_}_{\text{Couple 8}}.$$

    Now there are the following two allowable cases:

    1. Four couples sit on the same table (taking it all to themselves) and the other couple sits at the other.

    2. Three couples sit on the same table, and two sit at the other.

This is pretty much as far as I got. I'm not sure how to go about tackling these cases when considering the binary sequence construction. Perhaps there is a simpler way to represent the seatings? I'd appreciate any help.

$\endgroup$
  • $\begingroup$ Have you taken a look here? $\endgroup$ – drhab Apr 13 '17 at 10:28
  • $\begingroup$ @drhab Ah, so it is harder than I thought. Thanks. $\endgroup$ – Luke Collins Apr 13 '17 at 10:30
  • $\begingroup$ @drhab But that argument is quite general. Perhaps in this situation, one can tackle the problem in cases? $\endgroup$ – Luke Collins Apr 13 '17 at 10:33
  • $\begingroup$ Yes, your restricted problem is still quite challenging, and maybe more simple to solve. That's why I do not declare your question to be a duplicate. $\endgroup$ – drhab Apr 13 '17 at 10:35
1
$\begingroup$

Note that the number of pairs at table 1 will equalize the number of pairs at table 2, so you need $3$ or $4$ pairs at one table.


Let the ladies take a seat first and select $8$ chairs for the women.

First we look at the outcome of exactly $3$ women at some table which has probability: $2\frac{\binom83\binom85}{\binom{16}{8}}$.

In that situation select $3$ out of the $8$ open seats for their husbands.

The probability that they come to sit at the same table as their wives is $\frac{\binom53\binom30}{\binom83}$.

Now we look at the outcome of exactly $4$ women at both tables which has probability: $\frac{\binom84\binom84}{\binom{16}{8}}$.

In that situation select $4$ out of the open seats for the husbands of the women at table 1.

Probability that $3$ of them join their wives is: $\frac{\binom43\binom41}{\binom84}$.

Probability that $4$ of them join their wives is $\frac{\binom44\binom40}{\binom84}$.

Other situations are not relevant and we end up with probability:$$2\frac{\binom83\binom85}{\binom{16}{8}}\times\frac{\binom53\binom30}{\binom 83}+\frac{\binom44\binom40}{\binom84}\times\left[\frac{\binom43\binom41}{\binom84}+\frac{\binom44\binom40}{\binom84}\right]$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.