I'm back again So there's another problem that I can't get to prove
If we take 21 numbers randomly from $1, 2, 3, ..., 40$ then between those $21$ numbers we will be able to find two numbers, of which the smaller one will divide the bigger one
I've been reading james hein "discrete structures, logic and computability" but still can't get to think logically myself. I would be very grateful if I could get some directions/tips/hints or anything, thanks in advance
On
Every positive integer $n$ can be written uniquely as an odd number times an integer power of two. In other words, the factorization $n=k\cdot2^i$ is unique (where $k$ is a positive odd integer and $i$ is a nonnegative integer).
When the numbers in $\{1,2,\dots,40\}$ are written in this form, the value of $k$ will be one of the $20$ positive odd numbers less than $40$. If $21$ numbers are chosen from $\{1,2,\dots,40\}$, two of them will have the form $k\cdot2^i$ for the same value of $k$, and one of those two (the one with the smaller power of $2$) will divide the other.
Make a following sets:
$$ A= \{1,2,4,8,16,32\}$$ $$ B= \{3,6,12,24\}$$ $$ C = \{5,10,20,40\}$$ $$ D = \{7,14,28\}$$ $$ E = \{9,18,36\}$$ $$F = \{11,22\}$$ $$G = \{13,26\}$$ $$H= \{15,30\}$$ $$I = \{17,34\}$$ $$J = \{19,38\}$$ $$K = \{21,23,25,27,29,31,33,35,37,39\}$$
Suppose the statement is not true. Then we take from each set A,B,...,J at most one element and if we take all elements from K we have a total of 20 elements. A contradiction.