Problem 1103

Solution:

a) Let $a_{1} < \cdots < a_{n-1} < a_{n} = 2000 < a_{n+1} < \cdots < a_{m}$ be the elements of a good set. Since $a_{i+1} \geq 2 a_{i}$, then $2000000 > a_{m} \geq 2^{m-n} 2000$ and hence $m-n \leq 9$.

On the other hand, the equality $2000 = 2^{4} 5^{3}$ shows that $a_{i} = 2^{k_{i}} 5^{l_{i}}$ for $i \leq n-1$, where $0 \leq k_{i} \leq k_{i+1} \leq 4$, $0 \leq l_{i} \leq l_{i+1} \leq 3$ and $k_{i} + l_{i} \leq 6$. Hence $n \leq 8$ and so $A$ has at most $8 + 9 = 17$ elements. An example of a good set of $17$ elements is obtained by setting $a_{i} = 2^{i-1}$, $1 \leq i \leq 5$, $a_{i} = 2^{4} 5^{i-5}$, $6 \leq i \leq 8$, $a_{i} = 2^{i-4} 5^{3}$, $9 \leq i \leq 17$.

b) For a good set of maximal cardinality one has that $m = 17$ and $n = 8$, i.e. $a_{8} = 2000$. Moreover, $k_{i} + l_{i} = i-1$ for $1 \leq i \leq 7$, which shows that $a_{1} = 1$ and that the subset $\{a_{2}, \ldots, a_{7}\}$ is determined by the numbers $1 \leq i_{1} < i_{2} < i_{3} \leq 7$ such that $l_{i_{1}} = 0$, $l_{i_{1}+1} = 1$, $l_{i_{2}} = 1$, $l_{i_{2}+1} = 2$, $l_{i_{3}} = 2$ and $l_{i_{3}+1} = 3$.

There are $\binom{7}{3} = 35$ possibilities for this subset. Since $2^{9} < 2^{8} \cdot 3 < 1000 < 2^{10}$, it follows that either $a_{i} = 2^{i-4} 5^{3}$ for $9 \leq i \leq 17$, or there is an index $j$, $9 \leq j \leq 17$ such that $a_{i} = 2^{i-4} 5^{3}$ for $8 \leq i < j$ and $a_{i} = 2^{i-5} 5^{3} 3$ for $j \leq i \leq 17$. Hence there are $10$ possibilities for the subset $\{a_{9}, \ldots, a_{17}\}$. So, the number of the good sets of maximal cardinality equals $35 \cdot 10 = 350$.