I'm working on a proof where I want any subset of $n+1$ distinct integers chosen from $\{1,2,...,2n\}$ has at least two numbers such that one divides the other. I have a feeling that this may be a problem related to modular arithmetic on the set $[2n]$, but I am having issues figuring out the equivalence classes, or the "holes" to put the numbers, i.e. the "pigeons", into. I think what is key is that there will be at least two numbers that are part of the same equivalence class $\mod n,$ but I am not too sure where to move from their. Any suggestions?
1
-
1$\begingroup$ A little explanation for Andre's answer. Write every number in the form $2^km$ where m is odd. $\endgroup$ – Shailesh Dec 10 '15 at 3:37
Add a comment
|
$\begingroup$
$\endgroup$
Hint: Put two numbers $a$ and $b$ in the same pigeonhole if the largest odd number that divides $a$ is the same as the largest odd number that divides $b$.
Note that there are $n$ odd numbers between $1$ and $2n$, so there are $n$ pigeonholes.
answered Dec 10 '15 at 3:33
