# Divisibility proof in random integer subset

• May 8th 2009, 11:52 PM
knarQ
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.

http://www.bahnhof.se/wb204729/untitled.jpg
• May 9th 2009, 10:52 AM
ThePerfectHacker
Quote:

Originally Posted by knarQ
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.

http://www.bahnhof.se/wb204729/untitled.jpg

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$.
• May 10th 2009, 11:14 AM
knarQ
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!