# Thread: Weird (difficult) proof

1. ## Weird (difficult) proof

Show that given any $n+1$ integers from the set $\{1,2,...,2n\}$ one of the integers is a multiple of another. (In fact, one of them is a power of 2 times another.) Hint: Look at the largest odd factor of each number.

I am so confused about where to even start this problem.

2. ## Pigeon-hole principle

Hello VENI
Originally Posted by VENI
Show that given any $n+1$ integers from the set $\{1,2,...,2n\}$ one of the integers is a multiple of another. (In fact, one of them is a power of 2 times another.) Hint: Look at the largest odd factor of each number.

I am so confused about where to even start this problem.
Let $A=\{1,2,...,2n\}$, and we select the subset $S \subset A, |S| = n+1$.

Let $S = \{a_i, i = 1 \dots n+1\}$. Then each of the $a_i$ can be factorised into $2^p_i \times q_i$, where $q_i$ is odd, $q<2n$ and $p \ge 0$. But there are just $n$ odd integers $< 2n$. Therefore, by the pigeon-hole principle, two of the $q_i$ are equal, and hence one of the $a_i$ is a multiple of another.

3. Originally Posted by Grandad
Hello VENILet $A=\{1,2,...,2n\}$, and we select the subset $S \subset A, |S| = n+1$.

Let $S = \{a_i, i = 1 \dots n+1\}$. Then each of the $a_i$ can be factorised into $2^p_i \times q_i$, where $q_i$ is odd, $q<2n$ and $p \ge 0$. But there are just $n$ odd integers $< 2n$. Therefore, by the pigeon-hole principle, two of the $q_i$ are equal, and hence one of the $a_i$ is a multiple of another.

Why is this part true?

factorised into $2^p_i \times q_i$

4. ## Factorising

Hello VENI
Originally Posted by VENI
Why is this part true?

factorised into $2^p_i \times q_i$
Sorry, there is a little typo. There shouldn't be an 'i' subscript after the 2. It should, of course, read $2^p \times q_i$. You'll see that I've said that $p\ge 0$. So if the $a_i$ that we're factorising is an odd number, then $p = 0$, and we just get $a_i = q_i$.

OK?