# Crippled King Crossing a Canyon

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

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.

• Surely less than 87.5% – manshu Feb 29 '16 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? – PopularIsn'tRight Feb 29 '16 at 22:03
• @Bachrach44 the king can see which squares are destroyed, they are known in advance. – Mike Earnest Feb 29 '16 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 '16 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 '16 at 16:34

• @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 '16 at 4:41
• 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 '16 at 14:49