Problem 1155

We define a $\prec$ relation as follows. Let $1 \prec 2$. If the relation is already defined among the numbers $1, 2, \ldots, n$ $(n \geq 2)$, then for any $1 \leq a \leq n$ integer and $(n+1)$, we write them in the form $a=2^{k} a_{1}$ and $n+1=2^{l} B$, where $k$ and $l$ are non-negative integers, and $a_{1}, B$ are odd numbers. (Such a representation clearly exists and is unique for every positive integer.) If now $kl$ then let $n+1 \prec a$. If $k=l$, then consider the integers $\frac{a_{1}+1}{2}$ and $\frac{B+1}{2}$ not exceeding $n$ (and different from each other); let $a \prec n+1$ if $\frac{a_{1}+1}{2} \prec \frac{B+1}{2}$, and let $n+1 \prec a$ if $\frac{B+1}{2} \prec \frac{a_{1}+1}{2}$. This defines the $\prec$ relation between any two positive integers, and the desired property a) is clearly satisfied. Assume that the relation does not satisfy one of the other requirements, i.e., there exist positive integers $a, b, c$ such that $a \prec b \prec c$, and $2 b=a+c$ or $a \nprec c$. Among such triples, choose $a, b, c$ such that $c$ is as small as possible. Write the numbers in the form $a=2^{k} a_{1}, b=2^{l} b_{1}, c=2^{m} c_{1}$, where $k, l, m$ are non-negative, and $a_{1}, b_{1}, c_{1}$ are odd integers. Since $a \prec b \prec c$, we have $k \leq l \leq m$.

1. Case: $k<m$; then $a \prec c$. Clearly, $2^{k+1}$ divides $2 b=2^{l+1} b_{1}$, but does not divide $a+c=2^{k} a_{1}+2^{m} c_{1}=$ $2^{k}\left(a_{1}+2^{m-k} c_{1}\right)$, since $a_{1}+2^{m-k} c_{1}$ is odd. Thus, $2 b \neq a+c$, contradicting the choice of $a, b, c$.
2. Case: $k=l=m$; then $\frac{a_{1}+1}{2} \prec \frac{b_{1}+1}{2} \prec \frac{c_{1}+1}{2}$. If $c \neq 1$, then $\frac{c_{1}+1}{2}<c$, and by the minimality of $c$, $\frac{a_{1}+1}{2} \prec \frac{c_{1}+1}{2}$, so $a \prec c$, and $2 \cdot \frac{b_{1}+1}{2} \neq \frac{a_{1}+1}{2}+\frac{c_{1}+1}{2}$ implies $2 b \neq a+c$, contradicting the indirect assumption; thus $c=c_{1}=1$. Then $b \prec 1$. Let $d$ be the smallest positive integer for which $d \prec 1$. Clearly, $d$ is greater than 1 and odd, but then $\frac{d+1}{2} \prec \frac{1+1}{2}=1$. This, however, contradicts the minimality of $d$, since $\frac{d+1}{2}<d$.

In both cases, we arrive at a contradiction, so the $\prec$ relation satisfies all the requirements of the problem.

Braun Gábor (Budapest, Szent István Gimn., III. o.t.)