Problem 2011

Solution:

Number the vertices $0,1, \ldots, n-1$ clockwise starting at the vertex Zagi is on. After his $i$-th jump Zagi will be at a vertex numbered $1+2+\cdots+i=\frac{i(i+1)}{2} \pmod n$. We need to prove that if for all $k \in\left\{0,1,2, \ldots,\left\lceil\frac{n}{2}\right\rceil\right\}$ the fractions $\frac{k(k+1)}{2}$ achieve different values modulo $n$ then they achieve different values modulo $n$ even for all $k \in\{0,1,2, \ldots, n-1\}$. We will in fact prove two following claims:

- for numbers of the form $n=2^{r}$, with $r \geq 2$, all $k \in\{0,1,2, \ldots, n-1\}$ the fractions $\frac{k(k+1)}{2}$ achieve different values mod $n$;
- for numbers of the form $n=2^{r} \cdot l$, with $r \geq 0$ and $l \geq 3$ odd, we have that there exist distinct $a, b \in\left\{0,1,2, \ldots,\left\lceil\frac{n}{2}\right\rceil\right\}$ such that $\frac{a(a+1)}{2} \equiv \frac{b(b+1)}{2} \pmod n$.

Let us firstly observe $n$ of the form $2^{r}$, with $r \geq 2$. Let us assume that there are $1 \leq b < a \leq n-1$ such that $\frac{a(a+1)}{2} \equiv \frac{b(b+1)}{2} \pmod{2^{r}}$. Equivalently, $2^{r+1} \mid (a-b)(a+b+1)$. Factors on the right hand side have different parity, thus we have either $2^{r+1} \mid a-b$ or $2^{r+1} \mid a+b+1$. In the first case we have that $a-b \leq n-1 < 2n$. In the second case we have $a+b+1 \leq (n-1)+(n-2)+1 = 2n-2 < 2n$. Hence, in both cases we obtain contradiction, and we can conclude that there indeed do not exist such $a$ and $b$.

Let us now observe $n$ of the form $2^{r} \cdot l$, with $r \geq 0, l \geq 3$ odd. Set $M=\max \left\{2^{r+1}, l\right\}$ and $m=\min \left\{2^{r+1}, l\right\}$. We claim that the pair $(a, b)=\left(\frac{M+m-1}{2}, \frac{M-m-1}{2}\right)$ satisfies the desired conditions. Indeed:

- Since $2^{r+1}$ is even and $l$ is odd, both $M+m-1$ and $M-m-1$ are even and thus $a, b$ are integers.
- We have: $\frac{a(a+1)}{2}-\frac{b(b+1)}{2}=\frac{1}{2}(a-b)(a+b+1)=\frac{1}{2} m \cdot M=2^{r} l=n$.
- Since $M>m>0$, we have $0 \leq b < a$.

It remains to argue that $a \leq \left\lceil\frac{n}{2}\right\rceil$. Since $r \geq 0$ and $l \geq 3$ we conclude that both $m, M$ are greater or equal to $\min \left\{2^{r+1}, l\right\} \geq 2$. From $m M=2 n$, they are both less or equal to $n$. So we have inequality $(m-n)(m-2) \leq 0$, which implies $m+M=m+\frac{2 n}{m} \leq 2+n$. Hence $a=\frac{M+m-1}{2} \leq \frac{n+1}{2} \leq \left\lceil\frac{n}{2}\right\rceil$ as desired.