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?

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…