Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A chess king has been injured in battle against an evil wizard, and can no longer move northeast or southwest.

enter image description here

This king is on the North rim of a canyon, and must flee to safety on the South rim. The only way to cross is a bridge, which is a shaped like a standard chessboard.

However, as the king is about to cross, the evil wizard casts a fire spell on all 64 squares of the bridge. Each square is destroyed with a probability of 50%, independently of the others.

What is the probability that the king can cross the canyon via the undestroyed squares?

To be clear, the king is allowed to start on any undestroyed square on the top row of the chessboard, and succeeds as long as he reaches any undestroyed square on the bottom row.

enter image description here

share|improve this question
    
Surely less than 87.5% – manshu Feb 29 at 21:27
    
What happens if the king moves into a destroyed square? Does he die or does he just bounce and get to move again? Is there a way to know which squares have been destroyed in advance? – Bachrach44 Feb 29 at 22:03
2  
@Bachrach44 the king can see which squares are destroyed, they are known in advance. – Mike Earnest Feb 29 at 22:21
    
When you say the squares are destroyed with a 50% chance, is that a guaranteed 32 squares are destroyed, or is there a 1 in 2^64 chance of all or none of them being destroyed? – Danikov Mar 2 at 10:29
    
@Danikov I meant the latter; there are 64 independent coin flips which determine which squares are destroyed, so all being destroyed is possible. However, you will get the same answer assuming that exactly 32 squares are always destroyed. – Mike Earnest Mar 2 at 16:34
up vote 49 down vote accepted

Exactly 50%.

Explanation:

Consider another injured king (also can't move NE or SW) who is trying to get from the left side to the right side, but only travels on destroyed squares. By the Hex Theorem, the second king can cross if and only if first king can't. Because the situation is symmetrical (every square has a 50% chance of being destroyed), each king can cross exactly half of the time.

share|improve this answer
1  
This is the most simple and creative solution. – Paul Evans Feb 29 at 23:25
2  
@Bachrach44 No, their diagonal moves are in the same direction (NW/SE) so they can't cross like that. – f'' Mar 1 at 4:32
3  
@Bachrach44 Here's another way to see this. First, observe that each board configuration (of destroyed and whole squares) is equally likely. Second, let $K$ be the set of board configurations that allow the king to cross, and $W$ be the set of configurations that don't. We show that $K$ and $W$ have the same number elements, so the king's likelihood of crossing is $50$%. To that end, simply note that if one rotates the board, reflects (flips) it, then applies an inversion (destroyed squares become whole squares, and vice versa), you have a one-to-one correspondence between $K$ and $W$. – Fimpellizieri Mar 1 at 4:41
2  
I don't believe this is correct: the second king can cross if and only if first king can't. What about a board where the entire diagonal from top left to bottom right remains (along with some other, ignored squares). Both kings can successfully cross. – Dave McClelland Mar 1 at 14:49
3  
@DaveMcClelland The L->R king can only use destroyed squares. If that diagonal is intact, he can't cross it. – JonTheMon Mar 1 at 15:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.