[math-fun] Path Question
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?
On Saturday 14 April 2007 12:09, 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?
Sure. There are only countably many (polyomino,position) pairs. Enumerate them; find a finite move-sequence that does the job for the first, then one that does the job for the second given that we've already done the first set of moves, etc. -- g
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?
Sure: start with direction D = empty string, and iterate over all possible starting configurations C the operation "Append to D whatever moves would be needed to win, starting from configuration C and performing the moves in D so far first." I think the exactly analogous "set of instructions for getting out of any maze" shows up in _Godel, Escher, Bach_. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
participants (3)
-
David Wilson -
Gareth McCaughan -
Michael Kleber