Prove that any set of $3n+1$ numbers taken from $\{1,2,...,4n\}$ contains three different numbers $a$, $b$, $c$ such that $a|b$ and $b|c$. For arbitrary integer $n>0$, prove that any set of $3n+1$ numbers taken from $\{1,2,...,4n\}$ contains three different numbers $a$, $b$, $c$ such that $a|b$ and $b|c$.
I have tried using mathematical induction, but can't proceed from $k$ to $k+1$ since it is not clear how to choose three new integers from the enlarged set.
From my experience, the answers to this kind of problems may appear as a (mind-blowing) construction of pigeon holes, but I can't think of a way to complete such construction. 
 A: Call our set of $3n+1$ numbers $A$. Write each $a\in A$ as $2^sk$ where $s\geq0$ and $k$ is odd. Now, the possible values of $k$ are $\{1,3,\ldots,4n-1\}$, which has $2n$ elements, and we have $3n+1$ numbers, so some numbers will end up with the same $k$. If we have at least three numbers with the same $k$, we're done because they will divide one another in sequence. 
So suppose we're not done - then, by Pigeonhole there will be at least $n+1$ disjoint pairs of numbers $a,b$ where $a< b$, $a\in A,b\in A$, and $a$ and $b$ share the same odd part $k$. But for each such pair, the corresponding odd part $k$ can only be among $\{1,3,\ldots,2n-1\}$ because otherwise $b>4n$; since these are $n<n+1$ possibilities, this is a contradiction - so this case cannot arise.
A: Partition the set $\{1,2,\dots,4n\}$ into $2n$ chains (some of which are quite short), starting with an odd number and doubling at every step:


*

*$1, 2, 4, 8, 16, \dots$

*$3, 6, 12, 24, 48, \dots$

*$5, 10, 20, 40, 80, \dots$

*$\dots$

*$2n-1, 4n-2$

*$2n+1$

*$2n+3$

*$\dots$

*$4n-1$


If we pick any $2n+1$ numbers, then we'll get two numbers from the same chain, and then one divides the other: we've found a pair $a, b$ with $a \mid b$. That's the easy version of the problem, which gets asked more often. (See, for example, this question, which is where I get the idea.)
To guarantee instead $a, b, c$ such that $a \mid b$ and $b \mid c$, we need three numbers in one chain. So you need to show that if we choose $3n+1$ numbers, then you are guaranteed to end up with three in the same chain.
