2
$\begingroup$

Let $n \geq 2$ . Select $n+1$ different integers from the set ${\{1,2,...,2n}\}$. Is it true that there will always be two among the selected integers so that one of them is equal to twice the other?

Is it true that there will always be two among the selected integers so that one is a multiple of the other?

attempt:

The first statement is false. To see this, consider the case when $n=2$. Then we select $3$ different integers from ${\{1,2,3,4}\}$. Choose $1,3,4$, then it does not work.

Can someone please help me on the second part? Thank you

$\endgroup$
0
$\begingroup$

every number can be written uniquely in the form $2^ak$ so that $k$ is odd.

There are exactly $n$ different possible values of $k$, so by the pigeon-hole principle there exist integers $k,a,b$ such that $2^ak$ and $2^bk$ are both in the subset of selected integers.

$\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.