Problem 2223

Solution:

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 $0 < i < n$, $0 < j < n$, $i \neq j$, $n$ divides $2i + j$ and $x_{i} \geq x_{j}$. Then the highest power of $2$ dividing $2i + j$ is $2^{x_{j}}$ and therefore $k \leq x_{j}$ and $2^{k} \leq j$. Since $0 < j < n$, this is possible only if $n = 3 \cdot 2^{k}$ and either $j = 2^{k}$ or $j = 2^{k+1}$. In the first case, $i \neq j$ and $x_{i} \geq x_{j}$ imply $i = 2^{k+1}$ leading to the contradiction $3 \cdot 2^{k} = n \mid 2i + j = 5 \cdot 2^{k}$. The second case is not possible as $i \neq j$ and $x_{i} \geq x_{j}$ now imply $i \geq 2^{k+2} > n$.

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 $2a_{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.

Let $E = \{n / 3, n / 2, 2n / 3\} \cap \{1, 2, \ldots, n-1\}$, $D = \{1, 2, \ldots, n-1\} \setminus E$, and let $f: D \rightarrow \{1, 2, \ldots, n-1\}$ be the function sending $i$ in $D$ to the unique $f(i)$ in $\{1, 2, \ldots, n-1\}$ such that $f(i) \equiv -2i \pmod{n}$.
Then the condition of the problem is that $x_{i} < x_{f(i)}$ for each $i$ in $D$. Since $D$ is a finite set, the integers $x_{1}, x_{2}, \ldots, x_{n-1}$ exist if and only if for each $i$ in $D$ there exists a positive integer $k(i)$ such that $f^{k(i)}(i)$ belongs to $E$. This can be seen as follows:
- If $f^{k}(i)$ does not belong to $E$ for any $k > 0$ for some $i$, then there exists $k_{2} > k_{1} > 0$ such that $f^{k_{1}}(i) = f^{k_{2}}(i)$, leading to the contradiction $x_{f^{k_{1}}(i)} < x_{f^{k_{2}}(i)} = x_{f^{k_{1}}(i)}$.
- On the other hand, if such $k(i)$ exists for each $i$ in $D$, and if $k_{0}(i)$ denotes the smallest such, then the condition of the problem is satisfied by letting $x_{i} = -k_{0}(i)$ for $i$ in $D$, and $x_{i} = 0$ for $i$ in $E$.
In other words, the integers $x_{1}, x_{2}, \ldots, x_{n-1}$ exist if and only if for each $i$ in $D$ there exists a positive integer $k(i)$ such that $(-2)^{k(i)} i \equiv n / 3, n / 2$ or $2n / 3 \pmod{n}$. For $i = 1$, this implies that $n = 2^{k}$ with $k \geq 1$ or $n = 3 \cdot 2^{k}$ with $k \geq 0$. On the other hand, if $n$ has one of these forms, letting $k(i) = k$ does the trick for all $i$ in $D$.

Suppose that $x_{1}, x_{2}, \ldots, x_{k-1}$ satisfy the condition of the problem for $n = k$. Let $y_{2i} = x_{i}$ for $1 \leq i \leq k-1$ and choose $y_{2i-1}$ for $1 \leq i \leq k$ to be less than $\min \{x_{1}, x_{2}, \ldots, x_{k-1}\}$. Now suppose that for $n = 2k$ we have $0 < i < n$, $0 < j < n$, $i \neq j$, $n$ divides $2i + j$. Then $j$ is even. If $i$ is also even, then $0 < i/2 < k$, $0 < j/2 < k$ and $k$ divides $2(i/2) + (j/2)$; hence $y_{i} = x_{i/2} < x_{j/2} = y_{j}$. On the other hand, if $i$ is odd, then $y_{i} < \min \{x_{1}, x_{2}, \ldots, x_{k-1}\} \leq x_{j/2} = y_{j}$. Therefore, $y_{1}, y_{2}, \ldots, y_{2k-1}$ satisfy the condition of the problem for $n = 2k$.
Since the condition is vacuous for $n = 2$ and $n = 3$, it follows that $x_{1}, x_{2}, \ldots, x_{n-1}$ satisfying the condition exist for all $n = 2^{k}$ with $k \geq 1$ and $n = 3 \cdot 2^{k}$ with $k \geq 0$.
Now suppose that $x_{1}, x_{2}, \ldots, x_{n-1}$ satisfying the condition of the problem exist for $n = 2^{k} m$ where $k$ is a nonnegative integer and $m > 3$ is an odd number. Let $b_{0} = 2^{k}$ and let $b_{i+1}$ be the remainder of the division of $(-2) b_{i}$ by $n$ for $i \geq 0$. No terms of this sequence is $0$ and no two consecutive terms are both equal to $b_{1}$ as $m > 3$. On the other hand, as $(-2)^{\phi(m)} \equiv 1 \pmod{m}$, we have $b_{\phi(m)} \equiv (-2)^{\phi(m)} 2^{k} \equiv 2^{k} \equiv b_{0} \pmod{n}$, and hence $b_{\phi(m)} = b_{0}$. Since $2b_{i} + b_{i+1}$ is divisible by $n$ for all $i \geq 0$, we have $x_{b_{0}} < x_{b_{1}} < \cdots < x_{b_{\phi(m)}} = x_{b_{0}}$, a contradiction.