Prove that it is possible to choose $100$ out of the first $200$ positive integers such that none of the numbers chosen is a divisor of another one, but this is not possible for $101$ numbers.
I thought of the Pigeon Hole Principle, there are at least one of each of these two in the set we want to form:
The number of the first divides its double. If twice as much was not chosen it is because it has at least two sets from 1 to 100
How would I prove this formalized?
Best Answer
Solution to the Part $1$:
$$\{101,102,....,200\}$$
For the part $2$ do some partion of $$\{1,2,....,200\}$$
The same idea works if we put an $2n$ numbers. Here is shorter variant for $n=50$
Say $$|\{1,2,4,8,16,32,64\}| = 7$$
$$|\{3,6,12,24,48,96\}| = 6$$
$$|\{5,10,20,40,80\}| = 5$$
$$|\{7,14,28,56\}| = 4$$
$$|\{9,18,36,72\}| = 4$$
$$|\{11,22,44,88\}| = 4$$
$$|\{13,26,52\}| = 3$$
$$|\{15,30,60\}| = 3$$
$$|\{17,34,68\}| = 3$$
$$|\{19,38,76\}| = 3$$
$$|\{21,42,84\}| = 3$$
$$|\{23,46,92\}| = 3$$
$$|\{25,50,100\}| = 3$$
$$|\{27,54\}| = |\{29,58\}| =|\{31,62\}| = |\{33,66\}| =|\{35,70\}| =|\{37,74\}|=$$ $$ |\{39,78\}| =|\{41,82\}| =|\{43,86\}| =|\{45,90\}| = |\{47,94\}| = |\{49,98\}| =2$$
$$|R={rest\;of\; the\; numbers;}| = 25$$
So we find a partition with 25 sets. If the statement would not be true then from each set different from $R$ we have 1 element and if we take all elements from $R$ we would have total of 50 elements which is not true.