Find the right key as fast as possible

Question

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.

Answer 1

First some general thoughts:

This is very much like a binary De Bruijn Sequence. For example, the binary sequence 00010111 (where the end connects to the beginning to make an 8-bit cycle) contains every possible 3-bit sequence, so just by knowing 3 consecutive bits you know exactly where in the sequence you are.

With the key ring you can consider the key orientations (teeth up or teeth down) to be the bits of a sequence, and we want to use as few (presumably consecutive) such key orientations to determine where in the sequence we are. Unfortunately a standard De Bruijn Sequence does not work here. The orientation of the keyring as a whole is not known. Turning over the keyring reverses the key order and flips them over.

Examining $k$ keys gives us $2^k$ possible orientation patterns, but this really only encodes $2^{k-1}$ possibilities because the reverse-flipped sequence is equivalent. So if at most $k$ keys are examined, the largest number of keys on the keyring we could possibly distinguish between is $2^{k-1}$ keys.
If $k$ is even, some orientation patterns of $k$ keys remain the same when the keyring is turned over, and obviously we cannot allow that ambiguity to occur. So for even $k$ the upper bound for the number of keys on the keyring is actually less than $2^{k-1}$, namely $2^{k-1}-2^{k/2-1}$.

Here is an optimal solution for the single case of $N=16$ keys on the keyring, and only $5$ keys are examined.

If the keys are numbered 1 to 16, arrange them so that keys 6, 8, 11, 15, and 16 are oriented the opposite way. In other words: 0000010100100011.
If you look at any 5 consecutive keys, there will be at most 2 reversed, so the orientation of the keyring is determined by the direction of the majority in the group of 5 keys.
Furthermore, every set of 5 is unique, as shown here:

 0000010100100011 0000

 00000
  00001
   00010
    00101
     01010
      10100
       01001
        10010
         00100
          01000
           10001
            00011
             0011 0
              011 00
               11 000
                1 0000

Note that the solution above does not automatically work for fewer keys, but

you can shorten the loop in the above solution by finding a block of four key orientations that is repeated elsewhere, and then deleting everything from the middle of the first block to the middle of the second block.
For example, using the repeated 0010 block, 0000010100100011 is shortened by 5 keys to 00000100011. In this way most shorter lengths are achievable:

    16 0000010010100011
    15 000010010100011
    13 0000010100011
    12 000010100011
    11 00000100011
    10 0000100011
     9 000100101

I used a computer to explore these keyrings further.

There is no length 14 key ring that works when you observe at most 5 keys. It is not just that you cannot make it by shortening this particular length 16 solution, but it is not even possible at all.

If you can examine 6 keys, then the number of keys on the key ring can grow up to

22 keys at most. One solution is 0000001001000101000011. This solution has at most 2 reversed keys in any block of 6, but even without that restriction, no longer sequence is possible. Note that this falls a bit short of the previously established upper bound of $2^5-2^2=28$.
All shorter lengths 17-22 and 14 are possible, though for lengths 20, 17 and 14 there need to be blocks with three reversed keys.

    22 0000001001000101000011
    21 000001001000101000011
    20 00000100100011000101
    19 0000001000101000011
    18 000001000101000011
    17 00000010010100011
    14 00000010100011

If you can examine 7 keys, then

there are perfect solutions of length 64, for example 0000000100000110000101000101100010010101001001100100011010000111. I believe that once again all shorter lengths are possible except that you cannot shorten it by 2 to 62.

I believe there are similar perfect solutions for all powers of $4$, but have no proof of that.