Let $n \ge 3$ be an integer. Zagi the squirrel sits at a vertex of a regular $n$-gon. Zagi plans to make a journey of $n-1$ jumps such that in the $i$-th jump, it jumps by $i$ edges clockwise, for $i \in \{1, \ldots,n-1 \}$. Prove that if after $\lceil \tfrac{n}{2} \rceil$ jumps Zagi has visited $\lceil \tfrac{n}{2} \rceil+1$ distinct vertices, then after $n-1$ jumps Zagi will have visited all of the vertices. (Remark. For a real number $x$, we denote by $\lceil x \rceil$ the smallest integer larger or equal to $x$.)
Problem
Source: 2021 MEMO I-4
Tags: number theory, memo, MEMO 2021
Tintarn
07.09.2021 11:52
It actually seems pretty easy...
The two conditions are equivalent to whether there exists $d \ge 1,m \ge 0$ such that $n \mid (m+1)+\dots+(m+d)$ and $m+d \le n-1$ or $m+d \le \lceil \frac{n}{2}\rceil$, respectively.
This condition is equivalent to $2n \mid d(2m+d+1)$.
Since $d$ and $2m+d+1$ can be arbitrary positive integers, except of different parity, this is equivalent to showing that $2n=g \cdot u$ with $g$ even and $u$ odd is possible with $g+u \le 2n-1$ iff it is possible with $g+u \le n+2$.
But this is trivial:
Either $n$ is a power of $2$, in which case $g+u=2n+1$ and both conditions fails.
Otherwise, a choice with $g,u \ge 2$ is possible and then trivially $g+u \le n+2$ so both conditions are true.
rafaello
07.09.2021 17:34
Consider $n=2^ks$, where $k\geq 1$ and $s\geq 3$ is odd integer. Note that the given condition tells us that $$2n\nmid (i_1-i_2)(i_1+i_2+1)$$for all $0\leq i_1,i_2\leq \lceil \tfrac{n}{2} \rceil$. However note that taking $i_1=\frac{2^{k+1}-1+s}{2}$ and $i_2=\frac{2^{k+1}-1-s}{2}$, we have $i_1-i_2=s$ and $i_1+i_2+1=2^{k+1}$, which would imply a contradiction. Thus, we must have that $$2^{k-1}s<\frac{2^{k+1}-1+s}{2} \Longleftrightarrow 2^{k+1}+s \geq 2^{k}s\Longleftrightarrow 2^{k+1}\geq 3(2^{k}-1),$$thus $k\geq 2$ is impossible. Now if $k=1$, we would have $s\leq 4\implies s=3$. Thus, $n=6$, however $i_1=2$ and $i_2=0$ works here. We conclude now that $n$ is not in the form $2^ks$, where $k\geq 1$ and $s\geq 3$. If we just consider odd $n=2l-1$, we use $i_1=l$ and $i_2=l-2$, this works as $l\leq \lceil\tfrac{2l-1}{2} \rceil$. Hence we have narrowed our possible values of $n$ down to the perfect powers of $2$, i.e. $n=2^k$. Note that $$2^{k+1}\nmid (i_1-i_2)(i_1+i_2+1)$$for any $0\leq i_2<i_1\leq n-1$. Indeed, as $i_1+i_2+1>1$, we must have $2\mid i_1+i_2+1$. However then $i_1-i_2$ is odd. If $2^{k}\mid i_2+1$, we obtain contradiction, because then $2^{k}-1\leq i_2\leq 2^{k}-1$ and there is no possible value for $i_1$. We are done.