China Western Mathematical Olympiad

One can check that $M=\{1,2,2^2,2^3,\dots ,2^{10},3,3\times 2,3\times 2^2,\dots ,3\times 2^9\}$ satisfies the condition, and $|M|=21$.

Suppose that $|M|\ge 22$, and let $a_1<a_2<\cdots <a_k$ be the elements of $M$, where $|M|=k\ge 22$. We first prove that $a_{n+2}\ge 2a_n$ for all $n$; otherwise, we have $a_n<a_{n+1}<a_{n+2}<2a_n$ for some $n<k+2$, then any two of these three integers $a_n,a_{n+1},a_{n+2}$ do not have any multiple relationship, which contradicts the assumption.

It follows from the inequality above that $a_4\ge 2a_2\ge 4$, $a_6\ge 2a_4\ge 8$, $\dots$, $a_{22}\ge 2a_{20}\ge 2^{11}>2011$, which is a contradiction!

Hence, the maximum value of $|M|$ is $21$. $\square$