Results 1 to 3 of 3

Thread: Combinatorics - show result?

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

    Combinatorics - show result?

    If $\displaystyle (n + 1)$ integers are chosen from integers $\displaystyle 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 $\displaystyle a \cdot 2^k$ where $\displaystyle 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 $\displaystyle (n + 1)$ integers are chosen from integers $\displaystyle 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 $\displaystyle n=1 $, we choose $\displaystyle 2 $ integers of $\displaystyle 1,2 $. And $\displaystyle 1|2 $. Inductive step: Suppose that $\displaystyle k+1 $ integers are chosen from the integers $\displaystyle 1,2,3, \dots, 2k $ where $\displaystyle k \in \mathbb{N} $ and there are two, such that one divides the other. Now append $\displaystyle 2k+1 $ and $\displaystyle 2k+2 $. Then if we choose $\displaystyle k+2 $ of the integers we know have to use the Pigeonhole principle. You could have a case where you choose the $\displaystyle 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. $\displaystyle \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: Jan 3rd 2011, 06:56 AM
  2. Prove result
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Jul 4th 2010, 01:33 PM
  3. Show independence result
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Jul 1st 2010, 01:19 AM
  4. how can u get this result?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Oct 14th 2008, 11:23 AM
  5. prove this result please
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 21st 2008, 05:09 PM

Search Tags


/mathhelpforum @mathhelpforum