# Discrete Math - Pigeonhole Principle Problem

1. Jun 4, 2012

### Rockoz

1. The problem statement, all variables and given/known data
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?

2. Relevant 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.

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

2. Jun 4, 2012

### oli4

Hi Rockoz
I believe you are correct, never heard of this 'principle' before though :)
One thing: why are you talking about 'minimal number of small and large meals' ?
this is the total number of different meals, if anything, it is maximal (maximum number of non repeating meals)

Cheers..

3. Jun 4, 2012

### Rockoz

Right, that makes sense that it should be called maximal. That's what I was trying to describe. Bad word choice by me.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook