Library / China Western Mathematical Olympiad /32 of 51

China Western Mathematical Olympiad

Combinatorics Difficulty 6.2 National Olympiad Prove it China

Let $M \subseteq \{1, 2, \dots, 2011\}$ be a subset satisfying the following condition: For any three elements in $M$ , there exist two of them $a$ and $b$ , such that $a \mid b$ or $b \mid a$ . Determine, with proof, the maximum value of $|M|$ , where $|M|$ denotes the number of elements of $M$ . (posed by Feng Zhigang)

Solution

One can check that $M = \{1, 2, 2^2, 2^3, \dots, 2^{10}, 3, 3 \times 2, 3 \times 2^2, \dots, 3 \times 2^9\}$ satisfies the condition, and $|M| = 21$ .

Suppose that $|M| \ge 22$ , and let $a_1 < a_2 < \dots < a_k$ be the elements of $M$ , where $|M| = k \ge 22$ . We first prove that $a_{n+2} \ge 2a_n$ for all $n$ ; otherwise, we have $a_n < a_{n+1} < a_{n+2} < 2a_n$ for some $n < k + 2$ , then any two of these three integers $a_n, a_{n+1}, a_{n+2}$ do not have any multiple relationship, which contradicts the assumption.

It follows from the inequality above that $a_4 \ge 2a_2 \ge 4$ , $a_6 \ge 2a_4 \ge 8$ , $\dots$ , $a_{22} \ge 2a_{20} \ge 2^{11} > 2011$ , which is a contradiction!

Hence, the maximum value of $|M|$ is $21$ .
$\square$

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 reproduced verbatim; metadata (topic, difficulty) added by this project.