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)

Because there are 55 days, and 55 = (11*10)/(2!), every person will sit next to every possible pair of neighbors among the twelve, over the course of 55 days. It isn't hard to specify these possibilities for any given person. If the twelve conversing persons are A,B,C,D,E,F,G,H,I,J,K and L, then A's neighbors during the 55 days will be: BC, BD, BE, BF, BG, BH, BI, BJ, BK, BL, CD, CE, CF, CG, CH, CI, CJ, CK, CL, DE, DF, DG, DH, DI, DJ, DK, DL, EF, EG, EH, EI, EJ, EK, EL, FG, FH, FI, FJ, FK, FL, GH, GI, GJ, GK, GL, HI, HJ, HK, HL, IJ, IK, IL, JK, JL AND KL. The problem is that all these relationships are intertwined (when BG are A's neighbors, then A is one of B's and G's neighbors, and A and G cannot both be B's neighbors, nor can A and B both be G's neighbors on that day.) No reasonable person would try to solve this problem manually. It calls for a program. An approach I would take is: Randomly generate the seating arrangements, rejecting any that produce the same neighbors anyone had on  any preceding day, until 55 days' seating arrangements have been generated, or the end of the world arrives. (The program might run a while...) 

    

Posted by Penny on 2004-03-29 15:05:29