POW #5: Disambiguating Keys

We have a circular key chain and want to color the keys, using as few colors as possible, so that each key can be identified by the color pattern--that is, by looking at the key's color and neighboring colors as far away as needed. Let f (n) be the minimal number of colors required to uniquely disambiguate a circular key chain of n keys in this way.



For example, for n=4, the diagram above shows that three colors suffice--the keys can be identified as green, blue, red-next-to-green, and red-next-to-blue. By checking cases one sees that two colors is not enough to disambiguate the keys when n=4 (key rings can be flipped over, so references to left, right, clockwise, etc. are forbidden). Therefore we can conclude that f (4)=3.

Here is the problem: Determine a formula for f (n) for all positive integers n.


Return to Laura Taalman, Burruss 127, by 12/3/03.