- #1

Rockoz

- 30

- 0

## Homework Statement

Suppose that a menu consists of 4 main dishes, 9 choices of side dishes, and 6 desserts. A small meal consists of one main dish and two different side dishes and no dessert. A large meal consists of one main dish, two different side dishes and dessert. How many patrons must be served to guarantee that two have ordered exactly the same meal?

## Homework Equations

Pigeonhole Principle:

The pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item.

## The Attempt at a Solution

I want to apply the pigeonhole principle here but I'm a bit unsure about how to break this problem down. The following is my attempt:

So I'm thinking I want to pick the minimal number of small meals and large meals, and then add one so I get just enough to have "more pigeons than pigeonholes" as the principle wants. So for just picking small meals, we have 4 large meals to choose from, and then C(9,2) possible combinations of side dishes and no desserts. So we have 4 * C(9,2) small meals. Next we want to pick the large meals and so we have 4 * C(9,2) * 6 possible large meal combinations. (4 large meals, C(9,2) side dish combinations, and 6 desserts). Next we add one so we can use the pigeonhole principle and state that two patrons must have ordered exactly the same meal.

So I think the answer is: 4*C(9,2) + 4*C(9,2)*6 + 1.

Again, thank you for your time. Please let me know if my thinking is incorrect and why.