Applying the Pigeon Hole principle?

Question

I've been struggling with this problem for a while and can't find a solution.

Let M2n be the set {1, 2, 3, ..., 2n}

n+1 integers from the set are chosen.

Show that at least two of the numbers satisfy a|b; meaning a is a divisor of b.

Answer 1

This is a well-known problem, with an extremely elegant solution due to Paul Erdos.

Let the n + 1 chosen elements be a_1, a_2, ... , a_(n+1). Write a_j = 2^(e_j)*w_j, j = 1, ... n + 1, where w_j is odd. Since there are only n odd integers between 1 and 2n, some two w's are equal, say w_h and w_k. Now look at a_h and a_k; whichever one of these has the smaller exponent on 2 is the a you seek, the other is b.