Selection tests for the Gulf Mathematical Olympiad 2013

First, we see that it is possible for Tarik to choose the 101 numbers $11,12,\dots ,111$, since the product $11\times 12>111$.

Assume that Tarik has chosen $k$ numbers and let $d$ be the smallest among these numbers. If $d\ge 11$, then clearly, $k\le 101$.

If $2\le d\le 6$, from each of the 9 sets $\{9,9d\};\{10,10d\};\dots ;\{17,17d\}$, Tarik can choose at most one number. Because $9d>17$, these sets are pairwise disjoint. Because $17d\le 102$, there are at least 9 numbers between 9 and 102 that Tarik could not choose. Therefore $k\le 101$.

If $3\le d\le 10$, from each of the sets $\{d+1,d(d+1)\};\{d+2,d(d+2)\};\dots ;\{11,11d\}$, Tarik can choose at most one element. Because $d(d+1)\ge 12$, these sets are pairwise disjoint. Because $11d<111$, there are at least $11-d$ numbers from these sets that Tarik could not choose. But Tarik didn't choose the numbers $2,\dots ,d-1$. Therefore, Tarik didn't choose at least $11-d+d-2=9$ numbers. Hence $k\le 101$.

Therefore, the maximum number of numbers Tarik can choose is $101$.