Question 9
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:
Alice: Are you going to cover your keys?
Bob: I would like to, but there are only 7 colours and I have 8 keys.
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.
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.
Alice: Even so, you don't need 8 colours.
Problem: What is the smallest number of colours needed to distinguish $n$ keys if all the keys are to be covered.
Alice: Are you going to cover your keys?
Bob: I would like to, but there are only 7 colours and I have 8 keys.
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.
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.
Alice: Even so, you don't need 8 colours.
Problem: What is the smallest number of colours needed to distinguish $n$ keys if all the keys are to be covered.