Let $N \geq 3$ be an integer, and let $a_0, \dots, a_{N-1}$ be pairwise distinct reals so that $a_i \geq a_{2i}$ for all $i$ (indices are taken $\bmod~ N$). Find all possible $N$ for which this is possible. Proposed by Sutanay Bhattacharya
Problem
Source: India EGMO TST 2024/4
Tags: algebra, number theory, Egmo tst
starchan
31.12.2023 16:02
We contend that only powers of $2$ work. Draw a digraph $G$ on $\mathbb{Z}/N\mathbb{Z}$ with edges from $i \mapsto 2i$. It is clear that we may only assign distinct reals $a_i$ if and only if this graph admits a valid topological sort. This is equivalent to $G$ having no cycle of length greater than $1$.
Express $N = 2^{\ell} m$ where $\ell \geq 0$ and $m$ is some odd positive integer. Let $t = \text{ord}_m(2)$. Clearly we have the cycle \[2^{\ell} \mapsto 2^{\ell+1} \mapsto \dots 2^{\ell+t-1} \equiv 2^{\ell}\]This forces $t = 1$ and then $m = 1$, implying that $N$ is a power of $2$. Conversely we see that when $N = 2^{\ell}$ the graph $G$ is the complete (upward directed) binary tree on $N-1$ vertices with its root directed at the self loop $0 \mapsto 0$. It's clear that $G$ has no cycle of length greater than one, so we are done.
Carolstar9
04.01.2024 10:24
Let us look at the implication of the inequality when repeatedly applied on $i=1$. $a_1\ge a_2 \ge a_4 \ge \cdots \ge a_{2^k}\ge a_{2^{k+1}}\ge\cdots$ Since there are only finitely many indices, eventually, this series will repeat. Let $2^{i}\equiv 2^{i+j} \pmod{N}$. Then the chain of inequalities $a_{2^{i}}\ge a_{2^{i+1}} \ge \cdots \ge a_{2^{i+j}}$ has to be a chain of equalities, since $a_{2^{i}}= a_{2^{i+j}}$. Since $a_{l}$ are distinct, we get, in particular, $2^i \equiv 2^{i+1} \pmod{N}$. Therefore, $N \mid 2^{i}$. So, the only possible values are $N=2^k$ for some integer $k$. In this case, for indices of the form $l=2^{m}o$ where $o$ is odd, we can assign arbitrary (and distinct) real numbers from the interval $(-m-1, -m)$. Then, one can easily see that the condition is satisfied. [If $2^{m}o \equiv 2\cdot 2^{n}q \pmod{2^k}$, then $m=n+1$, unless $m, (n+1) \ge k$.]