Prove or disprove Any subset X 1 2 32n with X n contains tw

Prove or disprove: Any subset X {1, 2, 3,...,2n} with |X| > n contains two (unequal) elements a, b X for which a |b or b |a.

Solution

first process

Let X={1,2,3,....…,2n}. Write X=EO where E are the evens and O are the odds. Then |O| the size of O, is n. Now let xX. With the help of unique factorization of integers we can write x=2AB where B is odd. The association f:xB therefore gives a well defined mapping XO. Since |O|=n, |f(P)|n|

for any subset PX. Therefore, if PX has n+1 elements, there must be two elements a,bP such that f(a)=f(b). In other words a=2^a1*B and b=2^a2*B. So if a1<a2 then a divides b. Otherwise a1>a2 and b divides a..

Any subset X(1,2,3.....2n) with X>N contains two element a/b or b/a(Proved)