HMMT-Feb 2010 guts, Problem 19

A 5-dimensional ant starts at one vertex of a 5-dimensional hypercube of side length 1. A move is when the ant travels from one vertex to another vertex at a distance of $\sqrt{2}$ away. How many ways can the ant make 5 moves and end up on the same vertex it started at?

Solution: We let the cube lie in $\mathbb{R}^{5}$ with each corner with coordinates 1 or 0 . Assume the ant starts at $(0,0,0,0,0)$. Every move the ant adds or subtracts 1 to two of the places. Note that this means the ant can only land on a vertex with the sum of its coordinates an even number. Every move the ant has $\left(\begin{array}{l}5 \\ 2\end{array}\right)=10$ choices. From any vertex there are 10 two-move sequences that put the ant at the same vertex it started at. There are 6 two-move sequences to move from one vertex to a different, chosen vertex. If your chosen vertex differs from your current vertex by 2 of the 5 coordinates, your first move corrects for one of these two. There are 2 ways to choose which coordinate to correct for on the first move, and there are 3 ways to choose the second coordinate you change, yielding 6 sequences. If your chosen vertex differs from your current vertex by 4 of the 5 coordinates, each move corrects for two of these four. This yields $\left(\begin{array}{l}4 \\ 2\end{array}\right)=6$ sequences. Finally, there are 60 three-move sequences that put the ant at the same vertex it started at. There are 10 ways to choose the first move, and there are 6 ways to make two moves to return to your original position. The motion of the ant can be split into two cases. Case 1: After the 3rd move the ant is on the vertex it started at. There are $(60)(10)=600$ different possible paths. Case 2: After the third move the ant is on a vertex different from the one it started on. There are $\left(10^{3}-60\right)(6)=(940)(6)=5640$ different possible paths. So there are 6240 total possible paths. $\fbox{6240}$.

Answer: 6240