Results 1 to 3 of 3

Thread: Divisibility proof in random integer subset

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    9

    Divisibility proof in random integer subset

    Can anyone help me getting started on this one? I figure it has something to do with the pigeonhole principle, but I don't know where to start.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by knarQ View Post
    Can anyone help me getting started on this one? I figure it has something to do with the pigeonhole principle, but I don't know where to start.

    We can prove a more general result. If $\displaystyle A$ is a subset with $\displaystyle n+1$ elements from $\displaystyle \{1,2,3,...,2n\}$ then there exists $\displaystyle a,b\in A$ with $\displaystyle a|b$. Each element in $\displaystyle \{1,2,...,2n\}$ can be written as $\displaystyle n\cdot 2^m$ where $\displaystyle n$ is odd and $\displaystyle m\geq 0$. Let these be our pigeonholes. We see that there are $\displaystyle n$ pigeonholes because there are $\displaystyle n$ odd numbers between $\displaystyle 1,2,...,2n$. Thus, two numbers end up in the same pigeonhole. So $\displaystyle a=n\cdot 2^{m_1}, b=n\cdot 2^{m_2}$ not it is clear that $\displaystyle a|b$ if $\displaystyle m_1<m_2$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    9
    It took me a while to get this but it's a really nice proof. I was thinking in the lines of odd numbers and multiples of odd numbers but i couldn't get it down on paper, so thank you very much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Proof that if A is a subset of P(A), P(A) is a subset of P(P(A))
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: May 23rd 2011, 04:26 PM
  2. Proof on Openness of a Subset and a Function of This Subset
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Oct 24th 2010, 09:04 PM
  3. Replies: 0
    Last Post: Feb 3rd 2010, 12:48 PM
  4. Opinion on proof(Integer divisibility)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jan 29th 2010, 10:35 PM
  5. Choosing Random Integer
    Posted in the Statistics Forum
    Replies: 1
    Last Post: Oct 4th 2009, 02:07 PM

Search Tags


/mathhelpforum @mathhelpforum