Shortest bitstring whose infinite repetition is different after reversal

Question

Marvin Minsky asked me the following question during my oral exam:

As an ant walks it prints a binary number (e.g., 101) every time it takes a step. What is the minimum length, in digits, the binary number can be for it to be possible to tell which direction the ant is traveling without looking at the beginning or end of the string? The ant tells you the binary number.

Example: The ant's binary number is 101 and, hence, the ant leaves a trail that looks like this: 101101101101101101101. Note that there is no way to tell which way the ant is traveling. Hence, this particular number does not work (but there may be a three digit binary number that does).

Example: The ant's binary number is 011 and, hence, the ant leaves a trail that looks like this: 011011011011011011. Again, there is no way to tell which way the ant is traveling without looking at the ends of the string.

What is the answer to this question? Note that the answer cannot just be an example of a binary number that works. The answer needs to include a proof that no binary number of length less than n-1 will work where n is the length of the example binary number that works. A proof by exhaustive enumeration is ok, but unpleasant. :)

Answer 1

Another approach would be to depart from binary numbers. Rephrase the question as "What is the shortest possible pattern which is directional if one is allowed to use any number of unique symbols?"

The answer here is 3 (for example A;B;C or #;&;@) since 2 does not work. So when you have a pattern like ABC is becomes clear in which direction the ant is walking.

Either ...CABCABCABCABCAB... (from left to right) Or ...CBACBACBACBACBA... (from right to left)

Now, how many Binary digits do we need to write a pattern of 3 symbols in Ternary (base-3)?

Two Binary digits allow you to write a single Quaternary (base-4) digit, which is the first base higher than or equal to 3.

Thus: (2 digits-per-symbol) multiplied by (3 symbols) = 6 Binary digits.

Answer 2

ChssPly76 has the correct answer (IMHO) in the comments above.

6 digits, example 100110.