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

Home > Games
God and the Devil (Posted on 2005-02-08) Difficulty: 4 of 5
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.)
re(2): No Subject | Comment 48 of 67 |
(In reply to re: No Subject by Ken Haley)

Thanks for all the work Ken.

I did read your first posting, wrote down an answer to part one, but part two was much more difficult and it being a sunday, I gave up on it- Sorry. I thought the thing I posted was maybe a better point, so I posted that.

Now replying to your numbered list: In general, I am sold (for 90%) to the idea af God getting out in a finite time. There is however one problem to be solved, before I'll send in my $20. I tried to do it myself, but I am not absolutely sure that it works.

Here's my problem:
I agree up till point 6 and get stuck at 7 1/2, which is also repeated at 15.
Just to make sure that I correctly understand you: S1 is the sequence to the exit from P1 (the first starting point), S2 is the sequence to the exit from P2. P2 is found after S1 being executed from a certain point that was not solved by S1. You now create a new S(long), being S1:S2, this is: do S1, then do S2. (If you answer- which I would appreciate very much - please mention it if I didn't correctly understood you)
If the above is correct: Then what about this: The Devil picks a starting point for God, such that after doing S1, he ends up at P1. The rest of the sequences are now not guaranteed to find the exit.
I tried to solve this by extending your list to be all combinations of all S(n), but it would have to be proven that at a given moment, God is in a place where the right sequence starts. Although the probability that this happens is high, it isn't 1.

Once the above is solved, I agree that God wins.


  Posted by Hugo on 2005-02-14 09:48:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information