Ants are smart

This problem can be solved using Markov chains. If we label the grid as follows:

then the transition matrix $M$ (which shows the probability of moving from the cell in the left column to the cell in the top row) is

(the ant has probability $\frac14$ ) of move to any of its four orthogonally adjacent cells)

To find the probabilities for where the ant might be after four moves, we just calculate $M^4$ and read off the top row. Putting this back into the original grid, we get

so the answer we want is $\left \lfloor 10^6 \cdot \frac{30}{256} \right \rfloor=\boxed{117187}$ .

---

NB: The different states (and therefore the transition matrix) could be simplified by noting the symmetry along the main diagonal of the grid. This makes the matrix smaller, but the transitions are a little less obvious.

Refer to the above image

We can see that by symmetry all the corner cells are equivalent, and the cells except the corner and center are also equivalent by symmetry.

Now let us mark the probability of the ant coming from (in n moves towards the center)

• center to center = $c_{n}$
• corner to center = $a_{n}$
• others to center = $b_{n}$

Now,

• from one corner, the ant has 4 ways to move to ther cells, that is 2 ways to other corners or 2 ways to cells marked as b.
• from one cell marked as b, the ant has 4 ways to move to ther cells, that is 2 ways to corners or 1 way to other cell marked as b or 1 way to the center cell.
• from the center, the ant has 4 ways to move to ther cells, that is 4 ways to cells marked as b.

Now if ant is supposed to finish in n moves from a cell, and now suppose it makes a move to the next cell, then from that cell it has move to the center in n - 1 moves.

Now by using Recurrence Relations we get,

• $a_{n}$ = 0.5 $a_{n-1}$ + 0.5 $b_{n-1}$
• $b_{n}$ = 0.5 $a_{n-1}$ + 0.25 $b_{n-1}$ + 0.25 $c_{n-1}$
• $c_{n}$ = $b_{n-1}$

Now solve the equations with $a_{0}$ = $b_{0}$ = 0 and $c_{0}$ = 1. We get $a_{4}$ = 0.1171875. Therefore answer is 117187.