Skip to content

Thanksgiving Combinatorial Puzzles

November 26, 2008 pm30 4:56 pm

In Combinatorics today I will give students 6 puzzles to work on. The rules and puzzles are printed beneath the fold.

All of these puzzles have appeared here at least once before: last Thanksgiving. Sorry.

Click for my worksheet —>

There are six puzzles, worth 6 points each.  The points for each puzzle will be evenly divided among the groups solving that puzzle. The points you earn will be added to your most recent test score.

Good luck!

Puzzles:

1. At Thanksgiving dinner, there is turkey, cranberry sauce, stuffing, yams, mashed potatoes, and carrot casserole. How many different plates can be prepared if each plate has at least 2 items?

2. Four husband-wife couples will sit around a round table.
a) How many seating arrangements are possible?
b) How many boy-girl seating arrangements are possible?
c) If they try out each possible boy-girl seating arrangement for 20 seconds, how long will it be until they start eating?

3. Three husband wife couples will sit around a round table.  How many seating arrangements are possible without any spouses sitting next to each other?

4. There are eight people sitting around a round table. They all jump up to get food, and in their rush to start eating, they carelessly sit in the first seat they come to.  How many ways could they all end up in new seats?

5. There are eight people sitting around a round table. They all jump up to get food, and in their rush to start eating, they carelessly sit in the first seat they come to.
a) How many ways could exactly 2 of them end up in new seats?
b) How many ways could exactly one of them end up in a new seat?
c) How many ways could none of them end up in new seats?

6. There are eight people sitting around a round table. Each person reaches out to shake hands, and as they are shaking, they freeze. The most popular woman (a math geek) points out that there are four hand shakes going on, but that none of their arms are crossing. How many ways can this be done?

Advertisements
5 Comments leave one →
  1. December 1, 2008 pm31 8:43 pm 8:43 pm

    Maybe if I had tried to solve a few of these during Thanksgiving, I wouldn’t have eaten so much!

  2. February 22, 2009 pm28 6:57 pm 6:57 pm

    How many ways different seating arrangements are there for 8 people around a round table, allowing one, some or all persons to change seats with his/her right or left neighbour if he/she so wishes. Thus in any given seating arrangement, the person in the 6th seat, for example, must end up in the 5th, 6th or 7th seat; the 8th person in the 7th, 8th or 1st seat etc.

    What is the general solution for N people so seated?

    • February 22, 2009 pm28 11:09 pm 11:09 pm

      There are 8! arrangements, with no restrictions. (side note, there are (8-1)! circle permutations, if we care only about the relative positions, which is not the case here.

      But I don’t know how to do this…

      Try a smaller number of people?

      1 person, 1 way
      2 people, 2 ways
      3 people, 6 ways
      4 people, 24 ways minus something… I get 6 ways for each to be in the bad seat, that’s -24 or 0, but for every pair of guys we double counted… put 12 back, but now they everyone across from their seat thing is counted 4 times, subtract those, but we do need to count it once, add it back. 9 ways.
      I wanted to proceed with simple inclusion/exclusion, but neighbors get in each other’s way.
      5 people: 5! - \binom{5}{1} * 2*4! … but adding back in the double counts is trickier. Neighbors have fewer ways to be both in the wrong seats than non-neighbors do. 5! - \binom{5}{1} * 2*4! + 5*3*3! + (\binom{5}{2} - 5) * 4*3! ... (that’s adding in for the neighbors, then for the non-neighbors). Again we need to take away any triples, and again, the three-in-row case has fewer options… 5! - \binom{5}{1} * 2*4! + 5*3*3! + (\binom{5}{2} - 5) * 4*3! - 5*4*2! -  (\binom{5}{3} - 5) * 6*2!... (that’s taking away three in a row wrong, then three not in a row wrong). Finally I’ll add back in the cases where 4 are in the wrong place, and take away the cases where 5 are wrong: 5! - \binom{5}{1} * 2*4! + 5*3*3! + (\binom{5}{2} - 5) * 4*3! - 5*4*2! -  (\binom{5}{3} - 5) * 6*2! + \binom{5}{4} * 5 - 2

      And I will count this up, and think I have the case for 5, but without major rethinking this method will not yield a general solution.

      • February 23, 2009 pm28 4:52 pm 4:52 pm

        And to make matters worse, not only has this not led me to a general solution, but there appears to be an error…

Trackbacks

  1. A Thanksgiving Puzzle « Intrinsically Knotted

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: