Math about Christmas Meals (Corrected)

One day, a particular family went to a restaurant to have their Christmas dinner. This family has children, Adam, Ben, Carrie and David who are choosy over their food. Luckily, the restaurant provides set meals specifically made for choosy children, namely, Chicken Burger, Vegetable Frenzy, Spicy Gala and Steak.

Adam doesn't eat chicken and vegetable; Ben doesn't eat spicy food; Carrie doesn't eat chicken; and David doesn't eat beef. In how many ways can Mum order for a different set meal for each of the children such that all end up satisfied? (The children don't want to be called "copycats" so they all want different set meals from each other.)


The answer is 6.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Happy Melodies
Dec 27, 2013

This question can be easily solved using trial and error (due to the small cases) but I have used a slightly different technique known as the Rook's Polynomial. (If you are interested, I have posted an introduction on it here )

First, construct a 4 × 4 4 \times 4 board B 4 , 4 B_{4,4} as seen in the diagram. Label the rows with the names of each children (the first letter of the names as a short form), and the columns with the names of the set meals. Let the restrictions (e.g. Carrie doesn't eat chicken) be shaded in green.

Diagram Diagram

Then, lets reconstruct B 4 , 4 B_{4,4} into disjoint subboards by switching row(s) or/and column(s) (in this case, done by switching rows B B and C C .) From the diagram below (with blue shaded squares), we can see that there are 3 3 disjoint subboards ( B 1 , B 2 , B 3 B_1, B_2, B_3 ).

Diagram 2 Diagram 2

Here, using Rook Polynomial (do look at the intro), we get

R ( x , B 4 , 4 ) = R ( x , B 1 ) R ( x , B 2 ) R ( x , B 3 ) = ( x 2 + 3 x + 1 ) ( x + 1 ) 2 = x 4 + 5 x 3 + 8 x 2 + 5 x + 1 R(x, B_{4,4}) = R(x, B_1)R(x, B_2)R(x, B_3) = (x^2 + 3x+1)(x+1)^2 = x^4 + 5x^3 +8x^2 +5x +1

Then, using the inclusion-exclusion formula, our answer is

4 ! 5 ( 3 ! ) + 8 ( 2 ! ) 5 ( 1 ! ) + 1 ( 0 ! ) = 6 4! - 5(3!) + 8(2!) - 5(1!) +1(0!) = \boxed{6} .

Wow this is a much more elegant and neat solution than mine! I'll definitely try to get familiar with this versatile and dandy technique!

Milly Choochoo - 7 years, 5 months ago
Milly Choochoo
Jan 3, 2014

How I solved it was I represented each person as a letter ( A A for Adam, B B for Ben, C C for Carrie, and D D for David. Then I represented the meals as subscript numbers ( 1 1 for Chicken Burger, 2 2 for Vegetable Frenzy, 3 3 for Spicy Gala, and 4 4 for Steak. After reading the last paragraph, you get the following:

A 34 B 124 C 234 D 123 A_{34} - B_{124} - C_{234} - D_{123}

Now this is really easy because, since the children don't want to be copycats, when you assign a particular meal ( 1 1 , 2 2 , 3 3 , or 4 4 ), you can be sure that nobody else will get it, therefore allowing you to 'cross it off the list'. In general, this is just a basic combinatorics problem.

Okay so all we want to do is see how many ways we can organize the numbers 1 1 , 2 2 , 3 3 , and 4 4 , but with the restrictions/conditions as stated above (make sure no kid is assigned a meal they don't want and no copycats).

A 3 B 1 C 4 D 2 A_{3} - B_{1} - C_{4} - D_{2}

A 3 B 2 C 4 D 1 A_{3} - B_{2} - C_{4} - D_{1}

A 3 B 4 C 2 D 1 A_{3} - B_{4} - C_{2} - D_{1}

A 4 B 1 C 2 D 3 A_{4} - B_{1} - C_{2} - D_{3}

A 4 B 1 C 3 D 2 A_{4} - B_{1} - C_{3} - D_{2}

A 4 B 2 C 3 D 1 A_{4} - B_{2} - C_{3} - D_{1}

That's a total of 6 \boxed{6} combinations!

William Cui
Jan 3, 2014

Let's abbreviate our meals as CB, VF, SG, and S. We know that Adam can't eat CB or VF, so he can only eat SG. Ben can only eat CB, VF, and S; Carrie can only eat VF, SG, and S; and David can only eat CB, VF, and SG. Since there are 24 total arrangements (they don't want to be "copycats") that may or may not satisfy their wants, we can just systematically list out the possible ways that work.

Adam----------Ben----------Carrie---------David

SG................CB............S..................VF

SG................VF............S..................CB

SG................S...............VF...............CB

S...................CB............VF...............SG

S...................CB............SG...............VF

S...................VF............SG...............CB

Hmm I tried this code but it won't work (oops every \ gets doubled)

\\\[ \\begin\{tabular\}\{ l | l | l | l \}Adam & Ben& Carrie &David \\\\ \\hline SG & CB & S & VF\\\\ SG & VF & S & CB\\\\ SG & S & VF & CB\\\\ S & CB & VF &SG\\\\ S & CB & SG & VF \\\\ S & VF & SG & CB \\end\{tabular\} \\\]

William Cui - 7 years, 5 months ago

Is this what you're looking for: alt text alt text

minimario minimario - 7 years, 5 months ago

Log in to reply

yeah lol apparently you have to use array instead of tabular

William Cui - 7 years, 5 months ago

Log in to reply

No, you don't...

minimario minimario - 7 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...