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.