There’s a pawn starting in the center of this game board. At each move, it can advance randomly towards any of the adjacent squares sharing a common side with equal chance. What’s the probability of landing on the crossed spot on the ninth move?
This question is from a Swiss math contest, the FSJM, in 2008. The original questions are only available in French
I think the answer is
$\frac{935}{13122}$
Proof
After an even number of moves the pawn must be on one of the shaded squares
Due to the symmetry of the problem the probability of being on any of the four surrounding squares is equal so this simplifies the calculation a bit.
If the pawn is on the centre square at move $n$ then it has probability $\frac{1}{6}$ of being on each surrounding square at move $n+2$ and probability of $\frac{1}{3}$ of being back in the centre.
If the pawn is on a surrounding square at move $n$ it has probability of $\frac{1}{9}$ of being at the centre at move $n+2$. This means we generate the following probabilities after $2n$ moves:
2 moves: $p(centre) = \frac{1}{3}$, $p(surround) = \frac{1}{6}$ each
4 moves: $p(centre) = \frac{1}{9} + \frac{4}{54} = \frac{10}{54}$, $p(surround) = \frac{11}{54}$ each
6 moves: $p(centre) = \frac{10}{162} + \frac{44}{486} = \frac{74}{486}$, $p(surround) = \frac{103}{486}$ each
8 moves: $p(centre) = \frac{74}{1458} + \frac{412}{4374} = \frac{634}{4374}$, $p(surround) = \frac{935}{4374}$
which means it has probability of $\frac{935}{4374}$ for being in the top-left shaded square after 8 moves so $p=\frac{935}{13122}$ of being on the X after 9 moves
For simplification, I will represent squares with numbers 1-25 (With 1, 3, 5, 8, 11, 15, 18, 21, 23, and 25 unused) 2 is the goal square, and 13 is the starting point.
We can do this by working backwards, using the pretense that on each consecutive turn the pawn will end up on a "checkerboard" alternating from the previous turn:
Starting from 1 move to go,
On square 7 there is a 1/3 chance to reach the goal, on all other squares there is a 0% chance
From 2 moves to go,
On squares 2 and 6 there is a 100% chance to reach square 7, and on square 12 there is a 1/3 chance to reach square 7, (so effectively 1/9 total), on all else 0% chance
From 3 moves to go,
On square 7, there is a 2/3 chance of landing on a 1/3 square, and a 1/3 chance of landing on a 1/9 square. This averages out to a chance of 7/27. On Square 17 there is a 1/3 chance to land on a 1/9 square, so there is a chance of 1/27, and on square 13 there is a 1/2 chance to land on a 1/9 square, so there is a chance of 1/18.
From 4 moves to go,
On squares 2 and 6, you will always end on the 7/9 square. On squares 16 and 22, you will always end on the 1/27 square, on square 12, you will have an equal chance to land on the 7/9, 1/18, and 1/27 squares, so this averages to 47/162, lastly on square 14 you have a 1/3 chance to land on a 1/18 square, giving you a 1/54 chance.
From 5 moves to go,
On squares 9 and 19, there is a 1/3 chance to land on the 1/54 square, giving a 1/162 chance, on square 13 you take the average of squares 12 and 14 to get a 25/162 chance...
The more I'm doing this the more I'm realizing the ugly math here, and I'm realizing instead:
I can run a script starting with all squares occupied with 0 except the goal square occupied by 1, and run a procedure to change each square to the average of each adjacent square, run this 9 times, and return the value in the start square. I will get back with a solution after running this
Update, using my script I got a solution of:
7.125438195397042%
This can be solved with linear algebra as follows:
1. Create an adjacency matrix.
2. For each row in the matrix, scale all of the values so that the row sums to 1.
3. At this point, the value at row i, column j will be the probability that a single random step starting in cell i will land you in cell j.
4. Raise the matrix to the 9th power. If you're doing this by hand, you can do it in only 4 matrix multiplications if you're clever enough.
5. At this point, the value at row i, column j will be the probability that exactly 9 random steps starting in cell i will land you in cell j.
6. The row and column corresponding to the puzzle's specified starting and ending square will now contain the desired probability.
Here's a demonstration of this approach in Haskell (it requires thematrixpackage):import Data.Matrix adjacencies = [ [0,0,0,1,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,1,0,0,0,0,0,0,0,0,0,0], [0,0,0,1,0,0,0,0,0,0,0,0,0,0,0], [1,0,1,0,0,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,0,1,0,0,1,0,0,0,0,0,0], [0,0,0,0,1,0,0,0,0,0,0,0,0,0,0], [0,0,0,1,0,0,0,1,0,0,1,0,0,0,0], [0,0,0,0,0,0,1,0,1,0,0,0,0,0,0], [0,0,0,0,1,0,0,1,0,0,0,1,0,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,0,1,0,0,1,0,0,0,1,0], [0,0,0,0,0,0,0,0,1,0,0,0,1,0,1], [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]] normalize :: [Rational] -> [Rational] normalize xs = map (\x -> x / s) xs where s = sum xs stepProbabilities = fromLists (map normalize adjacencies) walkProbabilities = stepProbabilities ^ 9 -- Result: 935 % 13122 main = print $ getElem 8 1 walkProbabilities
One thing to know about FSJM problems is that they are to be solved with just pencil and paper, without a calculator.
I concur with hexomino in his answer and his method. I used a different method to compute the result. It is the "Markov chain matrix multiplication" method others mentioned. I initially thought it would be much simpler or faster to compute, but it the end it is not significantly different. I leave it here, it might be of interest to some.
Like in hexomino's answer I consider the probability of being in the center versus being in one of the 4 surrounding "even" squares after 2, 4 and 8 moves.
When you start in the center and do 2 moves, you end up in the center 1 out of 3 times. Or 3 in 9. And when you start in a surrounding square and do 2 moves, you end up in the center only 1 out of 9 times.
You can write the transition matrix for 2 moves between these 2 positions. The first row/column is the center, the 2nd row/column is any of the four surrounding squares. $$\frac{1}{9}\begin{pmatrix} 3 & 1 \\ 6 & 8 \\ \end{pmatrix}$$ If you square this matrix 2 times, you get the transition matrix for 8 moves.
$$(\frac{1}{9}\begin{pmatrix} 3 & 1 \\ 6 & 8 \\ \end{pmatrix})^2 = \frac{1}{81}\begin{pmatrix} 15 & 11 \\ 66 & 70 \\ \end{pmatrix}$$ $$(\frac{1}{81}\begin{pmatrix} 15 & 11 \\ 66 & 70 \\ \end{pmatrix})^2 = \frac{1}{81^2}\begin{pmatrix} 225+726 & 165+770 \\ 990+4620 & 726+4900 \\ \end{pmatrix} = \frac{1}{6561}\begin{pmatrix} 951 & 935 \\ 5610 & 5626 \\ \end{pmatrix}$$
(the matrix is complete here, but you actually need to compute only the bottom left term).
This matrix tells you that if you start from the center (1st column), the probability to end in a "corner" (bottom row) after 8 moves is $$\frac{5610}{6561} = \frac{1870}{2187}$$
To end up on the big cross after one more move, you have to actually be in the top-left corner, which happens 1 out of 4 times, and then move up, which happens 1 out of 3 times. Multiplying these probabilities you get the answer:
P(on X after 9 moves) $$= \frac{1870}{2187} \times \frac{1}{4} \times \frac{1}{3} = \frac{935}{13122}$$
