42
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ Surely less than 87.5% $\endgroup$
    – manshu
    Commented Feb 29, 2016 at 21:27
  • $\begingroup$ 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? $\endgroup$
    – PopularIsn'tRight
    Commented Feb 29, 2016 at 22:03
  • 2
    $\begingroup$ @Bachrach44 the king can see which squares are destroyed, they are known in advance. $\endgroup$
    – Mike Earnest
    Commented Feb 29, 2016 at 22:21
  • $\begingroup$ 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? $\endgroup$
    – Danikov
    Commented Mar 2, 2016 at 10:29
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mike Earnest
    Commented Mar 2, 2016 at 16:34

1 Answer 1

Reset to default
57
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ This is the most simple and creative solution. $\endgroup$
    – Paul Evans
    Commented Feb 29, 2016 at 23:25
  • 2
    $\begingroup$ @Bachrach44 No, their diagonal moves are in the same direction (NW/SE) so they can't cross like that. $\endgroup$
    – f''
    Commented Mar 1, 2016 at 4:32
  • 3
    $\begingroup$ @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$. $\endgroup$
    – Fimpellizzeri
    Commented Mar 1, 2016 at 4:41
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dave McClelland
    Commented Mar 1, 2016 at 14:49
  • 3
    $\begingroup$ @DaveMcClelland The L->R king can only use destroyed squares. If that diagonal is intact, he can't cross it. $\endgroup$
    – JonTheMon
    Commented Mar 1, 2016 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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