Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other

Question

Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other.

Answer 1

HINT: Create a pigeonhole for each odd positive integer $2k+1<2n$, and put into it all numbers in $[2n]$ of the form $(2k+1)2^r$ for some $r\ge 0$.

Answer 2

Attempt without pigeonhole principle.

Step 1:

Show the amount of primes less than $2n$ is less than or equal to $n$.

Consider the totatives of $2n$. Every totative is either a prime, $1$ or a multiple of primes that do not divide $2n$. So the amount of totatives of $2n$ added to $d$, where $d$ is the number of prime divisors of $2n$, is strictly larger than the amount of primes less than $2n$. And because the number 1 is a totative of any number, then the number of primes less than $2n$ is less than or equal to $\phi(2n) + d - 1$.

$\phi(2n) = r . \prod (p-1)$ where p are the prime divisors of $2n$, and $r = 2n ÷ (\prod (p-1))$. This is just a slight rearrangement of Euler's product formula for his totient function. And $\phi(2n) \leq n$ because $2$ is a factor of $2n$, and $2-1 =1$, which essentially halves the product relative to $2n$. When 2 is the only unique prime divisor of $2n$ then the number of divisors $d=1$, and so number of primes less than that is less than or equal to $\phi(2n) + d - 1 = \phi(2n) = n$.

For $2n$ with more than one prime divisor, $\phi(2n) = r \prod (p-1) \leq n$ because again, two is a divisor, as mentioned above. But suppose $q$ is also a prime divisor of $n$, then $\phi(2n) \leq (\frac{q-1}{q}) n$ and then by the fundamental theorem of arithmetic $\phi(2n) \leq n-1$. Considering each prime factor greater than $2$, where there are $d-1$ of them so, we induce that $\phi(2n) \leq n - (d-1).$ So the amount of primes less than $2n$ must be less than or equal to $n$ when $2n$ has more than one distinct prime divisor as well, because the amount of primes less than $2n$ is less than $\phi(2n) + d - 1$ which is $ \leq n.$ So the amount of primes less than $2n$ is always less than or equal to $n$

Step 2: Show the set of primes, is the largest subset of the set $[1, 2n]$ that doesn't contain a multiple or factor of any of its elements.

By definition a prime is not a multiple of anything but 1 and itself, so the set of all primes up to $2n$ contains no multiples of anything else. Every other number outside of this set, less or equal to $2n$, must be either a multiple of one of the primes, or a factor of them. And there are at most, $n$ primes up to $2n$ , so taking any $n+1$ elements will result in a multiple of one of the primes, or a factor of all of them.

Edit: On reflection of this approach, it's not complete. Step 2 is unproven. The largest set of totally coprime composites needs to be considered as well to make this proof complete.

There are $\sum (i-1)$ coprime composites with two distinct prime divisors upto ${p_i}^2$. Even given ${p_i}^2 \leq 2n \leq {p_{i+1}}^2$, calculating the size of the subset is not trivial, especially when considering additional coprimes between ${p_i}^2$ and $2n$.