Dutch Mathematical Olympiad

(a) When the frog has finished $n$ jumps, it has made $1+2+3+\cdots +n=\frac{1}{2}n(n+1)$ steps in total. To get back at $0$, the frog must make the same number of steps to the left and the right. Thus, the total number of steps must be even. This means that $\frac{1}{2}n(n+1)$ is even, and hence $n(n+1)$ is a multiple of four. This yields that $n$ or $n+1$ must be a multiple of four, that is, $n$ is of the form $n=4k-1$ or $n=4k$. Potential values for $n$ are $3,4,7,8,11,12,\dots$. Now we will show that for each of these values of $n$ the frog can get back at $0$ after $n$ jumps. We will prove this by induction. For $n=3$ and $n=4$, it is not hard to find a solution: $1+2-3=0$ and $1-2-3+4=0$. Now suppose that we can choose pluses and minuses such that $\pm 1\pm 2\pm \cdots \pm m=0$ for a certain integer $m$. Then we can also find a combination of pluses and minuses such that $\pm 1\pm 2\pm \cdots \pm (m+4)=0$. Indeed: $$\begin{array}{rl}& \pm 1\pm 2\pm \cdots \pm m+(m+1)-(m+2)-(m+3)+(m+4)\\ & =0+(m+1)-(m+2)-(m+3)+(m+4)\\ & =1-2-3+4\\ & =0.\end{array}$$ It follows that the frog can indeed get back to $0$ after $n$ jumps for each $n$ of the form $n=4k-1$ or $n=4k$. $\square$

(b) This problem actually consists of two variants on part (a), namely in the horizontal and the vertical direction. We start by considering the vertical direction. The frog is making jumps consisting of even numbers of steps. This is actually what was happening in part (a), except that the jumps are twice as long. Hence, the frog can end up on the x-axis if the last jump in the vertical direction consists of $8k-2$ or $8k$ steps. Now we have to investigate whether the frog can also arrive back on the y-axis, and hence at the origin $(0,0)$. The last horizontal jump is one before or one after the last vertical jump, hence the last horizontal jump must consist of $8k-3$, $8k-1$, or $8k+1$ steps. We will investigate whether it is possible that $\pm 1\pm 3\pm \cdots \pm n=0$ for $n$ of the form $8k-3$, $8k-1$, or $8k+1$. To get back to the y-axis, the total number of horizontal steps must be even. Because each jump consists of an odd number of steps, the frog must make an even number of jumps in the horizontal direction. If the last horizontal jump is of the form $n=8k-3$ or $n=8k+1$, then the total number of horizontal jumps is odd. This cannot happen. For the remaining case $n=8k-1$, we will use induction to prove that this case is possible. Suppose that the last horizontal jump consists of $8k-1$ steps. We show that we can put pluses and minuses such that $\pm 1\pm 3\pm \cdots \pm (8k-1)=0$. For $k=1$, we find $1-3-5+7=0$. Suppose that for a certain $j\ge 1$, we have $\pm 1\pm 3\pm \cdots \pm (8j-1)=0$. Then $$\begin{array}{rl}& \pm 1\pm 3\pm \cdots \pm (8j-1)+(8j+1)-(8j+3)-(8j+5)+(8j+7)\\ & =0+1-3-5+7\\ & =0\end{array}$$ and we can choose pluses and minuses such that $$\pm 1\pm 3\pm \cdots \pm (8(j+1)-1)=0.$$ Now we have shown that we can put pluses and minuses such that $\pm 1\pm 3\pm \cdots \pm (8k-1)=0$ for each integer $k$.

We conclude that there are two possibilities for the frog to end at the origin $(0,0)$. The first is for $n=8k-1$: the second to last jump consists of $8k-2$ vertical steps, and the last jump consists of $8k-1$ horizontal steps. The second is $n=8k$, then the second last jump consists of $8k-1$ horizontal steps and the last jump consists of $8k$ vertical steps. $\square$