Let there be $101$ numbers arbitrarily chosen from the first $200$ whole numbers $1,2, \ldots ,200$. Prove that among the chosen numbers there is a pair of numbers such that one them is divisible by other.

  • $\begingroup$ I do not know what's Pigeon Hole. So could not know that "Prove using Pigeon Hole" was my question. Sorry. $\endgroup$ – Anderson Lima Feb 6 '13 at 19:33

This follows from Pigeon hole principle. Any number $n$ in $\{1,2,\ldots,200\}$ can be written as $n=2^k a$ where $2^k \Vert n$ i.e. $(a,n) = 1$ and $a \in A = \{1,3,\ldots,199\}$.

The set $A$ has $100$ elements. Given $101$ distinct elements from $\{1,2,\ldots,200\}$, say $\{n_1,n_2,\ldots,n_{101}\}$, we have $n_j = 2^{k_j} a_j$, where $j \in \{1,2,\ldots,101\}$ and $a_j \in \{1,3,5,\ldots,197,199\}$.

Hence, by PHP, there exists $a_l = a_m = \tilde{a}$. Correspondingly, we have $n_l = 2^{k_l}\tilde{a}$ and $n_m = 2^{k_m} \tilde{a}$ and $k_m \neq k_l$. Clearly, either $\left(n_l = 2^{k_l}\tilde{a}\right) \vert \left(n_m = 2^{k_m}\tilde{a} \right)$ or $\left(n_l = 2^{k_m}\tilde{a}\right) \vert n_l = \left(2^{k_l}\tilde{a} \right)$.


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.