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 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 .