HMMT February, 2020

Solution:
Let $n=30$. The snake can get stuck in only 8 positions, while the total number of positions is about $n^{2} \times 4 \times 3 \times 3=36 n^{2}$. We can estimate the answer as $\frac{36 n^{2}}{8}=4050$, which is good enough for 13 points.

Let's try to compute the answer as precisely as possible. For each head position $(a, b)$ and tail orientation $c \in[0,36)$, let $x=36(n a+b)+c$ be an integer denoting the current state of the snake. Let $E_{x}$ by the expected number of moves the snake makes if it starts at state $x$. If from state $x$ the snake can transition to any of states $y_{1}, y_{2}, \ldots, y_{k}$, then add an equation of the form
$$E_{x}-\frac{1}{k} \sum_{i=1}^{k} E_{y_{i}}=1$$
Otherwise, if there are no transitions out of state $x$ then set $E_{x}=0$.

It suffices to solve a system of $36 n^{2}$ linear equations for $E_{0}, E_{1}, \ldots, E_{36 n^{2}-1}$. Then the answer will equal $E_{i}$, where $i$ corresponds to the state described in the problem statement. Naively, using Gaussian elimination would require about $\left(36 n^{2}\right)^{3} \approx 3.4 \cdot 10^{13}$ operations, which is too slow. Also, it will require too much memory to store $\left(36 n^{2}\right)^{2}$ real numbers at once.

We can use the observation that initially, the maximum difference between any two indices within the same equation is at most $\approx 72 n$, so Gaussian elimination only needs to perform approximately $\left(36 n^{2}\right) \cdot(72 n)^{2} \approx 1.5 \cdot 10^{11}$ operations. Furthermore, we'll only need to store $\approx\left(36 n^{2}\right) \cdot(72 n)$ real numbers at a time. Benjamin Qi's solution ends up finishing in less than two minutes for $n=30$ (C++ code).