Results 1 to 5 of 5

Thread: Weird (difficult) proof

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    33

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Pigeon-hole principle

    Hello VENI
    Quote Originally Posted by VENI View Post
    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.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    33
    Quote Originally Posted by Grandad View Post
    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.

    Grandad
    Why is this part true?

    factorised into $\displaystyle 2^p_i \times q_i$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Factorising

    Hello VENI
    Quote Originally Posted by VENI View Post
    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?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2009
    Posts
    33
    Got it, thank you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Weird Induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 25th 2010, 11:56 PM
  2. Difficult Proof
    Posted in the Trigonometry Forum
    Replies: 7
    Last Post: Oct 4th 2009, 06:11 PM
  3. Difficult Trig Proof
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: Dec 9th 2008, 06:38 PM
  4. [SOLVED] A weird limit proof
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Mar 24th 2008, 12:41 PM
  5. weird log proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Sep 26th 2006, 07:21 AM

Search Tags


/mathhelpforum @mathhelpforum