After $10$ minutes, what is the probability that the fly is back on $A$? A fly is walking on a hexagon, at random. The fly starts at vertex $A$. After a minute, it moves to one of the two adjacent vertices. After $10$ minutes, what is the probability that the fly in back on $A$?
 A: Hint: Label the vertices as $0,1,2,3,\ldots ,5$ with $A$ being $0$. Consider addition modulo $6$. At each minute, we either add or subtract $1$. For example, one option after $10$ minutes would be $+1, +1, +1, -1, +1, +1, +1, -1, +1, +1$ which sum to $6 \equiv 0 \pmod 6$, so this option gets us back to $A$.


*

*How many routes are possible in total?

*In order to get back to $A$, we must either sum to $0$ - in which case, the number of $+1$'s is equal to the number of $-1$'s, or we must sum to $\pm 6$. Can you count the possible solutions here?

A: Alternatively, you could use a Markov Chain.  
Find $[\mathbf P^{10}]_{1,1}$; the first column and row entry of:
$$\mathbf P^{10} = \dfrac 1{2^{10}}\begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 1 
\\ 1 & 0 & 1 & 0 & 0 & 0
\\ 0 & 1 & 0 & 1 & 0 & 0
\\ 0 & 0 & 1 & 0 & 1 & 0
\\ 0 & 0 & 0 & 1 & 0 & 1
\\ 1 & 0 & 0 & 0 & 1 & 0
\end{bmatrix}^{10}$$
A: My method: Make a pascal triangle.
Each time it breaks represents the fly going left or going right. The number at any point is how many possibilities that the fly is there after that many minutes (1 row is 1 min) 
On the 11th row (after 10 minutes, with minute 0 being row 1), add up the middle term, the term 3 to the left of it, and 3 to the right of it (the reason you do 3 rather than 6 is that only the even numbers are shown in the 11th row, so 3 over is 6 more or less. After 10 steps, the only possible sum is even)
Edit: read the comments for further elaboration, with some possibly helpful pictures
