any subset

[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.