A dangerous game .....
A pawn, starting on the lower left corner square of a standard 8 by 8 chessboard, is to be moved one square at a time to the upper right corner square. The only permitted moves are one square up or one square to the right.
Four squares, (other than the starting and finishing squares), chosen at random, are rigged so that if the pawn is moved to one of these squares it vaporizes, never to be seen again. The probability that the pawn reaches the upper right corner square intact is b a , where a and b are positive coprime integers. Find b − a .
The answer is 345969.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Note first that any path from the starting to finishing squares will consist of 1 4 moves, ( 7 up and 7 to the right).
There are 6 2 squares on the chessboard other than the starting and finishing squares. Since 4 of these squares are unsafe, the probability that the pawn is still intact after the first move is 6 2 5 8 .
Given that the pawn survives the first move, there are 6 1 squares left, 5 7 of which are safe. Thus the probability that the pawn survives the second move is 6 1 5 7 .
This process continues such that, given that the pawn is safe after k moves, the probability that it survives the ( k + 1 ) st move is 6 2 − k 5 8 − k .
Now if the pawn is safe after 1 3 moves then the next move is guaranteed to be safe since it will be to the finishing square. This means the desired probability is the product
∏ k = 0 1 2 6 2 − k 5 8 − k = ( 4 6 2 ) ( 4 4 9 ) = 5 5 7 8 4 5 2 1 1 8 7 6 .
This makes a = 2 1 1 8 7 6 , b = 5 5 7 8 4 5 and b − a = 3 4 5 9 6 9 .
You have to be careful. Not all squares are treated the same. For example, if 2 of the rigged squares are ( 1 , 2 ) and ( 2 , 1 ) , then the pawn will never reach the upper right corner.
I suspect that due to the dependency, the approach is not so simple,
Log in to reply
You're right, not all squares are equal in terms of the number of paths that contain them. Each of the two you mention are on half the potential paths while ( 8 , 1 ) is only on 1 . But all 6 2 squares being dealt with have an equal chance of being rigged, which is why I took the 'one move at a time' approach in my posted solution.
I did have some reservations about my solution, but I thought that the question was intriguing enough that it was worth the risk in posting it and seeing what others had to say, even if it turns out I am wrong. Perhaps I could have posted it for discussion, but I felt confident enough to go ahead and post it as a question. As of yet no one has got it but there have only been two attempts, so ....
Someone may end up doing a computer simulation, which is always welcome with problems like these. Maybe I should have tagged it to computer science as well as combinatorics.
Because of that observation, I tried to solve the problem using programming, and the answer turned out to be 3909 (prob. of surviving = 5 5 7 8 4 5 5 5 3 9 3 6 ). I think the proposed answer discards that observation, which makes it incorrect.
To demonstrate the point, let's consider a 3x3 version of the problem with 2 rigged squares. The number of possibilities is ( 2 7 ) = 2 1 . The only bad configurations are { ( 1 , 2 ) , ( 2 , 1 ) } and { ( 2 , 3 ) , ( 3 , 2 ) } , so the probability of reaching the opposite corner is 2 1 2 1 − 2 = 2 1 1 9 . On the other hand, the proposed solution would tell us, if I understand the approach correctly, that this probability is ( 2 7 ) ( 2 4 ) = 7 2 = 2 1 1 9 . Even worse, if the number of rigged square is only 1, then it would give something other than 1 1 , while this is the answer because the pawn can always avoid any chosen square.
Additionally, I noticed that it does not matter whether you are allowed to move to the left or down, since with only four squares prohibited, no configuration exists where moves to the left or downward are necessary. With five, however, such configurations exist.
Log in to reply
You've done an interesting analysis, but I think you're answering a different interpretation of the question than I intended, which was that the pawn doesn't 'know' which squares are rigged. So even if there are potential safe routes from start to finish that doesn't mean that the pawn, moving randomly either right or upward, will end up taking any of those routes. So it could get vaporized even if there are potential safe routes.
There are 62 squares that can be rigged. For any path the pawn takes, there are 13 squares of the path that could be rigged. This means there are always 6 4 − 1 3 = 4 9 "safe" squares. Therefore, the probability that the pawn survives is simply ( 4 6 2 ) ( 4 4 9 ) = 5 5 7 8 4 5 2 1 1 8 7 6 . The answer is 5 5 7 8 4 5 − 2 1 1 8 7 6 = 3 4 5 9 6 9 .