## Seating around a Table

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Seating around a Table

Okay so I have a puzzle for you guys, I read it in The Bent magazine, but I believe it was published elsewhere before.

In how many ways, order matters, can 14 married couples be seated in chairs consecutively 1 to 28 at a round table so that one man is always between two women and no man ever sits next to his wife?

Intriguing isn't it.

My way of looking at the problem
Spoiler:
We think of the married couples as two 14 digit sets, husband and wife are represented by the same digit. How many 28 digit numbers exist so that there are no repetitions and the first and last digits are unique.

My attempt at a calcultation
Spoiler:
For our first digit we have n choices, since the second cannot be the partner of the other we have (n-1) choices.
Our third choice cannot be equal to our first or second, therefore n-2, likewise our fourth is n-2 since it cannot be equal to the second or third. Seeing a pattern yet?

I believe that we arrive at n(n-1)(n-2)(n-2)(n-3)(n-3).... or n(n-1)((n-2)!)^2. For the given parameters this is about 1.38*10^24, so there are quite a few ways to sit the party it would seem.

Let me know where I messed up!
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Seating around a Table

dshizzle wrote:Okay so I have a puzzle for you guys, I read it in The Bent magazine, but I believe it was published elsewhere before.

In how many ways, order matters, can 14 married couples be seated in chairs consecutively 1 to 28 at a round table so that one man is always between two women and no man ever sits next to his wife?

Intriguing isn't it.

My way of looking at the problem
Spoiler:
We think of the married couples as two 14 digit sets, husband and wife are represented by the same digit. How many 28 digit numbers exist so that there are no repetitions and the first and last digits are unique.

My attempt at a calcultation
Spoiler:
For our first digit we have n choices, since the second cannot be the partner of the other we have (n-1) choices.
Our third choice cannot be equal to our first or second, therefore n-2, likewise our fourth is n-2 since it cannot be equal to the second or third. Seeing a pattern yet?

I believe that we arrive at n(n-1)(n-2)(n-2)(n-3)(n-3).... or n(n-1)((n-2)!)^2. For the given parameters this is about 1.38*10^24, so there are quite a few ways to sit the party it would seem.

Let me know where I messed up!

A few things.
Spoiler:
Your recasting as a string of quadridecimal digits ignores the fact that the table is round. The first and last of your string are also adjacent.

Spoiler:
Suppose you start your string with 1231... . Your counting method would have it that for the fifth place you have n-3 possible choices. There are however n-2 choices. You have assumed that there is always one choice eliminated because of the adjacent previously placed person, but in this example that is not so because that choice was already not available as he is seated already.

Edit: I don't know offhand how you can calculate it though, unless you use a recursive or dynamic computer program.

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Seating around a Table

Your recasting as a string of quadridecimal digits ignores the fact that the table is round. The first and last of your string are also adjacent.

hmm, I did realize this, thats why the first and last integers must be unique relative to one another.

Suppose you start your string with 1231... . Your counting method would have it that for the fifth place you have n-3 possible choices. There are however n-2 choices. You have assumed that there is always one choice eliminated because of the adjacent previously placed person, but in this example that is not so because that choice was already not available as he is seated already.

I completely missed that case! that might confound my ability to come up with a quick solution. The problem was offered as a computer based problem so I think they expect a more algorithmic kind of solution.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Seating around a Table

Although I suppose it does function as an upper bound, but not a solution.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

CCC
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

### Re: Seating around a Table

In how many ways, order matters, can 14 married couples be seated in chairs consecutively 1 to 28 at a round table so that one man is always between two women and no man ever sits next to his wife?

Do you mean so that each man is between two wonen, thus mwmwmwmw... or so that at least one man is between two women (wmwmmwwmmmwww...)?

I tried, assuming that each man should be between two women, for smaller numbers of couples:

Spoiler:
One or two couples, no solutions (each husband must sit next to his wife, if they're alternating).

Three couples, I found 12 possibilities (3!*2) (once the women are in position, there's not much choice about the men).

Four couples, I found 96 possibilities (4!*2*2) (once the women are in position, place a single man (choice of two options) and the rest of the men's positions are forced)

Five couples, I found 3120 possibilities (5!*2*13) (once the women are placed randomly, there appear to be 13 possibilities for arranging their husbands that I could find)

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

### Re: Seating around a Table

This sounds suspiciously like a homework problem, and I believe the exact problem is in Ross.

Edit: didn't pay enough attention to your intro. Nevertheless, I distinctly recall solving this problem in my probability course.

If it is not a homework problem, I can dig up the solution. I'm too tired and sore to reason through it manually right now.

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Seating around a Table

This sounds suspiciously like a homework problem, and I believe the exact problem is in Ross.

Edit: didn't pay enough attention to your intro. Nevertheless, I distinctly recall solving this problem in my probability course.

If it is not a homework problem, I can dig up the solution. I'm too tired and sore to reason through it manually right now.

It's funny how pretty much every math problem phrased can sound like a homework problem if you choose the class properly. But no, this was not inspired by a class, we college kids take summers off to work where I'm from. If you have a solution thats great but please spoiler it. I'm gonna see if I can fix my solution.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Seating around a Table

CCC wrote:
In how many ways, order matters, can 14 married couples be seated in chairs consecutively 1 to 28 at a round table so that one man is always between two women and no man ever sits next to his wife?

Do you mean so that each man is between two wonen, thus mwmwmwmw... or so that at least one man is between two women (wmwmmwwmmmwww...)?

I tried, assuming that each man should be between two women, for smaller numbers of couples:
Yes wmwmwmwmwmwm alternating,
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Seating around a Table

Also if anyone has a good hint for a probability text I'd love to have it, my experience with probability is relegated to google.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

### Re: Seating around a Table

dshizzle wrote:Also if anyone has a good hint for a probability text I'd love to have it, my experience with probability is relegated to google.

Ross (which I linked above) is very good.

Also, clues to the solution in the spoiler

Spoiler:
This is known as the Menage problem: http://en.wikipedia.org/wiki/M%C3%A9nage_problem

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Seating around a Table

Finally gave in and looked at the page, good thing too, wasn't anywhere close to the solution. Funny how missing a simple thing can make such a difference in complexity.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

### Re: Seating around a Table

dshizzle wrote:Finally gave in and looked at the page, good thing too, wasn't anywhere close to the solution. Funny how missing a simple thing can make such a difference in complexity.

The basic way to solve this problem is to use the fundamental principle of counting, then the inclusion exclusion principle.

Obviously, if you seat the women first, imagine that the chairs are alternating red and blue. There are 14! ways to seat the women in blue chairs, and 14! to seat them in red chairs, so that's where the 2*14! comes from.

The summation term is a bit more complicated to reason, but the (-1)^k term there comes from inclusion-exclusion.

Fundamental principle of counting then gets invoked to multiply the summation term by 2*14!.

So it's simple at the outset, but it does become more challenging when you try to reason out the ways to seat the men.

Jaywalk3r
Posts: 14
Joined: Fri Apr 06, 2012 5:07 am UTC

### Re: Seating around a Table

dshizzle wrote:Okay so I have a puzzle for you guys, I read it in The Bent magazine, but I believe it was published elsewhere before.

In how many ways, order matters, can 14 married couples be seated in chairs consecutively 1 to 28 at a round table so that one man is always between two women and no man ever sits next to his wife?

It's the Ménage problem.