Solution
Unlike most of my problems, this one always elicits more wrong answers than right. At last count I received 9 incorrect and 10 correct answers, though for most of the week the wrong outnumbered the right.
The complete K-sequence is
1, 2, 3, 3, 3, 2, 2, 2, ..., 2, ...
That is, K(n) is 2 for any n ≥ 6.
The big trap here is that one feels satisfied finding a solution with 3 colors since, after all, 4 keys and 5 keys both require 3 colors.
For 6 keys or more, two colors work via RBRRBBBBBB....., wrapping around. The idea is that the red island gives a direction. This fails for five keys, which is handled by RRGRB.
Barry Cox observes that this sequence is Ceiling[(2n(n - 1))(1/n)], but that seems like a coincidence.
This problem was originally posed in 1979. I heard it from Joe Konhauser, and mentioned it in 1994 to former student Karen Collins. She mentioned it to Mike Albertson and they generalized the concept to all graphs, not just cycles. It seems that at least 50, perhaps 100 or more papers have been written on the subject.
The formal definition is as follows: Given a graph G, the "distinguishing number" of G is the minimal number of colors that can be assigned to the vertices so that there is no nonidentity automorphism of G that preserves the colors.
So one wonders, for each graph, what the distinguishing number is. For example, if our keys are in a path instead of a cycle, then the coloring GRRRRRRR...R shows that 2 colors suffice for all lengths.
The first major paper in the area is M. O. Albertson and K. L. Collins, "Symmetry breaking in graphs," Electronic J. of Combinatorics 3 (1996) #R18.
[Back to Problem 1177]
© Copyright 2014 Stan Wagon. Reproduced with permission.