Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $\{1,2,\ldots,2n\}$, prove that there are two numbers in the set, one of which divides the other.

I can't tell if I'm reducing the problem in the right way. Would it be something like:

Induction Hypothesis: A set of $n+1$ numbers from the first $2n$ natural numbers contains two numbers, one of which evenly divides the other.

Base Case: $n=1$, $\{1,2\}$, 2 is divisible by 1.

Consider a set of $n+2$ numbers, $A$, from the first $2n+2$ natural numbers. There are three cases:

  1. Each number in $A$ is less than or equal to $2n$. The proof follows from the induction hypothesis.

  2. One number in $A$ is greater than $2n$. The remaining set of $n+1$ numbers must each be less than or equal to $2n$. The proof follows from the induction hypothesis.

  3. $A$ contains both $2n+1$ and $2n+2$. I'm not sure how to solve this case.

I'm working through Udi Manber's Introduction To Algorithms: A Creative Approach for personal development, so in keeping with the spirit of the book, I'm trying to use induction.

Without induction, the question is identical to Prove two numbers of a set will evenly divide the other



(1) If $n+1$ is also in $A$, then $n+1|2n+2$.

(2) If $n+1$ is not in $A$, then if we replace $2n+2$ with $n+1$, say the new set is $B$, we can use the induction hypothesis like in case $2$ to conclude there exist $a|b$ in $B$. If both $a,b\neq n+1$, then $a,b$ are in $A$ and we are done. If either $a,b=n+1$ then the other is in $A$ and that number divides $2n+2$. QED.

  • $\begingroup$ Oh, clever. So, in case 2, you're finding either a divisor of 2n+2 or a totally separate $a$ and $b$. $\endgroup$ – Joe Oct 23 '15 at 3:00
  • $\begingroup$ That's correct. $\endgroup$ – cr001 Oct 23 '15 at 3:03

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.