3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ $b\ne a$ right?? $\endgroup$ – Shubham Johri Nov 8 '20 at 20:42
  • $\begingroup$ 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$)? $\endgroup$ – QC_QAOA Nov 8 '20 at 20:43
  • $\begingroup$ @QC_QAOA Yes $ a\ne b $ and $\# $ means Cardinality. Thanks. $\endgroup$ – hamam_Abdallah Nov 8 '20 at 20:47
  • $\begingroup$ 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". $\endgroup$ – Hanno Nov 8 '20 at 21:47
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ +1 very nice... $\endgroup$ – user2661923 Nov 8 '20 at 21:27
  • 1
    $\begingroup$ Thank you very much. God bless you. $\endgroup$ – hamam_Abdallah Nov 8 '20 at 21:47
  • $\begingroup$ I searched in vain for alternative (less elegant) proofs. To the best of your knowledge, is there such an alternative proof? $\endgroup$ – user2661923 Nov 9 '20 at 0:06
  • $\begingroup$ @user2661923 I can tell you this is a classic pigeonhole problem. But I am not aware of another proof. $\endgroup$ – Shubham Johri Nov 9 '20 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.