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$
$\endgroup$
1
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
0
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)$.
