Look for the smallest n of colors to color and make the keys distinguishable

Question

taken from a practice for an admission test:

why 2? If I have only 2 colors (A and B), I can only make these permutations:

AA AB BA BB

That are not enough for 8 keys even if I leave a key without color, another colored only the half of A, and another colored only half of B, in this case I would have 7 permutations that still not enough.

AA AB BA BB 0 0B A0

('0'='no color')

Answer 1

Assumptions:

1. By “colour”, we really mean any marking of the key in such a way that keys with different colours are distinct, but keys with the same colour are not (without further information). So “leaving uncoloured” is one colour, as is “red on one half”, “red and blue stripes”, “marking with a number”…
2. The keys stay on the ring, but can move around the ring freely. There is no “first” or “last” key, but each key is always adjacent to the same two others. Flipping the ring over means “left” and “right” neighbours can’t be distinguished.

With these assumptions, we have two items of information to distinguish one key from another: its colour, and its neighbours’ colours.

With two colours, we have two options for colouring the key itself (A or B). Considering just its immediate neighbours, we have three options (both A, both B, one of each), for 2×3=6 combinations… not enough. But considering its next-but-one neighbours as well, we have ten options (AA…AA, AA…AB, AA…BA, AA…BB, AB…AB, AB…BA, AB…BB, BA…AB, BA…BB, BB…BB), for 2×10=20 combinations total.

In short, each run of five keys has twenty possible combinations of colours, which we can use to identify the key in the middle. It remains only to find a colouring of all eight keys such that each five-key run uses a different combination.

By trial and error, I ruled out multiple arrangements before finding that AAABABBB works. I suspect, but haven’t bothered to prove, that it may well be unique!

(Credit to Daniel Mathias, whose comments contained the essential points of the answer and the same colour arrangement.)