A frog jumps around on the grid points in the plane, from one grid point to another. The frog starts at the point $(0, 0)$. Then it makes, successively, a jump of one step horizontally, a jump of $2$ steps vertically, a jump of $3$ steps horizontally, a jump of $4$ steps vertically, et cetera. Determine all $n > 0$ such that the frog can be back in $(0, 0)$ after $n$ jumps.
Problem
Source: Dutch NMO 2021 p3
Tags: combinatorics, lattice points
14.01.2022 15:48
Taking only the vertical jumps into account, we need to know when it is possible that $\pm 2 \pm 4 \pm \dots \pm 2 \left \lfloor \frac{n}{2} \right \rfloor = 0$ which is equivalent to $\pm 1 \pm 2 \pm \dots \pm \left \lfloor \frac{n}{2} \right \rfloor = 0$. Since flipping a sign on the LHS would either add or subtract an even integer, $1 + 2 + \dots + \left \lfloor \frac{n}{2} \right \rfloor = \frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor \left (\left \lfloor \frac{n}{2} \right \rfloor + 1\right)$ must be even. Thus, $\left \lfloor \frac{n}{2} \right \rfloor$ must be either $0 \pmod{4}$ or $3 \pmod{4}$ and $n$ must be $0, 1, 6, 7 \pmod{8}$. Taking only the horizontal jumps into account, we need to know when it is possible that $\pm 1 \pm 3 \pm 5 \pm \dots \pm \left (2 \left \lceil \frac{n}{2} \right \rceil - 1 \right) = 0$. Since flipping one of the signs on the LHS would either add or subtract an even integer, $1 + 3 + 5 + \dots + \left (2 \left \lceil \frac{n}{2} \right \rceil - 1 \right)$ must be even, which means $\left \lceil \frac{n}{2} \right \rceil^2$ must be even. Thus, $n$ must be $0 \pmod{4}$ or $3 \pmod{4}$. From both parts, we see that $n$ must be either $0$ or $7 \pmod{8}$. If $n = 8k$ for some positive integer $k$, then the frog can go right, up, left, down, left, down, right, up in this order $k$ times, where it would be back to $(0,0)$ at the end. If $n = 8k+7$ for some nonnegative integer $k$, then the frog can go right, up, left, up, left, down, right in this order, where it returns to $(0,0)$, and then it can go right, up, left, down, left, down, right, up in this order $k$ times, , where it would also be back to $(0,0)$ at the end. Therefore, the answer is all integers $n>0$ which are $\boxed{0 \pmod{8} \text{ or } 7 \pmod{8}}$.