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 I am determined to solve this diabolical puzzle ! by Penny)

Actually there are more solutions than you think! 1st of all there are 12! ways to order the letters from A-L, right? That's almost half a billion. But if you are going to arrange them around a circle then there would be many duplicates. For ex. for each one of them you can rotate the letters from left to right and then reverse them. For 3 letters there are 6 different ways to arrange them...

ABC
ACB
BAC
BCA
CAB
CBA

 but arranged in a circle, you can see that they are all the same. I took 4 letters and arranged them to find that there are only 3 distinct combinations when put in a circle.

ABCD DABC CDAB BCDA DCBA CBAD BADC ADCB
ABDC CABD DCAB BDCA CDBA DBAC BACD ACDB
ACBD DACB BDAC CBDA DBCA BCAD CADB ADBC

Pick one from each row and you have the solution for 4 people. I thought I was onto something until I tried 5 letters.

ABCDE EABCD DEABC CDEAB BCDEA EDCBA DCBAE CBAED BAEDC AEDCB 
ABCED DABCE EDABC CEDAB BCEDA DECBA ECBAD CBADE BADEC ADECB
ABDCE EABDC CEABD DCEAB BDCEA ECDBA CDBAE DBAEC BAECD AECDB
ABDEC CABDE ECABD DECAB BDECA CEDBA EDBAC DBACE BACED ACEDB
ABECD DABEC CDABE ECDAB BECDA DCEBA CEBAD EBADC BADCE ADCEB
ABEDC CABED DCABE EDCAB BEDCA CDEBA DEBAC EBACD BACDE ACDEB
ACBDE EACBD DEACB BDEAC CBDEA EDBCA DBCAE BCAED CAEDB AEDBC
ACBED DACBE EDACB BEDAC CBEDA DEBCA EBCAD BCADE CADEB ADEBC
ACDBE EACDB BEACD DBEAC CDBEA EBDCA BDCAE DCAEB CAEBD AEBDC
ACEBD DACEB BDACE EBDAC CEBDA DBECA BECAD ECADB CADBE ADBEC
ADBCE EADBC CEADB BCEAD DBCEA ECBDA CBDAE BDAEC DAECB AECBD
ADCBE EADCB BEADC CBEAD DCBEA EBCDA BCDAE CDAEB DAEBC AEBCD

One from each bold row forms one solution, and one from each non-bold row from a different solution. So what I think is, that there is most likely millions of solutions for 12 people. Even when taking into account duplicate combinations. Since 12! is about half a billion, the number of disctinct combinations would be just 12! divided by 24 or about 20 million. But each one of those should be a part of a solution, wouldn't you think? Because it would depend on which one you start with. With 5 people, if you started with ABCDE, then the solution you find would be the ones from the bold rows from above. If you started with ABCED, then your solution would be completely different. Those 2 can't appear in the same solution (because B is between A and C in both of them) but they definately both appear in a solution because there is no reason why ABCED couldn't work itself into a solution if you started with it.

So, back to 12 people, assuming that each of the 12! / 24 appears in one and only one solution, and that any of the 12! / 24 will work in a solution, then I'd say that the total number of solutions would be 362880. Or, 12! / 24 divided by the number of days in each solution, which is 55. (edit: I realize now that it is possible for a unique combination to be a part of more than one solution. So the total number of solutions would be much greater. Don't ask me to figure out how many)

If you want to narrow down the possibilities even more you can start by choosing 3 letters in each row then all you have to do is find the remaining 9. For ex.

BAC
BAD
BAE
BAF
BAG
BAH
BAI
BAJ
BAK
BAL
CAD
CAE
CAF
CAG
CAH
CAI
CAJ
CAK
CAL
DAE
DAF
DAG
DAH
DAI
DAJ
DAK
DAL
EAF
EAG
EAH
EAI
EAJ
EAK
EAL
FAG
FAH
FAI
FAJ
FAK
FAL
GAH
GAI
GAJ
GAK
GAL
HAI
HAJ
HAK
HAL
IAJ
IAK
IAL
JAK
JAL
KAL

Now you have all the possible neighbors of A. Just find the other 9 for each row. There are 9! possibilities for the first row but once you have a complete row, there is a 9! / 55 chance to randomly guess another row that belongs to the same solution. Which I still wouldn't suggest doing because there is less than a 1 in a 10 ^ 200 chance to guess all 55 correctly. But if you want to keep track of the neighbors of each letter with each row that would help a lot. Then I think choosing the least common neighbor for each letter along the way would get you pretty far. For ex. this is what 7 letters looks like half way done (which I gave up on)

         A  B  C  D  E  F  G
ABGEFDC BC AG AD FC FG DE BE
ABFGECD BD AF ED AC GC BG FE
ABDFCGE BE AD FG BF AG CD CE
ABECGDF BF AE EG GF BC AD CD
ABCDEFG BG AC BD CE DF EG AF
AC    D CD
AC    E CE
AC    F CF
AC    G CG
AD    E DE
AD    F DF
AD    G DG
AE    F EF
AE    G EG
AF    G FG

You can see that in the next row C is looking for one more neighbor. It can't be A, C or D because they're already used in that row, so it has to be B, E, F or G. But G has been a neighbor of C twice already, and B, E and F only once. And I think, that by not choosing G you reduce you chances of running into a dead end in the future.

I'm sure I'll never figure out the solution for 12 people as I think that only someone who can program will have to solve it, but hopefully someone (Penny?) who reads this can use this to help them program a more efficient algorithm.

Edited on August 15, 2004, 12:34 pm

Posted by Danny on 2004-06-29 18:45:08