8
$\begingroup$

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

$\endgroup$
6
$\begingroup$

$3$.

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

$\endgroup$
  • $\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
  • $\begingroup$ What if, in case 2, we end up with $(n+1) | b$ in $B$ and $b$ is odd. Then we would not be able to replace $(n+1)$ with $2(n+1)$, correct? $\endgroup$ – Elliot Gorokhovsky Dec 9 '19 at 7:26
  • $\begingroup$ Ah, the key is that $(n+1)$ cannot divide any integer in $B$ since $\max B \leq 2n$. This may be worth mentioning in the proof; you say "if either $a,b = n+1$", but it must be the case that $b$ specifically is equal to $n+1$. $\endgroup$ – Elliot Gorokhovsky Dec 9 '19 at 7:28

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.