Library / Taiwan IMO Selection Camp /262 of 359

Taiwan IMO Selection Camp, 2021

Number theory Difficulty 6.5 National Olympiad Prove it Taiwan

Let $S$ be a set consisting of $n \ge 3$ positive integers, none of which is a sum of two other distinct members of $S$ . Prove that the elements of $S$ may be ordered as $a_1, a_2, \dots, a_n$ , so that neither $a_{i-1} + a_{i+1}$ nor $a_{i-1} - a_{i+1}$ is divided by $a_i$ for all $i = 2, 3, \dots, n-1$ .

Solution

We prove by induction. Let $a = \max S$ and use the inductive hypothesis to find an ordering $b_1, b_2, \dots, b_{n-1}$ of $S \setminus \{a\}$ so that $b_i$ does not divide $b_{i-1} \pm b_{i+1}$ for all $2 \le i \le n-1$ . Observe that
$|b_j - b_{j+1}| < a \neq b_j + b_{j+1} < 2a,$
so that $a$ divides neither $b_j - b_{j+1}$ nor $b_j + b_{j+1}$ . Thus if $b_1, b_2, \dots, b_j, a, b_{j+1}, \dots, b_{n-1}$ does not satisfy the desired property, then either $b_j \mid a + \epsilon b_{j-1}$ or $b_{j+1} \mid a + \epsilon b_{j+2}$ for some $\epsilon \in \{1, -1\}$ . Since there are $n$ positions to insert $a$ and only $n-1$ of $b_j$ , at least one $b_j$ “violates the condition twice as the divider”, meaning $b_j \mid a + \epsilon_1 b_{j-1}$ and $b_j \mid a + \epsilon_2 b_{j+1}$ for some $\epsilon_1, \epsilon_2 \in \{1, -1\}$ . Thus, $\epsilon_2 b_{j+1} \equiv -a \equiv \epsilon_1 b_{j-1} \pmod{b_j}$ , contradicting the induction hypothesis.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.