Can any subset from a set of {1,2,...,2n} contain two elements where one divides the other?

[barbiemathgurl]

i got this problem which is killin me :tongue:

given a set {1,2,...,2n} choose any (n+1) element subset, show there exists an element which divides another element.

 

[cristo]

What's the actual question? Are you asked to choose a subset of {1,2,...,2n} containing n+1 elements such that at least one element divides at least one other? I guess it isn't, since an answer to this is pretty obvious isn't it?

 

[Kummer]

The problem is asking, I assume, that is you choose any n+1 element subset then there exists two elements a and b so that a|b.

Proof. Any number from {1,2,...,2n} can be uniquely expressed as $$2^pq$$ where p is a non-negative integer and q is an (odd) positive integer.
Define the sets:
T_1 = {2^p * 1 }
T_2 = {2^p * 2 }
...
T_n = {2^p * n}
So we partitioned the set into n sets. By the pigeonhole principle two elements end up in the same set T_j, but we purposely defined these sets in such a way so that one divides the other.