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. :)