For any $n$ positive integers ($n\geq 5$) exactly 3 or 4 of them are equal to each other modulo $2^m$ for some $m$ How can one prove that for any $n$ distinct positive integers, $n\geq 5$, there exists $m$ such that exactly 3 or 4 of them are equal to each other modulo $2^m$?
I tried to prove it for small $n$. For example, for $n=5$ I came up with the following heuristic argument: 3 or 4 or 5 of them are all odd or all even, so we need to exclude the ''5''-case. Assuming they all are, for example, even, we compare them modulo 4, and get the same alternative, and so on. Since we have finite number of the powers of 2, at some point we have to arrive to the desired. 
But I don't know how to handle the general case. Maybe someone has a better idea?
 A: Assume there were counterexamples. Then there is a counterexample with minimal $n \geqslant 5$. There would be one with minimal smallest number involved, and among the counterxamples with that number, with the minimal second-smallest number. Let's say the numbers are $a_1 < a_2 < \dotsc < a_n$. Then all of these numbers must be even, or all must be odd, for otherwise the subset of even numbers or the subset of odd numbers would furnish a counterexample with smaller $n$, since neither subset could have $3$ or $4$ elements, and not both could have $2$ or fewer. So at least one of the two parts contains at least $5$ elements. Since no even number is congruent to an odd number modulo $2^m$ for $m \geqslant 1$, it would be a counterexample. If the numbers were even, then $\bigl(\frac{a_1}{2},\frac{a_2}{2},\dotsc,\frac{a_n}{2}\bigr)$ would be a smaller counterexample, since $\frac{k}{2} \equiv \frac{\ell}{2} \pmod{2^m} \iff k \equiv \ell \pmod{2^{m+1}}$. So all numbers are odd. But then $(a_1+1,a_2+1,\dotsc,a_n+1)$ would also be a counterxample. And so would $\bigl(\frac{a_1+1}{2},\frac{a_2+1}{2},\dotsc,\frac{a_n+1}{2}\bigr)$. But that contradicts the minimality.
