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.


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.