11
$\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$

1 Answer 1

10
$\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$
4
  • $\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
    Commented Oct 23, 2015 at 3:00
  • $\begingroup$ That's correct. $\endgroup$
    – cr001
    Commented Oct 23, 2015 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$ Commented Dec 9, 2019 at 7:26
  • 2
    $\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$ Commented Dec 9, 2019 at 7:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .