# Prove that some subsets contain two positive integers $a$ and $b$ such that $a|b$

Let $$n$$ be a positive integer $$(n\ge 2)$$ and $$A$$ be the set $$A=\{1,2,3,...,2n\}$$ Prove that

$$(\forall B\subset A)\;$$ $$\Bigl(\# B=n+1\implies \exists (a,b)\in B^2 \;:\;a\ne b \wedge a|b\Bigr)$$

It is easy to prove it when $$1\in B$$ and when $$2\in B$$ but i have no idea for the other cases.

Any help will be appreciated. Thanks in advance.

• $b\ne a$ right?? – Shubham Johri Nov 8 '20 at 20:42
• Two things, isn’t this trivially true since any number will divide itself and do you mean to say that $|B|=n+1$ (cardinality is $n+1$)? – QC_QAOA Nov 8 '20 at 20:43
• @QC_QAOA Yes $a\ne b$ and $\#$ means Cardinality. Thanks. – hamam_Abdallah Nov 8 '20 at 20:47
• For Paul Erdős this was one of his favourite "initiation" questions to mathematics. It is mentioned in the chapter "Pigeon-hole and double counting" in "Proofs from THE BOOK". – Hanno Nov 8 '20 at 21:47

Let $$B=\{x_1,x_2...x_{n+1}\}\subseteq A$$.
Let $$x_i=2^{a_i}p_i$$ where $$2\not|~p_i$$ and $$a_i\in\Bbb Z_{\ge0}$$. Then $$p_1,p_2,...,p_{n+1}$$ are $$n+1$$ odd numbers that belong to $$S=\{1,3,5,...,2n-1\}$$. But $$|S|=n$$. By the pigeonhole principle, $$p_k=p_m$$ for some $$k\ne m$$. This gives $$x_k|x_m$$ or $$x_m|x_k$$.