Answer: $|M|=21$ . For example: $M={1,2,2^{2},...,2^{10},3,3\times 2,3\times 2^{2},...,3\times 2^{9}}$

Obviously, we have to prove it can't be with more. Suppose $M$ is the best. Sure $1$ may be an element always. Now let $k$ be the smallest element, if all other ones are multiples of $k$, we can divide the others by that and also add the biggest one. At this way, we can do so on until we will get a smallest number $t$ such that $k \not | t.$ (otherwise we can add one element more, cause each $2$ are divisors of each other) Now taking $k,t$ it is easy each element is multiple of $k$ and/or $t.$ Write the multiples in increasing order $K_1, k_2,\cdots$ and $t_1,t_2,\cdots$ Now $k_i|k_j$ if $i<j$ and similar is to prove and then ts09 have constructed a way for maximum, cause the fraction is at least $2$ and $k,t$ at least $2,3.$ The proof, just taking $k_i, k_j,t_l$ where $t_l$ is the biggest one, we see we can better place $K_j$ in row $t$ and by induction, we remove bigger ones each time.

I am not quite satisfied with the rigor of the proof above; too many vague statements. The problem is killed by Dilworth's theorem. Take $M$ to be an eligible set (satisfying the conditions). Then $(M, \mid)$ is a finite poset, with largest size for an antichain being $2$. Then, by Dilworth's theorem, $M$ can be partitioned into two chains. Let $M$ be a maximal size eligible set. Clearly we must have $1\in M$. Also, $M$ cannot be just one chain, since we may increase it by the union with any other element. So $M = A\cup B$, with $A\cap B = \emptyset$, $1\in A$, both $A$ and $B$ being chains. Let $a = \min (A\setminus \{1\})$ and $b=\min B$. No matter how the chains $A$ and $B$ look like, $M$ is eligible, since any subset of three elements contains two comparable ones, by pigeonhole principle. So it all boils down to finding the largest sizes for these two chains. Let $A$ be made by the elements $1 < a < a_1<\cdots <a_k$. Then $a_i \geq 2^{i}a$ for all $i$. Similarly, let $B$ be made by the elements $b < b_1<\cdots <b_{\ell}$. Then $b_j \geq 2^{j}b$ for all $j$. The largest sizes are clearly obtained for $\{a,b\} = \{2,3\}$, $a_i = 2^{i}a$ and $b_j = 2^{j}b$, precisely the example given in the second post.

|M|=21(example is given by ts0_9,I will give my proof) let's prove that |M|>=22 is wrong. Consider |M|=22,M={a1,a2,...,a22} We can assume that a1<a2<...<a22

<Lemma>

<Proof for Lemma

<The Rest of the problem>

Click to reveal hidden text