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

$\endgroup$
6
  • 1
    $\begingroup$ 1/120 cannot be correct if the cook chooses each of the 7 meals he prepares indepently (and uniformly between the 4 menu items), because then there are $4^7=16384$ ways the cook can make his decision (all equally likely), and 16384 is not a multiple of 120. $\endgroup$
    – hmakholm left over Monica
    Apr 26, 2012 at 20:19
  • $\begingroup$ @Henning: If you interpret the cook preparing 7 meals, and then the seven meals being given to the guests, the combinations are not $4^7$ (where order matters); rather, you want to count the number of combinations with repetitions, of which there are $\binom{4+6}{7} = \binom{10}{3} = 120$. $\endgroup$
    – Arturo Magidin
    Apr 26, 2012 at 20:27
  • $\begingroup$ Also, it matters what the guests actually ordered. If the order was 7 hamburgers, then it's $7!/2^3=630$ times less likely for the the cook to hit the right combination than if the order was 2 hamburgers, 2 chicken tikka, 2 pork chops and 1 grilled salmon. Are we to understand that it is a part of the experiment that the guests first order randomly? $\endgroup$
    – hmakholm left over Monica
    Apr 26, 2012 at 20:28
  • $\begingroup$ Besides, the cook might prepare something not on the menu... $\endgroup$
    – copper.hat
    Apr 26, 2012 at 20:29
  • $\begingroup$ @Arturo: That's why I explicitly stated an assumption about the probability distribution the cook follows when he selects what to do. Seven independently random meals is something different from one random seven-meal combination (when the latter is chosen uniformly among all multisets of cardinality 7). $\endgroup$
    – hmakholm left over Monica
    Apr 26, 2012 at 20:30

3 Answers 3

Reset to default
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ Where do you get the information that the cook chooses randomly among the combinations-with-repetitions? You don't state it as an explicit assumption, and it doesn't feel very natural to me to assume that the cook just happens to have a deck of 120 cards with combinations-with-repetitions on them, to choose uniformly from. But I can readily imagine the cook rolling 7 d4's or somehow else choose a random meal to prepare 7 times. $\endgroup$
    – hmakholm left over Monica
    Apr 26, 2012 at 20:36
  • $\begingroup$ Yes, this seems the right problem statement -and solution. But it should be noted that "choose from all possible total orders randomly" (each total order with same probability) is not trivial, and is not the same as prepare 7 meals, each chosen at random from the 4 possible ones. $\endgroup$
    – leonbloy
    Apr 26, 2012 at 20:36
  • $\begingroup$ @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...) $\endgroup$
    – Arturo Magidin
    Apr 26, 2012 at 20:38
0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

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