perplexus.info :: Games : God and the Devil

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)

Submitted by David Shin

Rating: 3.6842 (19 votes)

Solution: (Hide)

Naturally, God will emerge the winner. To see this, we first prove a lemma:

Lemma: For any given finite maze, there is a finite sequence of moves that God can take to escape the maze, no matter what His starting position is.

Proof: Place an army of angels in the maze, one in each possible starting position. Construct the sequence by moving the entire army in unison until all the angels leave the maze. Note that multiple angels may occupy any one square during this sequence. God can take the resulting sequence to escape the maze from any starting position, since He will be starting where some angel started in this construction, and since that angel escaped with this sequence.

With this lemma, God's strategy is simply to perform all 1-move sequences, then all 2-move sequences, then all 3-move sequences, etc. This infinite sequence has the property that every finite sequence occurs as a subsequence of it. Then, regardless of what maze the Devil selects, God will arrive at a subsequence which allows Him to escape that particular maze no matter where God currently is within that maze.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
re(2): $10 on the Devil	selapio	2024-09-12 22:58:51
getting out of the maze	Steven Lord	2022-09-20 22:46:42
Possible problem with the latest solution	Steven Lord	2022-09-20 04:36:26
re: Puzzle Answer	K Sengupta	2022-09-19 05:36:03
No Subject	Whia1967	2022-09-19 03:44:30
Puzzle Answer	K Sengupta	2022-08-24 02:20:00
God is ominiscient!	jduval	2007-08-25 08:36:22
re(2): Reply to comment 53 & 54	Avin	2005-02-17 16:56:29
re: Reply to comment 53 & 54	Ken Haley	2005-02-17 05:19:16
re(2): Spiral sequence	Ben Gornall	2005-02-17 04:11:14
re(2): Gambling and Charity	David Shin	2005-02-16 20:56:44
re: Gambling and Charity	Hugo	2005-02-16 18:36:58
Gambling and Charity	David Shin	2005-02-16 16:47:03
Reply to comment 53 & 54	Hugo	2005-02-16 16:12:25
re(6): Extreme stupidness	Ken Haley	2005-02-16 05:41:55
re(5): No Subject	Ken Haley	2005-02-16 05:35:09
re: Erm....? I have an assertion to make	Angela	2005-02-15 18:42:33
re(5): Extreme stupidness	Angela	2005-02-15 18:38:21
re(4): No Subject	Hugo	2005-02-15 16:33:57
re(3): No Subject	Ken Haley	2005-02-15 05:12:23
re(2): No Subject	Hugo	2005-02-14 09:48:07
re: No Subject	Ken Haley	2005-02-14 03:53:59
No Subject	Hugo	2005-02-13 15:21:49
re: Waaw, all those comments, just for $ 20.	Ken Haley	2005-02-12 17:45:46
Waaw, all those comments, just for $ 20.	Hugo	2005-02-12 17:08:52
full solution - god would win	ronen	2005-02-12 10:46:06
re(3): $ 20 on the Devil	Dustin	2005-02-12 05:54:34
re(2): $ 20 on the Devil	Jrdn	2005-02-12 05:33:29
re: $ 20 on the Devil	Ken Haley	2005-02-12 05:21:11
re: Careless wagering or a philosophical paradox!	Jack	2005-02-12 03:07:53
$ 20 on the Devil	Hugo	2005-02-11 20:19:11
Erm....?	Joe	2005-02-11 12:59:52
re(3): Clarification of infinite sequence	David Shin	2005-02-10 04:17:57
re(3): Please don't over-react.	Dustin	2005-02-09 22:38:13
re(2): Clarification of infinite sequence	Spoiler	2005-02-09 21:27:19
Method of proof?	Jer	2005-02-09 17:09:46
re: Spiral sequence	David Shin	2005-02-09 14:19:48
Iterative Deepening?	Sam	2005-02-09 09:02:51
Spiral sequence	Ben Gornall	2005-02-09 09:00:26
re: Clarification of infinite sequence	David Shin	2005-02-09 06:33:21
re: $10 on the Devil	Graham	2005-02-09 05:17:07
re: No Subject (and solution!)	Ken Haley	2005-02-09 05:12:42
$10 on the Devil	Farthing	2005-02-09 04:42:22
Infinity	Michael Cottle	2005-02-09 04:15:20
The answer is in the Question	randy	2005-02-09 03:46:44
Easy Solution	randy	2005-02-09 03:43:02
Would this work?	Tristan	2005-02-09 03:20:01
Clarification of infinite sequence	Farthing	2005-02-09 02:22:10
re(5): Solution attempt - Jack was right	David Shin	2005-02-09 02:21:42
re(2): Regarding randomness	David Shin	2005-02-09 02:20:45
re: Regarding randomness	Charlie	2005-02-09 02:11:30
re(4): Solution attempt - Jack was right	Dustin	2005-02-09 01:54:34
re(3): Solution attempt - Jack was right	SteveH	2005-02-09 01:47:01
re(2): Solution attempt	Jack	2005-02-09 01:27:42
re: Solution attempt	SteveH	2005-02-09 01:02:53
Solution attempt	Jack	2005-02-09 00:37:25
Regarding randomness	David Shin	2005-02-09 00:33:24
re(2): No Subject	Dustin	2005-02-09 00:13:52
re: No Subject	Gamer	2005-02-08 23:49:04
No Subject	SteveH	2005-02-08 23:12:46
Explanation	Gamer	2005-02-08 22:58:58
re(4): boiling it down - Not so simple	John	2005-02-08 22:43:15
re(3): boiling it down - Not so simple	David Shin	2005-02-08 22:40:54
re(2): boiling it down - Not so simple	John	2005-02-08 22:38:29
re(2): boiling it down - Not so simple	Hugo	2005-02-08 22:25:54
re: boiling it down - Not so simple	David Shin	2005-02-08 22:19:13
boiling it down	John	2005-02-08 22:07:47
My idea, for what it's worth	Hugo	2005-02-08 20:14:46

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info