BdMO Online Forum

Let every unit square is a node and the path is edge. Then I had tried to figure out that how many paths we can create by 4 edges and how many of them go through the middle node. I tried some experiments but I can't figure this out.

Observation:
It is clear that we can get to the centre only from an edge. We can not get to the centre from a corner. Let's say we are not allowed to go into the centre square. Then in which move we can go to an edge or corner? It is clear we can go to the edge by only an odd number of moves regardless of whether we go into the centre or not. So we can reach the corner squares by only an even number of moves. So we can get to the middle square by only even number of moves. This divides our solution into $2$ cases, when Caitlin reaches the middle square at the $2nd$ or $4th$ move.
Solution:
Let us denote the $3\times 3$ square grid by numbers. It will help us to explain things better. Just like in the picture; So we need start from $1$ and we need to reach $5$.
Case1:
We reach $5$ in the $2nd$ move.
We can reach $5$ by only $2$ ways,

• $1\to 2\to 5$
  $1\to 4\to 5$

We still have $2$ moves left.
From $5$ we can go to $4$ other edges. And from those $4$ edges, we can go to the $2$ other corners. (Note that we can't go back to $5$ as we can only enter $5$ once).
So total ways Caitlin can do $4$ moves and get into $5$ in the $2nd$ move is $2\times4\times2=16$

Case:2
Getting into $5$ in the $4th$ move.
This is the same as saying how many ways we can reach an edge using $3$ moves. Actually, with $3$ moves, we will always reach an edge. But we need to avoid using the centre. Let us see how Caitlin can reach the square $6$. There is only one way, $1\to 2\to 3 \to 6$
Now how can Caitlin reach $2$ in $3$ moves?
There are actually $3$ ways

• $1\to 2\to3\to2$
  $1\to 2\to 1\to 2$
  $1\to 4\to1\to 2$

So we can reach either $2$ or $6$ in $4$ ways. Similarly, we can move to $4,8$ in $4$ ways. So we can reach an edge in $3$ moves in $8$ ways. The last move is fixed which is to go to $5$.
So total number of favourable outcome $=16+8=24$

Now to find the total number of outcomes.
$2$ cases,
Case:1
We go in $5$ in the $2nd$ move,
Then the number of $4$ moves is $=2\times 1\times 4\times 3=24$
Case:2
We do not go in $5$ in the $2nd$ move,
Then the number of $4$ moves is $=2\times 2\times 2\times 3=24$
So total number of moves $=48$
So probability $=\frac{24}{48}=\frac{1}{2}$