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

Question

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.

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 08 '20 at 20:43
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 08 '20 at 21:47

Shubham Johri · Accepted Answer · 2020-11-08T21:28:48.123

2

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

edited Nov 08 '20 at 21:28

answered Nov 08 '20 at 20:52

Shubham Johri

17,659

+1 very nice... – user2661923 Nov 08 '20 at 21:27
1

Thank you very much. God bless you. – hamam_Abdallah Nov 08 '20 at 21:47
I searched in vain for alternative (less elegant) proofs. To the best of your knowledge, is there such an alternative proof? – user2661923 Nov 09 '20 at 00:06
@user2661923 I can tell you this is a classic pigeonhole problem. But I am not aware of another proof. – Shubham Johri Nov 09 '20 at 15:20

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

1 Answers1