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 No solutions for the 7 person case? by Glorat)

Sorry Glorat and Penny but I have to prove you wrong. Over the last few months I've been working on a program to solve this (first I had teach myself how to write programs because I had never written programs before)  and I finally got it to work. It took my computer less than a second to solve the 6 person schedule (took me hours) but almost 4 minutes to solve 7. This is the 7 person solution it gave me...

How many people are in the club? 7
I started searching for a schedule on Aug 15, 2004 at 12:21:04

          A  B  C  D  E  F  G
ABCDEFG  GB AC BD CE DF EG FA
ABDCEGF  FB AD DE BC CG GA EF
ABFDCGE  EB AF DG FC GA BD CE
ABGCEFD  DB AG GE FA CF ED BC
ABEDFGC  CB AE GA EF BD DG FC
ACFDBEG  GC DE AF FB BG CD EA
ACBDGEF  FC CD AB BG GF EA DE
ACDGBFE  EC GF AD CG FA BE DB
ACEBFGD  DC EF AE GA CB BG FD
ADCFEBG  GD EG DF AC FB CE BA
ADEGBCF  FD GC BF AE DG CA EB
ADBGFCE  ED DG FE AB CA GC BF
AEDBFCG  GE DF FG EB AD BC CA
AEBCGDF  FE EC BG GF AB DA CD
AFBCEDG  GF FC BE EG CD AB DA

I finished on Aug 15, 2004 at 12:24:57
?

The funny thing is that the 6 person solution it gave me was different than the one I found. Not counting rotations and reversals, I found 6 solutions for 6 people. The one I originally posted, plus 5 more where I just reversed a pair of letters. I thought those were the only solutions because I assumed that each unique combination of letters appeared in only one unique solution. But I guess I was wrong. Look here...

        A  B  C  D  E  F            A  B  C  D  E  F
ABCDEF FB AC BD CE DF EA   ABCDEF  FB AC BD CE DF EA
ABDCFE EB AD DF BC FA CE   ABDCFE  EB AD DF BC FA CE
ABFECD DB AF ED CA FC BE   ABFCED  DB AF FE EA CD BC
ABEFDC CB AE DA FC BF ED   ABEFDC  CB AE DA FC BF ED
ACEDBF FC DF AE EB CD BA   ACBEDF  FC CE AB EF BD DA
ACBFDE EC CF AB FE DA BD   ACFDBE  EC DE AF FB BA CD
ACFBED DC FE AF EA BD CB   ACEFBD  DC FD AE BA CF EB
ADBECF FD DE EF AB BC CA   ADCEBF  FD EF DE AC CB BA
ADFCBE ED CE FB AF BA DC   ADFBCE  ED FC BE AF CA DB
AECBDF FE CD EB BF AC DA   AEDBCF  FE DC BF EB AD CA

The one on the left is the one I originally posted (the order of the rows was rearranged to be in alphabetical order, but it's the same solution) and the one on the right is the one the computer gave me. Notice how they match in 3 rows (1, 2 & 4) Apparently it's possible for unique combinations to be in multiple solutions for 6 or more people. I didn't realize that because for 5 people it is not possible. I explained all that in my other post. That means there could literally be millions of different solutions for 12 people. But that doesn't mean much when the total number of unique combinations you can 12 letters in 55 rows (9!^54) is a number so high that I don't think it even has a name.

Anyway, I already started the search for 8 people. I expect it to run for hours so I'll just check it tomorrow. I know that if I ever want to solve 12 people that I am going to have to change something in my program to make it run faster, like starting with a few more assumptions, otherwise it could take years for my computer to solve it.

Posted by Danny on 2004-08-15 12:47:01