2
$\begingroup$

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?

$\endgroup$
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
1
$\begingroup$

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.

$\endgroup$

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.