A long worm crawls into a cosmetic veterinary surgery, complaining of a problem with 1's.

A worm can be thought of as a string of 0's and 1's and the most beautiful worm is 00000 ... 0. The worm is a sequence of segments and there is a 0 or a 1 on each segment. The procedure for removing 1's is complicated. If there is a 1 at the right hand end (where the tail is), then the surgeon can remove this 1 (and the segment it lies on) and place a new segment with 0 or a 1 at the left hand end (where the head is).

If however there is a 0 at the right hand end then the surgeon can remove it, but he has no control over what appears on the new segment at the left hand end. Indeed, the surgeon has to operate under the assumption that there is an adversary making a choice of what to replace a 0 by.

The adversary would like the operation to continue indefinitely. The surgeon claims a 100% success rate. Do you believe him?

 

alanATrandomDOTmathDOTcmuDOTedu