# Weird (difficult) proof

• Mar 23rd 2009, 06:26 PM
VENI
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.
• Mar 24th 2009, 04:24 AM
Pigeon-hole principle
Hello VENI
Quote:

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.

• Mar 24th 2009, 07:49 AM
VENI
Quote:

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$
• Mar 24th 2009, 08:10 AM
Factorising
Hello VENI
Quote:

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?