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

Printable View

- May 9th 2009, 12:52 AMknarQDivisibility 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, 11:52 AMThePerfectHacker
We can prove a more general result. If is a subset with elements from then there exists with . Each element in can be written as where is odd and . Let these be our pigeonholes. We see that there are pigeonholes because there are odd numbers between . Thus, two numbers end up in the same pigeonhole. So not it is clear that if .

- May 10th 2009, 12:14 PMknarQ
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!