Alice and Bob are in a hardware store
Source: Canadian Mathematical Olympiad - 1984 - Problem 2.
June 26, 2011
geometrygeometric transformationrotationcombinatorics unsolvedcombinatorics
Problem Statement
Alice and Bob are in a hardware store. The store sells coloured sleeves that fit over keys to distinguish them. The following conversation takes place:
[color=#0000FF]Alice: Are you going to cover your keys?
[color=#FF0000]Bob: I would like to, but there are only colours and I have keys.
[color=#0000FF]Alice: Yes, but you could always distinguish a key by noticing that the red key next to the green key was different from the red key next to the blue key.
[color=#FF0000]Bob: You must be careful what you mean by "next to" or "three keys over from" since you can turn the key ring over and the keys are arranged in a circle.
[color=#0000FF]Alice: Even so, you don't need colours.
Problem: What is the smallest number of colours needed to distinguish keys if all the keys are to be covered.