$n + 1$ numbers are picked at random from $2n$ integers $1, 2, 3, \ldots, 2n$. Prove that among the numbers picked we can find at least two, one of which is divisible by the other.

If we try to chose numbers from the right most end from 2n and the approach n we see that there are two pairs of numbers n, 2n and n-1, 2n-1 which satisfy this.

Similarly, I have tried some possibilities, all of them satisfy but I am not able to think of a proof.

Also, this problem is given on the chapter titled "Arithmetic of Integers" that is, related to Number Theory. I don't know anything about Combinatorics except Permutations and Combinations.

Can somebody provide me a hint?

Any help would be highly appreciated.

Edit:— I've just realized that this problem is to be proven via mathematical induction. I would be greatly thankful to anyone who would provide me a solution via induction.

  • $\begingroup$ I searched about similar problems like this. The problems seemed to use Combinatorics (I don't know anything about it). I want hint based on introductory number theory. $\endgroup$ – Crocogator Mar 21 '20 at 9:27
  • $\begingroup$ Hint: define an equivalence relation on positive integers: let $a\sim b$ denote $a=2^kb$ for some integer $k$. From $1$ to $2n$ inclusive, how many equivalence classes are occupied? $\endgroup$ – J.G. Mar 21 '20 at 9:56
  • 1
    $\begingroup$ @DietrichBurde I have autocorrect system on my keyboard. I forgot to change it on the title and I didn't do it for some lame "fun". Is there any other reason you downvoted? $\endgroup$ – Crocogator Mar 21 '20 at 10:03
  • $\begingroup$ Why do you think that I have downvoted? $\endgroup$ – Dietrich Burde Mar 21 '20 at 12:34
  • $\begingroup$ How did you realize that you need a proof based on mathematical induction? $\endgroup$ – user Mar 21 '20 at 17:46

Every number of the set $A=\{1,2,3, \dots 2n\}$ can be written as $2^a \cdot b$ and each number have unique $a$ and $b$.

Now there are only $n$ possibilities for $b$. This is because $b$ must be an odd number and there are only $n$ odd numbers in $2n$ consecutive integers.

If two numbers have the same $b$ then put them in the same bucket. By pigeonhole principle, there are $n$ possibilities but $n+1$ are picked so $2$ numbers must have the same $b$.

Hence there always exists a pair of integers such that one divides the other.


Not the answer you're looking for? Browse other questions tagged or ask your own question.