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.)
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.
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!
How I solved it was I represented each person as a letter ( A for Adam, B for Ben, C for Carrie, and D for David. Then I represented the meals as subscript numbers ( 1 for Chicken Burger, 2 for Vegetable Frenzy, 3 for Spicy Gala, and 4 for Steak. After reading the last paragraph, you get the following:
A 3 4 − B 1 2 4 − C 2 3 4 − D 1 2 3
Now this is really easy because, since the children don't want to be copycats, when you assign a particular meal ( 1 , 2 , 3 , or 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 , 2 , 3 , and 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 2 − C 4 − D 1
A 3 − B 4 − C 2 − D 1
A 4 − B 1 − C 2 − D 3
A 4 − B 1 − C 3 − D 2
A 4 − B 2 − C 3 − D 1
That's a total of 6 combinations!
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\} \\\]
Is this what you're looking for:
Log in to reply
yeah lol apparently you have to use array instead of tabular
Problem Loading...
Note Loading...
Set Loading...
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 board 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
Then, lets reconstruct B 4 , 4 into disjoint subboards by switching row(s) or/and column(s) (in this case, done by switching rows B and C .) From the diagram below (with blue shaded squares), we can see that there are 3 disjoint subboards ( B 1 , B 2 , B 3 ).
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
Then, using the inclusion-exclusion formula, our answer is
4 ! − 5 ( 3 ! ) + 8 ( 2 ! ) − 5 ( 1 ! ) + 1 ( 0 ! ) = 6 .