Mathematicians Please Help

Factual Questions
1

How do you prove the following:

There is a set containing the integers from 1 to 2n. From this set a proper subset of n+1 elements is taken. In this subset there exists two integers a and b such that a divides b.

No, you are not doing my homework for me. I had a roommate a few years ago who had this problem. I did not figure it out and I never did get the solution from him. It seems like it should be simple and because of what he was studying at the time I believe it involves the pigeon hole principle but I cannot put it together.

I just know I am going to feel like an idiot when I see this.

2

Here’s a proof:

http://www.sisweb.com/cgi-bin/msgbrd/read2.pl?archived=gen_0/1766.htm

3

Thank you cabbage. I don’t feel like an idiot now. That was not at all an obvious proof. Though, since I strongly suspected the pigeon hole principle was involved, I should have been able to find it.