Library / /4 of 11

, 2013

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Saudi Arabia

Tarik wants to choose some distinct numbers from the set $S = \{2, \ldots, 111\}$ in such a way that each of the chosen numbers cannot be written as the product of two other distinct chosen numbers. What is the maximum number of numbers Tarik can choose?

Solution

First, we see that it is possible for Tarik to choose the 101 numbers $11, 12, \ldots, 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 \geq 11$ , then clearly, $k \leq 101$ .

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

If $3 \leq d \leq 10$ , from each of the sets $\{d+1, d(d+1)\}; \{d+2, d(d+2)\}; \ldots; \{11, 11d\}$ , Tarik can choose at most one element. Because $d(d+1) \geq 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, \ldots, d-1$ . Therefore, Tarik didn't choose at least $11-d + d-2 = 9$ numbers. Hence $k \leq 101$ .

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.