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)

An approach that would be similar to the 3-at-a-table problem would be to arrange 11 of the people in a circle and one person at the center and arrange 5 cycles (permutations) of the people and connect them with lines.  If the permutation is such that no two vertices have the same pair of side lengths coming from them (distinguishing clocwise from counterclockwise--that is, 1 to the left and 2 to the right is different from vice versa), then that set of lines can be rotated to give 11 days worth of new permutations in which no person is adjacent to the same pair twice.

Then another such cycle would have to be created for days 12-22, also not repeating any variety of vertex, including not repeating any from the first cycle.

There are a total of 60 types of vertex, including 5 that have the vertex at the center, so there are 55 along the outside (11 for each of 5 such cycles), where 11 of the people are.  Each 11-day cycle permutation has to include one of the 5 V-at-center pieces, plus two different vertices that include a reach to the center, and 9 vertices that go from one point on the circle to another.

The V-at-center pieces differ in that one spans one unit along the circle, another two, up to 5 (as a span of 6 is just 5 in the other direction).  The 10 pieces that include one reach to the center have as their other arm spans of -5 to +5 (where -5 = +6).  Here, they're different as the reach to the center is at one end or the other.

There are 45 edge-to-edge pieces (vertices). They include, referenced by leg spans, 1,1 to 1,5 and 1,-5 to 1,-2 (1,-1 doesn't make sense as it would require a vertex to be visited twice).  Then come 2,1 to 2,5 and 2,-5 to 2,-3. (2,-2 is excluded for the same reason as -1,-1, and 2,-1 is excluded because it would span the same sets of vertices as 1,-2).  And so forth.

These have to be linked together in five sets of eleven, each set making sure that adjacent vertices are compatible (they share one leg) and that each vertex gets visited once and only once.  For example, 2,4 could be followed by 4,5, or by 3,-4 (hooked up in reverse), but not by 5,3. If 2,4 is followed by, for example 4,2, the next vertex can't be 2,3, as that would circle around the the vertex to the left of the original vertex (2+4+2+3=11).

Assembling 5 such cycles out of the 45 regular pieces, 10 reach-to-center pieces and 5 V-at-center pieces had my computer running all night still not finding an answer or even getting to the fifth cycle and therefore not changing the first day's to an alternate possibility if that one were impossible to allow for the rest.

Posted by Charlie on 2004-03-29 16:50:08