Question

Given a positive integer n, suppose S is a subset of {1, 2,..., 2n} with |S| = n + 1. Prove that there are distinct a,b in S such that a divides b.

Answer 1

i am going to guess pigeon hole principle

Answer 2

i mean, i wasn't given a specific way or topic to use, but i think that would be probably the way to go right?

Answer 3

but how to use it and prove it?

Answer 4

it is actually not that simple, although pigeons it is
a worked out proof is here

Answer 5

i can't seem to open the link

Answer 6

oo okay got it

Answer 7

it is example 3, seems to be a putnam problem

Answer 8

thats the same problem wooww thanks

Answer 9

now i have to think and understand how it works :)

Answer 10

gotta love google right?

Answer 11

yes, that will be the hard part, but it is explained pretty well i think

Answer 12

thanks very much