Prove that if select $101$ integers from the set $S = \{1,2,3,...,200\}$, there exist $m,n$ in the selection where $\gcd(m,n) = 1$!
Any hint how to prove this?
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ Two must be consecutive. $\endgroup$ – Robert Cardona Feb 6 '13 at 6:27
-
$\begingroup$ Divide $S$ into $100$ pairs in such a way that the members of each pair are relatively prime. $\endgroup$ – Brian M. Scott Feb 6 '13 at 6:28
Add a comment
|
$\begingroup$
$\endgroup$
2
Consider the partition of $\{1,2,\ldots,200\}$ into $100$ partitions $$\{1,2\},\{3,4\},\{5,6\}, \ldots,\{199,200\}$$ By pigeon-hole principle, we have two numbers in one partition say $2n-1$ and $2n$. The $\gcd$ of this pair is $1$ since if $d \vert (2n)$ and $d \vert (2n-1)$, then $d \vert (2n-(2n-1))$ i.e. $d \vert 1$. Hence, $$ \gcd(2n-1,2n) = 1$$
-
$\begingroup$ in the last step.., since d|1 , so the only possibilities of d is 1, so, gcd(2n-1,2n) = 1 , right? $\endgroup$ – chihiroasleaf Feb 6 '13 at 7:22
-
$\begingroup$ @chihiroasleaf Yes. precisely. $\endgroup$ – user17762 Feb 6 '13 at 7:23
