# Weird (difficult) proof

• Mar 23rd 2009, 06:26 PM
VENI
Weird (difficult) proof
Show that given any $\displaystyle n+1$ integers from the set $\displaystyle \{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 $\displaystyle n+1$ integers from the set $\displaystyle \{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 $\displaystyle A=\{1,2,...,2n\}$, and we select the subset $\displaystyle S \subset A, |S| = n+1$.

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

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

Hello VENILet $\displaystyle A=\{1,2,...,2n\}$, and we select the subset $\displaystyle S \subset A, |S| = n+1$.

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

Why is this part true?

factorised into $\displaystyle 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 $\displaystyle 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 $\displaystyle 2^p \times q_i$. You'll see that I've said that $\displaystyle p\ge 0$. So if the $\displaystyle a_i$ that we're factorising is an odd number, then $\displaystyle p = 0$, and we just get $\displaystyle a_i = q_i$.

OK?