Problem 1652

For any odd number $a$, $a < 2000$, define the set
$$S_a = \{a \cdot 2^i \mid i \ge 0,\ a \cdot 2^i \le 2000\}.$$
Note that $\{1, 2, ..., 2000\} = \bigcup_a S_a$, where $a$ varies through all odd numbers less than $2000$. Both numbers of the pair $(k, 2k)$ belong to one and the same $S_a$. So we need to find the least amount $m_a$ of the numbers that one should mark in any $S_a$ in order that any pair $(k, 2k)$ from $S_a$ contains at least one marked number. It is obvious that if $x_1 < x_2 < ... < x_n$ are all numbers from $S_a$, then this least amount equals $[n/2]$ (since at least one of any two neighboring numbers should be marked).

Further,
$$|S_1| = 11 \text{ since } 2^{10} < 2000 < 2^{11}, \text{ thus } m_1 = 5;$$
$$|S_3| = 10 \text{ since } 3 \cdot 2^9 \le 2000 < 3 \cdot 2^{10}, \text{ thus } m_3 = 5;$$
$$|S_5| = |S_7| = 9 \text{ since } 7 \cdot 2^8 \le 2000 < 5 \cdot 2^9, \text{ thus } m_5 = m_7 = 4;$$
$$|S_a| = 8 \text{ for } a = 9, 11, 13, 15 \text{ since } 15 \cdot 2^7 \le 2000 < 9 \cdot 2^8, \text{ thus } m_a = 4 \text{ for these } a;$$
$$|S_a| = 7 \text{ for odd } a, 17 \le a \le 31 \text{ (in total, 8 values) since } 31 \cdot 2^6 \le 2000 < 17 \cdot 2^7, \text{ thus } m_a = 3 \text{ for these } a;$$
$$|S_a| = 6 \text{ for odd } a, 33 \le a \le 61 \text{ (in total, 15 values) since } 61 \cdot 2^5 \le 2000 < 33 \cdot 2^6, \text{ thus } m_a = 3 \text{ for these } a;$$
$$|S_a| = 5 \text{ for odd } a, 63 \le a \le 125 \text{ (in total, 32 values) since } 125 \cdot 2^4 \le 2000 < 63 \cdot 2^5, \text{ thus } m_a = 2 \text{ for these } a;$$
$$|S_a| = 4 \text{ for odd } a, 127 \le a \le 249 \text{ (in total, 62 values) since } 249 \cdot 2^3 \le 2000 < 127 \cdot 2^4, \text{ thus } m_a = 2 \text{ for these } a;$$
$$|S_a| = 3 \text{ for odd } a, 251 \le a \le 499 \text{ (in total, 125 values) since } 499 \cdot 2^2 \le 2000 < 251 \cdot 2^3, \text{ thus } m_a = 1 \text{ for these } a;$$
$$|S_a| = 2 \text{ for odd } a, 501 \le a \le 999 \text{ (in total, 250 values) since } 999 \cdot 2^1 \le 2000 < 501 \cdot 2^2, \text{ thus } m_a = 1 \text{ for these } a.$$
So we need to mark at least $1 \cdot (250 + 125) + 2 \cdot (62 + 32) + 3 \cdot (15 + 8) + 4 \cdot (4 + 2) + 5 \cdot (1 + 1) = 375 + 188 + 69 + 24 + 10 = 666$ numbers. On the other hand, one can easily mark exactly $666$ numbers to satisfy the problem condition.