12
$\begingroup$

Professor Erasmus told me that today he has proved another fascinating theorem about strings made of 0s and 1s. He takes an arbitrary such string and repeats the following step on it:

  • if the leftmost symbol is 1, Erasmus removes the three leftmost symbols and attaches 11 at the right end
  • if the leftmost symbol is 0, Erasmus removes the three leftmost symbols and attaches 0010 at the right end

If the procedure ever reaches a string of length at most 2, it halts.

Example 1: Starting from 1001, this procedure yields 111, then 11, and halts.

Example 2: Starting from 01010, this procedure yields 100010, then 01011, then 110010, then again 01011, then again 110010; etc. There is a loop of length two.

Professor Erasmus has proved that independently of the starting string, the procedure will eventually halt or enter a loop of length at most 25.

Has the professor once again made one of his well-known mathematical blunders, or does his claimed theorem indeed hold true?

$\endgroup$
  • $\begingroup$ What happens if you have a string of length 1 or 2? Do you just remove all existing symbols? $\endgroup$ – Zandar Sep 17 '15 at 18:34
  • 1
    $\begingroup$ @Zandar 15: then the procedure stops $\endgroup$ – Gamow Sep 17 '15 at 18:34
  • $\begingroup$ does the string have to contain atleast one 0 and one 1? $\endgroup$ – SirParselot Sep 17 '15 at 18:41
  • 2
    $\begingroup$ Each step switches the parity of the number of characters in the string, so every loop must have an even number of steps. So if Erasmus is correct that every loop has at most 25 steps, then if fact every loop has at most 24 steps :) $\endgroup$ – Julian Rosen Sep 17 '15 at 19:01
  • 1
    $\begingroup$ It seems that it would be more appropriate for the professor to be called Post. $\endgroup$ – Peter Taylor Sep 17 '15 at 19:31
23
$\begingroup$

Professor Erasmus

has made a blunder.

If the leftmost six numbers are $110\,010$, then the first step removes $110$ from the left and adds $11$ on the right, and the next step removes $010$ from the left and adds $0010$ on the right. The result is that after two steps, $110\,010$ has been removed from the left and added on the right.

Similarly, if the leftmost twelve numbers are $001\,000\,101\,111$, the net result is that after four steps these numbers have been removed from the left and added on the right.

Call the strings $S_1=110\,010$ and $S_2=001\,000\,101\,111$. Suppose we start with the string $$S_1S_1\ldots S_1 S_2,$$ with $n$ copies of $S_1$ followed by a copy of $S_2$. After two steps, we get $S_1\ldots S_1 S_2 S_1$. After two more steps, $S_1 \ldots S_1 S_2 S_1 S_1$, and so on. So after $2n$ steps, we have reached $S_2 S_1 \ldots S_1$. Four more steps takes us back to the original $S_1\ldots S_1 S_2$.

The original string is the only string in the cycle whose rightmost five digits are $01111$, so this is a cycle of length $2n+4$. We can choose $n$ arbitrarily, so as long as $n\geq 11$, we get a cycle of length greater than 25.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.