2
$\begingroup$

I have a problem that goes like this:

7 people are at a restaurant. The restaurant has a menu which has four unique items from which the 7 men choose from. Each men orders one of the 4 meal options and gives their choice to the waiter. However, the waiter accidentally loses the paper that tells him what each person ordered. The waiter then tells the cook to just make whatever he wants and hope for the best (make 7 meals randomly choosing one of the 4 options for each person). What are the chances (probability) that each man actually receives what he ordered (basically that the group 7 items that were randomly made can be given such that each man can receive what he wanted)?

I saw a youtube video of someone trying to explain this problem and I wasn't quite convinced that the answer was (1/120) even though there are 120 different combinations the cook can make.

This is the video: His original problem is here, starting at 1:00 :youtube.com/watch?v=ILAGckNjXvo. And his solution is here at 2:15 : youtube.com/watch?v=E31aGpE8TH0.

What is the best way to approach this problem? Are the 120 combinations actually equally likely to be made by the cook?

Thanks

  • 0
    @Henning: But there's something wrong with that interpretation anyway: no matter how the cook chooses, the order will be "right" if his final multiset agrees with the multiset of the order, whether or not he prepared it in the same order that it was given to the waiter. That means, as per your second comment, that you would have to "weigh" the different kinds of orders in order to compute the odds that he "hit" the right combination.2012-04-26

3 Answers 3

3

If the four meals are $A,B,C$, and $D$, we’re interested in the $4$-tuple $\langle a,b,c,d\rangle$, where $a$ is the number of $A$ meals, $b$ is the number of $B$ meals, and so on. Of course $a,b,c$, and $d$ must be non-negative, and $a+b+c+d=7$. The number of possible $4$-tuples is $\binom{7+4-1}{4-1}=\binom{10}3=120\;,$ as you already knew.

This is fine, if the cook chose one of these $4$-tuples at random with equal probability. If, on the other hand, he prepared a sequence of seven meals, choosing the type of each meal independently, then these $120$ combinations are not equally likely, and the probability of getting the right one is not $1/120$.

To see why these $120$ possible combinations of meals are not equally likely, pick one, $\langle a,b,c,d\rangle$. In how many different ways can the cook make this combination of meals? He makes them in some sequence. There are $\binom7a$ ways to choose which $a$ places in the sequence are $A$ meals. Then there are $\binom{7-a}b$ ways to choose which of the remaining $7-a$ places are $B$ meals. Continuing in the same vein, we see that there are $\binom7a\binom{7-a}b\binom{7-a-b}c\binom{7-a-b-c}d\tag{1}$ ways to make $a$ $A$ meals, $b$ $B$ meals, and so on.

Now simplify $(1)$: the last factor is $\binom{d}d=1$, so it’s $\frac{7!}{a!(7-a)!}\cdot\frac{(7-a)!}{b!(7-a-b)!}\cdot\frac{(7-a-b)!}{c!(7-a-b-c)!}=\frac{7!}{a!b!c!d!}\;,$ and you can easily verify that this multinomial coefficient depends on the specific values of $a,b,c$, and $d$. In particular, it’s $1$ when $a=7$ (or when $b,c$, or $d$ is $7$): by this procedure the cook is very unlikely to prepare $7$ identical meals. On the other hand, it’s $630$ when three of $a,b,c$, and $d$ are $2$ and the remaining one is $1$.

2

As I understand the problem: the cook will prepare $7$ meals randomly, and then the waiter will take all seven meals to the guests. If the combination of meals is right, we get a "win".

So what we want to count is the number of "combinations with repetitions": we will make $7$ selections from $4$ possibilities, allowing repetitions. It seems, from the solution given, that there is an assumption that the cook will select one of these combinations-with-repetitions uniformly, an assumption I am adopting, and the question is "What are the odds that his choice will be the order?" This amounts to counting how many different total orders there can be of 7 selections from 4 possibilities, allowing repetitions.

This is a classic stars and bars problem. We want all $4$-tuples of nonnegative integers that add up to $7$. The total number is $\binom{7+4-1}{7} = \binom{10}{7} = \frac{10\times9\times 8}{6} = 120.$

So there are $120$ possible distinct total orders (just how many of each dish were ordered). The cook will prepare one set of seven dishes; if we assume he chooses from all possible total orders randomly and independently, then the odds of his getting the order right is indeed $\dfrac{1}{120}$.

  • 0
    @Henning: As with all these attempts at "real life", there is a lot missing from the statement of the problem. But, yes, I should make it clear that the uniform choice is a *hypothesis* I'm making, not information given in the problem. (For that matter, it's been shown that humans are lousy at trying to create random selections, so "choosing a random meal to prepare 7 times" is unlikely to *actually* produce a uniform distribution among the $4^7$ possible sequences...)2012-04-26
0

It all comes down to your final question

Are the 120 combinations actually equally likely to be made by the cook?

If the answer is yes, then the probability the cook chooses a correct combination must be $\frac{1}{120} \approx 0.0083$, no matter what or how the diners choose.

But if the cook chooses each dish the way the diners did (and also assuming all choices are made independently one at a time, with four equally likely possibilities) then the probability of a match improves, to $\dfrac{9671}{524288} \approx 0.0184$ which is more than double the earlier probability.

And if the cook chooses one of the four best combinations which have two each of three of the dishes and one of the remaining dish, then with the same assumption about the diners the probability of matching more than doubles again. rising to $\dfrac{7!/2^3}{4^7} =\dfrac{315}{8192} \approx 0.03845$.