Divisibility proof in random integer subset

**knarQ** · May 8th 2009, 11:52 PM

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.

**ThePerfectHacker** · May 9th 2009, 10:52 AM

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.

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

**knarQ** · May 10th 2009, 11:14 AM

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!

Thread: Divisibility proof in random integer subset

LinkBack

Thread Tools

Display

Divisibility proof in random integer subset

Similar Math Help Forum Discussions

[SOLVED] Proof that if A is a subset of P(A), P(A) is a subset of P(P(A))

Proof on Openness of a Subset and a Function of This Subset

Proof with a subset of linear combinations of integer numbers

Opinion on proof(Integer divisibility)

Choosing Random Integer

Search Tags