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.
Answer
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.
No comments:
Post a Comment