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?
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