$Prove that one of $(n+1)$ numbers chosen from $\{1,2, \dots, 2n\}$ is divisible by another.$

Question

$Prove that one of $(n+1)$ numbers chosen from $\{1,2, \dots, 2n\}$ is divisible by another.$

Let $S$ be a subset of $\{1,2, \dots, 2n\}$ with $(n+1)$ elements. Prove that there is an element of $S$ that is divisible by another element of $S$.

Putnam Competition Math Competitions Number Theory

Savionf

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to 50% commission on every question your affiliated users ask or answer.

Answer 1

Answers can be viewed only if

The questioner was satisfied and accepted the answer, or
The answer was disputed, but the judge evaluated it as 100% correct.

View the answer

Select $n+1$ numbers $a_1, a_2, \dots, a_{n+1}$ and write them in the form
\[a_i=2^{k_i}b_i,\]
where $b_i$ are odd numbers between in $\{1, 2, \dots , 2n\}$. Since there are only $n$ such odd numbers, by pigeonhole principle we must have
\[b_i=b_j\]
for some $i,j $ with $i \neq j$. Now it is easy to see that one of $a_i$ or $a_j$ is divisible by the other.

Erdos

$Prove that one of $(n+1)$ numbers chosen from $\{1,2, \dots, 2n\}$ is divisible by another.$

Answer

Related Questions

Search