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$.

Question

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.

Answer 1

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.

Answer 2

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.