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)
There is an upper bound to the number of days ("arrangements")
that can exist for a given number of people. A simple proof will show
that for N people, you can have at most (N-1)(N-2)/2 seatings (exercise
for reader). That means for 6 people, you can have at most 10
arrangements and for 12 people, 55.
However, whether there exists such an arrangement is another matter!
I've written a program to do an exhaustive search for the full maximal
schedule given a number of people (will post source code over the
weekend). It successfully finds the 10 arrangement schedule for 6 but
completes the exhaustive search for 7 people and 15 arrangements with
no solution. I.e. I believe you cannot find 15 arrangements for 7
The search took several minutes to run on my laptop for 7 people but it
would probably take millenia to search for 55 on 12 (since this is an
exponentially growing search space). However, I'd be well impressed if
anyone can find a 15 seating arrangements for the 7 member conversing
Posted by Glorat
on 2004-08-12 05:43:29