Discrete Math - Pigeonhole Principle Problem

[Rockoz]

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.

 

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

 

[Rockoz]

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

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