Many members of the club disliked the lack of variety and togetherness at the club. Although the club still had 12 members, some members were threatening to quit because each schedule was so short and there were so few people around each table.

To satisfy their request, the club decided to seat themselves around a big table and create a longer schedule. The twelve members of the club seated themselves in a schedule such that during each block of 55 days, no person was between the same pair of people. How was the schedule constructed?

(Based on The Round Table)

(In reply to Curses by Bruce Brantley)

When I saw the progress in this problem, using a computer to solve it, I already thought that the puzzle was invented long ango, when there where no computers around.  SK's answer that the solving method was important strengthened my conviction.

What I was looking for was a sort of seating arrangement generator.  I used the following:
two concentric circles which each have six positions to hold a figure.  On the inner circle  the numbers are at the uneven numbers of a clock, at the outer at the even positions of the clock. Starting with the number 1 position, turn clockwise and read every number you find, be it on the inner or outer circle.  This generates seating arrangement 1.  Now turn the outer circle 60 degrees clockwise, such that 12 comes at the 2 position, 2 at the 4,.
..  Read the numbers again and you have seating arrangement 2. Do this 4 more times and you have 6 seatings.

These are the first six.
Inner circle figures: 01 03 05 07 09 11
Outer circle figures: 02 04 06 08 10 12
Arrangements generated:
01 02 03 04 05 06 07 08 09 10 11 12
01 12 03 02 05 04 07 06 09 08 11 10
01 10 03 12 05 02 07 04 09 06 11 08
01 08 03 10 05 12 07 02 09 04 11 06
01 06 03 08 05 10 07 12 09 02 11 04
01 04 03 06 05 08 07 10 09 12 11 02

Following job is to rearrange the figures on the circles, such that they do not have a neighbour that they have already had. The following is a possibility:
Inner circle figures: 01 05 09 03 11 07
Outer circle figures: 02 06 10 04 12 08
Arrangements generated:
01 02 05 06 09 10 03 04 11 12 07 08
01 08 05 02 09 06 03 10 11 04 07 12
01 12 05 08 09 02 03 06 11 10 07 04
01 04 05 12 09 08 03 02 11 06 07 10
01 10 05 04 09 12 03 08 11 02 07 06
01 06 05 10 09 04 03 12 11 08 07 02

For the following set of six you have to start mixing the figures of the two circles, always remembering not to have neighbours already used.  I found three other circles:
Circle set 3:
Inner circle figures: 01 02 05 06 09 10
Outer circle figures: 03 04 07 08 11 12

Circle set 4:
Inner circle figures: 01 04 05 08 09 12
Outer circle figures: 02 03 10 07 06 11

Circle set 5:
Inner circle figures: 01 09 04 08 03 06
Outer circle figures: 02 10 11 05 12 07

The above gave me 30 seatings, but now my generator gets stuck: each figure has now had 10 neighbours and there are only 11 possible, so I can't find a new circle set.

Some thoughts:
Two concentric circles with each 6 figures are not the most efficient way to generate seatings.  Five on a circle would be better, but what should I do with the two remaining figures?  Maybe four circles withe three figures each?
I am now trying to find new arrangements, starting from mixing the circle in a set and the let it follow by a mixed version  of the other circle.  This should be good for another four solutions.
Maybe the above can be used to start a new computer based search, there are now sets of figures you can eliminate in the calculations.

And now something completely different:  when  reading the threads, I saw that different people have a number of solutions (I think taht the max was 47 out of 55), what if they where all compared, this may bring us closer to 55

Posted by Hugo on 2004-09-20 04:14:34