6
$\begingroup$

Question states: "Show that if $n+1$ integers between $1$ and $2n$ (inclusive) are chosen, the set of chosen integers will contain at least one number which divides another member of the same set."

I have found a non-inductive proof online, which uses pigeonhole principle and expressing each number of the chosen set as $2^{aj}$ where $j$ is an odd number from $\{1,3,5,...,2n-1\}$. (so there are $n$ boxes of $j$) So pretty much divide a number repeatedly by 2 until that number becomes odd. For example, we can express $56$ as $2^3 \times 7$. we have $n+1$ numbers which can fit into $n$ boxes, and by the Pigeon Hole Principle we conclude that there are two numbers in a given $j$ boxes; one of them divides the other.

However, my book says that I can prove the question by using induction. Obviously, the base case holds. Here is my progress so far:

Assume true for an integer $n$. We need to prove that an arbitrary set of $n+2$ integers from $\{1,...,2n,2n+1,2n+2\}$ have a number which divides another number from the chosen set. If either one or none of the two new numbers ($2n+1$ and $2n+2$) is chosen, we are done, since we must pick at least $n+1$ elements from the rest of the set $\{1,...,2n\}$ .

A problem arises if BOTH of the two new numbers are chosen. Then we are required to prove that an arbitrary set of $n$ numbers from the set $\{1,...,2n\}$ contains two numbers, one of which divide another, or that the same arbitrary set of numbers must contain a number that divides either $2n+1$ or $2n+2$. If the arbitrary set of $n$ numbers contain either $1$, $2$, or $n+1$, then we are done. So we must prove that an arbitrary set of $n$ numbers from the set $\{3,4,...,n-1,n,n+2,...,2n\}$ contains two numbers, one of which divide another, or that the same arbitrary set of numbers must contain a number that divides either $2n+1$ or $2n+2$.

How do I show this?

$\endgroup$
4
  • 7
    $\begingroup$ Similar: math.stackexchange.com/questions/769721/… also math.stackexchange.com/questions/1493253/… and probably many others. $\endgroup$ – Gerry Myerson Dec 31 '16 at 0:05
  • $\begingroup$ The only numbers in if you choose any n+1 integers in 1...2n then they contain n integers and so one divides another. If you select 2n+1 but not 2n +2 then you must have also selected n and 2n. If you selected 2n+2 then you selected n+1. $\endgroup$ – fleablood Dec 31 '16 at 4:33
  • $\begingroup$ Yes, yes I was. $\endgroup$ – fleablood Dec 31 '16 at 6:11
  • $\begingroup$ Okay, only problem occurs if you pick both $2n+1$ and $2n+2$. Replace $2n+2$ with $n+1$ and toss the $2n+1$. Then you must have two terms divide each other (as you have $n+1$ terms from $1....2n$). If one of the terms divides n+1 then it divides $2n+2$. If not two other terms divide. $\endgroup$ – fleablood Dec 31 '16 at 6:38
2
$\begingroup$

If for the $n+2$ you select only one of them is $2n +1$ or $2n+2$ then the remaining $n+1$ you picked are from $1... 2n$ and must have one number divide another.

If both of $2n+1$ and $2n+2$ are chosen then assume, for sake of a proof by contradiction, that none of the $n+2$ terms have any term dividing another... then you did not pick $n+1$ and none of the terms divide $n+1$ (which divides $2n + 2$). Discard $2n+1$ and $2n+2$ and pick $n+1$ instead. You now have $n+1$ terms from $1... 2n$. None of the terms that aren't $n+1$ divide $n+1$ or each other. $n+1$ doesn't divide any number less then or equal to $2n$. So none of the terms divide any other. That's a contradiction.

==== old answer where I made the faulty assumption that the terms had to be consecutive ===

Suppose you selected $\{m,m+1,.....m+n+1\}\subset \{1....2n\} $

Then $\{m,.....,m+n\}\subset\{1....2n\} $ has a number that divides another.

If $\{m,m+1,...m+n+1\}\not \subset \{1....2n\} $ then $2n+1 \in \{m,m+1,...m+n+1\}$.

Either $m+n+1=2n+1$ so $m=n$ and the set has $n $ and $2n $,

or $m+n+1=2n+2$ in which case $m=n+1$ and the set has $n+1$ and $2n+2$.

$\endgroup$
0

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