David Wilson wrote:
Suppose there is a man standing on a random square of a random polyomino. At regular intervals, we may instruct the man to move in one of the directions north, south, east or west. If the adjacent square in the specified direction is part of the polyomino, the man will move to that square, otherwise he will stay on his current square.
Is there a single infinite sequence of directions we can give to the man that guarantees he will eventually visit every square of the polyomino, regardless of its shape or size or of the man's initial square?
Here's another solution: Generate a random string of instructions. With probability 1, it will have the property you desire, since it will contain every finite sequence of instructions. Of course, randomness plays no essential role here, as other people's solutions to David's question have made clear. This topic provides me with a good opportunity to raise a question that has been on my mind for a year or two: Can anyone find an explicit construction of an infinite sequence S of 0's and 1's with the property that for any finite bit-string s, the relative frequency with which s occurs in the first N bits of S converges to (1/2)^(length of s) with error that falls like (log N)/N? Note that the Champernowne sequence A030190 has error 1/(log N). An explicit construction of Alon, Kohayakawa, Mauduit, Moreira and R\"odl allows one to achieve error 1/N^c for any exponent c greater than 2/3 (which beats what one would get from a random sequence of bits). Jim Propp