Hosted by The Math Forum

Problem of the Week 1177

The Long Key Chain

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

Given some identically shaped keys on a circular chain, one wishes to color them so that each is identifiable by its color alone.

For example, for four keys, colors can be assigned Red, Red, Blue, Green:

The top key is the red adjacent to green, while the other red is next to blue.

A scheme can refer to neighbors at any distance, but it must work even if the chain is flipped, so one cannot use right or left.

If K(n) is the least number of colors necessary so that each of n keys can be uniquely identified, then K(1) = 1, K(2) = 2, and K(3) = K(4) = 3.

What is K(1177)?

Source: F. Rubin, Problem 729, J. Rec. Math. 11 (1979) 128; 12 (1980) 145.

© Copyright 2014 Stan Wagon. Reproduced with permission.

[View the solution]

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


14 March 2014