Problem 1276

From $(0,0,0,0)$ we have to go to $( \pm 1, \pm 1, \pm 1, \pm 1)$, and from $(1,1,1,1)$ (or any of the other similar points), we have to go to $(0,0,0,0)$ or $(-1,1,1,1)$ and its cyclic shifts. If $a_{i}$ is the number of ways to go from $(1,1,1,1)$ to point of the form $( \pm 1, \pm 1, \pm 1, \pm 1)$ in $i$ steps, then we need to find $\nu_{2}\left(16 a_{2018}\right)$. To find a recurrence relation for $a_{i}$, note that to get to some point in $( \pm 1, \pm 1, \pm 1, \pm 1)$, we must either come from a previous point of the form $( \pm 1, \pm 1, \pm 1, \pm 1)$ or the point $(0,0,0,0)$. In order to go to one point of the form $( \pm 1, \pm 1, \pm 1, \pm 1)$ through $(0,0,0,0)$ from the point $( \pm 1, \pm 1, \pm 1, \pm 1)$, we have one way of going to the origin and 16 ways to pick which point we go to after the origin. Additionally, if the previous point we visit is another point of the form $( \pm 1, \pm 1, \pm 1, \pm 1)$ then we have 4 possible directions to go in. Therefore the recurrence relation for $a_{i}$ is $a_{i}=4 a_{i-1}+16 a_{i-2}$. Solving the linear recurrence yields $a_{i}=\frac{1}{\sqrt{5}}(2+2 \sqrt{5})^{i}-\frac{1}{\sqrt{5}}(2-2 \sqrt{5})^{i}=4^{i} F_{i+1}$ so it suffices to find $\nu_{2}\left(F_{2019}\right)$. We have $F_{n} \equiv 0,1,1,2,3,1(\bmod 4)$ for $n \equiv 0,1,2,3,4,5(\bmod 6)$, so $\nu_{2}\left(F_{2019}\right)=1$, and the answer is $4+2 \cdot 2018+1=4041$.