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 Solution, seating generator V2.2 by Hugo)

... and by hand no less. Anyways, I thought that even if there was one line that didn't fit (as Glorat pointed out) that it was still the best solution we've seen so far for 12 people. But after looking at it some more I noticed that there more lines that didn't fit, all involving the neighbors of 12.

I have to say that I find it EXTREMELY unlikely that someone can solve this by hand. Trust me, if there is a pattern to the solution it is so much more complicated than the one you came up with. I also don't think that the fact that 55 is divisble by 5 & 11 means anything either. It's just another triangular number, just like the number of days for the solution to any number of people is going to be a triangular number. Look at the solutions for 6, 7, 8 or 9.  The solution for 7 didn't have a 3 x 5 pattern even though it had 15 lines in it. It was 15 lines long because that's what ((n-1)(n-2))/2 is when n=7. And if you can't find a 3 x 5 pattern in the solution for 7, what makes you think that there will be a 5 x 11 pattern in the solution for 12?

If you start with solving all 55 neighbors of one person that leaves 9 positions left to figure out in each row. That's means there's 9! or 362880 combinations for each row. You can pick any order for all 12 in the first row, but that just means that there's 9!^54 total possible combinations! That's about 10^300.

You will HAVE to use a computer to solve this. It's THAT big of a problem. Don't waste your time trying to solve it by hand. To solve this, it'll take you the rest of your life and, if you believe in reincarnation, any other lives that you may have. Spend your time trying to figure out a more effiencient algorithm or, like me, spend your time tryna make money so that you can buy a faster computer to solve this. I can't compete with people who have a 2.8GHz Pentium 4 when it takes my computer 4 minutes to solve 7. It could be that my program just isn't as slick as it can be, but it couldnt even solve 8 over a weekend. I think that the reason why Gamer originally gave this a difficulty of 3 was because he had no idea how complicated it really was. I doubt he posted this with a solution! ...despite what SilverKnight said. I think he just picked 12 people in TCC3 because that's how many people were used in TCC2, not realizing there were 10^300 total combinations.

After about 2 hours of searching my computer found six 48 day solutions for 55 people, and no 49 day solutions yet. It's just not worth it with my computer.

Posted by Danny on 2004-10-11 20:45:48