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 .