
4. Determine all integers $n \geq 2$ for which there exist integers $x_{1}, x_{2}, \ldots, x_{n-1}$ satisfying the condition that if $0<i<n, 0<j<n, i \neq j$ and $n$ divides $2 i+j$, then $x_{i}<x_{j}$.

Proposed by Merlijn Staps, NLD

The answer is that $n=2^{k}$ with $k \geq 1$ or $n=3 \cdot 2^{k}$ where $k \geq 0$.


## Solution 1.

Suppose that $n$ has one of these forms. For an integer $i$, let $x_{i}$ be the largest integer such that $2^{x_{i}}$ divides $i$. Now assume that $0n$.

Now suppose that $n$ does not have one of these forms and $x_{1}, x_{2}, \ldots, x_{n-1}$ satisfying the given condition exist. For any positive integer $m$, let $a_{m}$ be the remainder of the division of $(-2)^{m}$ by $n$. Then none of $a_{m}$ is 0 as $n$ is not a power of 2 . Also $a_{m} \neq a_{m+1}$ for any $m \geq 1$ as $a_{m}=a_{m+1}$ would lead to $n$ dividing $3 \cdot 2^{m}$. Moreover $n$ divides $2 a_{m}+a_{m+1}$. Hence we must have $x_{a_{1}}<x_{a_{2}}<x_{a_{3}}<\ldots$ which is not possible as $a_{m}$ 's can take on only finitely many values.

