All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 God and the Devil (Posted on 2005-02-08)
God and the Devil decide to play a game. God will start by picking an infinite sequence of moves of the form "left", "right", "up", and "down". The Devil responds by creating a finite maze with an exit and by placing God somewhere inside. God then follows His pre-selected sequence to traverse the maze. Unmakable moves are ignored; for example, if the next move is "left" and there is a wall to the left of the current square, God goes on to the next move in the sequence without moving.

If God escapes the maze in finite time, He wins. Otherwise, the Devil wins.

Assuming both agents act optimally, who will win?

(assume that the maze is formed by deleting some edges from a rectangular grid, and that it has no isolated regions; i.e., it is always possible to get to the exit from any point inside the maze)

 See The Solution Submitted by David Shin Rating: 3.6842 (19 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Method of proof? | Comment 33 of 62 |

Is this what needs to be proved?:  There exists a sequence of moves such that for evey possible finite maze, this sequence yields a solution.

If so I think I got it.

Consider the set of all mazes that fit inside a 2x2 grid.  This is definitely a finite set.  Let f(n)= the minimum length of move sequence that solve any nxn maze.

f(2)=finite.  I'm not going to find it but it is probably less than 20 because there are only a few 2x2 mazes.  (I'm considering the start and end to both be grid squares so there is no 1x1 maze.)

f(n) is just some function of n.  If this function could be explicitly found it could be shown that f(n) is finite for any n.

-Jer

 Posted by Jer on 2005-02-09 17:09:46

 Search: Search body:
Forums (0)