Results 1 to 3 of 3

Math Help - Combinatorics - show result?

  1. #1
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539

    Combinatorics - show result?

    If (n + 1) integers are chosen from integers 1,2,3,\mbox{...},2n, show that, among the chosen integers, there are two, such that one of them divides the other.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    I cant remember exactly how to do this but what you have to note is that any integer can be written in the form a \cdot 2^k where k \geq 0 and a is odd. Note also that in this case a has n values since there is n odd and n even integers between 1 and 2n.

    Now you have to use the pigeonhole principle. How exactly i cant remember. But im guessing since there n values of a and you choose n+1 integers you'll end up at the fact that one 'hole' has 2 'pigeons' in it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by fardeen_gen View Post
    If (n + 1) integers are chosen from integers 1,2,3,\mbox{...},2n, show that, among the chosen integers, there are two, such that one of them divides the other.
    You could probably use induction. Proof. Base case: For  n=1 , we choose  2 integers of  1,2 . And  1|2 . Inductive step: Suppose that  k+1 integers are chosen from the integers  1,2,3, \dots, 2k where  k \in \mathbb{N} and there are two, such that one divides the other. Now append  2k+1 and  2k+2 . Then if we choose  k+2 of the integers we know have to use the Pigeonhole principle. You could have a case where you choose the  k+2 integers such that the integer in the inductive hypothesis are contained. Or could have both numbers not contained. Finally you could have one contained and the other not.  \square
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How was this result found
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: January 3rd 2011, 07:56 AM
  2. Prove result
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: July 4th 2010, 02:33 PM
  3. Show independence result
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: July 1st 2010, 02:19 AM
  4. how can u get this result?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 14th 2008, 12:23 PM
  5. prove this result please
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 21st 2008, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum