US-TST 2019 Problem 3

A snake of length $k$ is an animal which occupies an ordered $k$-tuple $\left(s_{1}, \ldots, s_{k}\right)$ of cells in an $n \times n$ grid of square unit cells. These cells must be pairwise distinct, and $s_{i}$ and $s_{i+1}$ must share a side for $i=1, \ldots, k-1$. If the snake is currently occupying $\left(s_{1}, \ldots, s_{k}\right)$ and $s$ is an unoccupied cell sharing a side with $s_{1}$, the snake can move to occupy ( $s, s_{1}, \ldots, s_{k-1}$ ) instead. The snake has turned around if it occupied $\left(s_{1}, s_{2}, \ldots, s_{k}\right)$ at the beginning, but after a finite number of moves occupies $\left(s_{k}, s_{k-1}, \ldots, s_{1}\right)$ instead. Determine whether there exists an integer $n>1$ such that one can place some snake of length at least $0.9 n^{2}$ in an $n \times n$ grid which can turn around.