Thread: Combinatorics - show result?

1. Combinatorics - show result?

If $(n + 1)$ integers are chosen from integers $1,2,3,\mbox{...},2n$, show that, among the chosen integers, there are two, such that one of them divides the other.

2. I cant remember exactly how to do this but what you have to note is that any integer can be written in the form $a \cdot 2^k$ where $k \geq 0$ and a is odd. Note also that in this case a has n values since there is n odd and n even integers between 1 and 2n.

Now you have to use the pigeonhole principle. How exactly i cant remember. But im guessing since there n values of a and you choose n+1 integers you'll end up at the fact that one 'hole' has 2 'pigeons' in it.

3. Originally Posted by fardeen_gen
If $(n + 1)$ integers are chosen from integers $1,2,3,\mbox{...},2n$, show that, among the chosen integers, there are two, such that one of them divides the other.
You could probably use induction. Proof. Base case: For $n=1$, we choose $2$ integers of $1,2$. And $1|2$. Inductive step: Suppose that $k+1$ integers are chosen from the integers $1,2,3, \dots, 2k$ where $k \in \mathbb{N}$ and there are two, such that one divides the other. Now append $2k+1$ and $2k+2$. Then if we choose $k+2$ of the integers we know have to use the Pigeonhole principle. You could have a case where you choose the $k+2$ integers such that the integer in the inductive hypothesis are contained. Or could have both numbers not contained. Finally you could have one contained and the other not. $\square$