Results 1 to 5 of 5

Math Help - Weird (difficult) proof

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    33

    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.
    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 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
    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 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
    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 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
    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: February 26th 2010, 12:56 AM
  2. Difficult Proof
    Posted in the Trigonometry Forum
    Replies: 7
    Last Post: October 4th 2009, 07:11 PM
  3. Difficult Trig Proof
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: December 9th 2008, 07:38 PM
  4. [SOLVED] A weird limit proof
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 24th 2008, 01:41 PM
  5. weird log proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 26th 2006, 08:21 AM

Search Tags


/mathhelpforum @mathhelpforum