I have a number of keys on my keyring and want to find the correct key as fast as possible. Unfortunately, all the keys look the same. However, I can see if the teeth are turned the same or opposite way as the two keys next to it.
The issue: I pick up my keyring from my pocket and hold onto one key. I do not know which way this key is or if it is turned one way or the other. Now I can move sideways on the keyring and can keep track of the keys I've gone through.
I want to find the best pattern to put my keys on the keyring. The best pattern include:
- When starting at a random key I can move through the neighboring keys and identify where I am.
- The number of keys I must go through must be as low as possible.
- "Lowest" is the worst case scenario no matter where you start on the keyring.
- The pattern should be general and can accommodate any number of keys.
- State if your solution does not work for a specific number of keys on the keyring (probably such as two keys).
- The solution does not involve lateral thinking like marking the keys, counting the number of teeth on a key or similar.
- The solution mentioned in this question (Identical-Looking Keys on a Ring), can force you to go through all but one key. So another solution can probably be applied.
- This is not about finding the correct key, but identifying where on the keyring I am.
An example with an issue: You have four keys and put two of them one way and two of them the other way. Here you will never figure out where you are. So another pattern must be used.
What is the best pattern?
I do not know the optimal solution myself.
To compensate for my lack in English (non-native), I'll give an example with five keys. :)
If I set it up like the following I am never able to determine anything.
If I set it up like the following, I am able to determine it (at some point).
I put the five keys into my pocket and take them out again and start by looking at one key (marked with red teeth). Here I do not know if I've picked up a key which is orientated like A or like B-E.
So I move one to the right and now know the orientation is the same on these two.
Based on this I can deduce the orientation, but I still do not know if my starting position was B, C or D
I go one to the right and look at the next key which shows me the same orientation. I now know I started at either B or C.
I go one to the right again which shows me the same orientation of the next key. I now know where I started.
Since I know where I started I can conclude the following.
Overall, I had to look at four keys. I can generalize this and say that with N keys, I can always find my starting position by N-1 operations (for N>2). The question is if a general solution can be better than this.
I do believe that no better solution can be found for the example of N=5 we just went through.