Weird (difficult) proof

**VENI** · March 23rd 2009, 06:26 PM

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.

**Grandad** · March 24th 2009, 04:24 AM

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.

Grandad

**VENI** · March 24th 2009, 07:49 AM

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.

Grandad

Why is this part true?

factorised into $2^p_i \times q_i$

**Grandad** · March 24th 2009, 08:10 AM

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?

Grandad

**VENI** · March 24th 2009, 09:21 PM

Got it, thank you.

Thread: Weird (difficult) proof

LinkBack

Thread Tools

Display

Weird (difficult) proof

Pigeon-hole principle

Factorising

Similar Math Help Forum Discussions

Weird Induction proof

Difficult Proof

Difficult Trig Proof

[SOLVED] A weird limit proof

weird log proof

Search Tags