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:
-
Each number in $A$ is less than or equal to $2n$. The proof follows from the induction hypothesis.
-
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.
-
$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
Best Answer
$3$.
If $n+1$ is also in $A$, then $n+1|2n+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$. $\blacksquare$