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)

I have an algorithm which works, but it takes a fair amount of space to describe, and programming it would be more of a chore than I want to undertake right now.

Let's see if I can describe it here using 5 members and 6 days as an example...

First off, each person (we'll label them A through E5) has (4*3)/2 combinations of people they have to sit between, so for person A, the table would look like this over the six days:

day   person A's view
 1        B A C
 2        B A D
 3        B A E
 4        C A D
 5        C A E
 6        D A E

Each person has a similar set of views, so for the 5 people present, there are 30 different views, which altogether look like:

    A       B       C       D       E
 1.BAC   7.ABC  13.ACB  19.ADB  25.AEB
 2.BAD   8.ABD  14.ACD  20.ADC  26.AEC
 3.BAE   9.ABE  15.ACE  21.ADE  27.AED
 4.CAD  10.CBD  16.BCD  22.BDC  28.BEC
 5.CAE  11.CBE  17.BCE  23.BDE  29.BED
 6.DAE  12.DBE  18.DCE  24.CDE  30.CED

Now on each day we'll start the order as it's given for person A, so on day 1 we start with BAC and cross view 1 off our list of remaining views. 

Once the first three seats are assigned, we have to find the fourth seat by looking under the column of the person in the third seat (C) where they sit next to the person in the second seat (A).  We find that views 13, 14, and 15 fulfill this requirement.  However, one of the people in view 13 (B) has already been assigned a seat so we are obligated to use view 14 or 15--we'll just try the next one in line (14). 

We overlap view 1 (BAC) with view 14 (ACD) to get BACD and we cross view 14 off our list of remaining views. 

We repeat the process by looking under the column of the person in the fourth seat (D) for a view which also includes the person in the third seat (C) and find views 20, 22, and 24 (ADC, BDC, CDE).  A has already been assigned a seat and B has already been assigned a seat so we are obligated to use view 24 (CDE) and we cross view 24 off the list of remaining views.

At this point we have day number one complete as BACDE and three views crossed off our list.  We now have to cross off two more views based on the two people on the ends of our seating list (B, E)  We pick the appropriate view for the person in seat 1 by looking at who's in seats 2 and 5 (A, E) and find that view 9 gets cross off.  We repeat this step for the person in seat 5 by looking at who's in seats 4 and 1 (D, B) and find that view 29 gets crossed off.

At the end of day 1 we have one view from each column crossed off.

For day 2 we repeat this process starting with view number 2 (BAD).  In the next step we look for views under column D which include A and find 19, 20, and 21.  View 19 won't work because B is already seated so we try view 20 (ADC) which leads to us picking view 18 to complete the 5 seats.  However, at this point we find that when looking for views under column B that include A and E that the only view that would have worked (view 9) has already been crossed off the list so we have to back step to the point where we selected view 20 and pick view 21 instead, and then view 30 completes the arrangement for day 2.  In finishing off the ends of the list, views 7 and 17 also get crossed off our list.

This entire process gets repeated where we pick one view from each column for all the days required and, as we find a fit, we cross off the view that is  being used.  Tracing back is required when there are no views which fulfill then next seat's requirement.

 

Now for the problem of finding all 55 days for 12 people, we have to set up 660 individual views (55 days x 12 people), and the process will take more time than I'm willing to spend to do it manually, and I don't feel like programming it.  I'll leave that task to Penny or Charlie.

Posted by Erik O. on 2004-06-23 16:00:15