January 2005
<<December January February>>
Answer:
There is no obvious general way to attack this problem. However, with the seven colors called A, B, 0, 1, 2, 3, 4, one solution is:
1243A0B 2304A1B 3410A2B 4021A3B 0132A4B.
The spaces partition the necklace into five 7-bead segments to call attention to the symmetry: Any bead and the bead 7 positions further along are of the same color when that color is A or B; otherwise the latter is 1 more (modulo 5) than the former. QED
This solution does not readily extend to other numbers of colors. It is not unique:
1. There are 14 solutions with the above symmetry. One segment of each of these solutions is:
1243A0B, 0231A0B, 3014A0B, 0312A0B, 1023A0B, 2314A0B, 2341A0B, 0214A0B, 0341A0B, 3124A0B, 1024A0B, 3012A0B, 0243A0B, 0324A0B.
2. The colors of a solution may be arbitrarily permuted, yielding a solution with perhaps a modestly different symmetry. Among these permutations are those having the same effect as reversing the necklace and/or changing the increment for the segment-to-segment color changes.
3. Given a solution, any sequence of beads such that the last two beads in the sequence are the same as the first two but in the reverse order, may be reversed to yield a new solution, which generally has no simple symmetry. For example, in the original solution the sequence 43A0B 2304A1B 34 may be reversed, yielding the solution:
1243B1A 4032B0A 3410A2B 4021A3B 0132A4B.
(James B. Shearer pointed out this technique.)
4. Patrick LoPresti investigated solutions for other choces of the parameters:
"So far, my program has found these solutions for (n,m,nCm), where n is the number of colors, m is the size of the subset, and nCm is n-choose-m. I have omitted the trivial cases of m=1 and m=n-1, as well as the unsolvable cases where n does not divide nCm.
(5,2,10)
0 1 2 0 3 1 4 2 3 4
(5,3,10)
no solution
(7,2,21)
0 1 2 0 3 1 4 0 5 1 6 2 3 4 2 5 3 6 4 5 6
(7,3,35)
0 1 2 3 0 1 4 2 0 5 1 2 6 0 3 4 1 5 6 2 4 3 5 0 4 6 3 2 5 4 6 1 3 5 6
(7,4,35)
0 1 2 3 4 0 1 2 5 3 0 1 6 4 2 0 5 6 3 1 4 5 2 6 3 0 4 5 1 6 2 3 4 5 6
(7,5,21)
No solution.
(8,3,56)
still running...
(8,5,56)
0 1 2 3 4 5 0 1 2 3 6 4 0 1 2 7 5 3 0 1 6 7 4 2 0 5 6 3 4 7 1 2 5 6 0 7 3 4 1 5 6 2 3 7 0 4 5 1 6 7 3 2 4 5 6 7"
Thanks, Patrick
5. John Fletcher remarks:
An (n,2) necklace always exists when n is odd, as the following recursive construction shows: Label the n colors with the integers from 0 to n-1. Given a sequence of n(n-1)/2 beads (starting with 0) for a necklace of n colors, a sequence for n+2 colors is obtained by appending to that sequence the following sequence of 2n+1 beads: 0, n, 1, n+1, 2, n, 3, n+1, ... , n+1, n-3, n, n-2, n+1, n-1, n, n+1 . (Except for the final n+1, alternate beads form two subsequences, each of n beads: 0, 1, 2, ..., n-1 and n, n+1, n, n+1, ..., n.) The recursion begins at n = 1 with an empty necklace. This is followed by:
for n = 3: 0, 1, 2;
for n = 5: 0, 1, 2, 0, 3, 1, 4, 2, 3, 4;
for n = 7: 0, 1, 2, 0, 3, 1, 4, 2, 3, 4, 0, 5, 1, 6, 2, 5, 3, 6, 4, 5, 6;
etc.
It is not difficult to see that each sequence retains all adjacent color pairings from its predecessor, to which it adds the pairing of the two new colors with each other and all 2n pairings of each of them with each of the n old colors.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com