Let $S$ be the subset of $\{1, 2, \dots, 100\}$ where $|S|=26$. Then, $S$ contains an odd or there exists $x,y\in S$ such that $x|y$

Question

If it contains an odd then we are done. Otherwise there will be $26$ even numbers which is $1$ more than the half of the total even numbers in the set. But I have no idea how to do it. Will Pigeonhole principle be helpful? Does smallest number in the set is the required $x$?

Answer 1

Suppose $S$ does not contain an odd number. Notice that every even number in the set $\{1,2,\dots,100\}$ is of the form $2^ab$ where $a\geq1$ and $b$ is an odd integer between $1$ and $49$ ($25$ options). Because of this there must be two numbers with the same value of $b$ in $S$, that is $2^ab$ and $2^cb$, this is a contradiction as one would divide the other.