Only ${2n}\choose{n+1}$ ${n+1}\choose{2}$ cases to try... at worst

Number Theory Level 2

Let $S$ be a subset of $n+1$ elements of $\{1,2, \ldots, 2n \}$ . Are there necessarily two numbers in S such that one is divisible by the other?

Yes, it is always possible No, it is not possible No, it depends on the subset

S

chosen

1 solution

Tomás Carvalho
Jul 24, 2017

All elements $k$ of the subset can be represented as $k = 2^{j}.s$ for some odd number $s$ . This way, we can write the subset as ${2^{k_{1}}.s_{1}, ... , 2^{k_{n+1}}.s_{n+1}}$ where $k_{j}$ are chosen from the set of non negative integers and $s_{j}$ from the set ${1, 3, ..., 2n-1}$ . This set has $n$ elements, so there will be two $s_{j}$ , $s_{t}$ such that $s_{j} = s_{t}$ for different $t$ and $j$ , and therefore one of the elements of the subset , $2^{k_{j}}.s_{j}$ or $2^{k_{t}}.s_{t}$ divides the other.

Only ( 2 n n + 1 ) {2n}\choose{n+1} ( n + 1 2 n ​ ) ( n + 1 2 ) {n+1}\choose{2} ( 2 n + 1 ​ ) cases to try... at worst

1 solution

0 pending reports

Only ${2n}\choose{n+1}$ ${n+1}\choose{2}$ cases to try... at worst