Problem 12.5. A set $A$ of positive integers less than 2000000 is called good if $2000 \in A$ and $a$ divides $b$ for any $a, b \in A, a<b$. Find:

a) the maximum possible cardinality of a good set;

b) the number of the good sets of maximal cardinality.

Oleg Mushkarov, Nikolai Nikolov
12.5. a) Let $a_{1}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 $\left\{a_{2}, \ldots, a_{7}\right\}$ 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} .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 $\left\{a_{9}, \ldots, a_{17}\right\}$. So, the number of the the "good" sets of maximal cardinality equals $35.10=350$.