SELECTION and TRAINING SESSION

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.