There have been other SE posts on this question, but I haven't looked at them yet because I want to try to solve the problem myself first.
However, the problem makes no sense to me. For example, $n=10$. Then the problem is saying that among the numbers $11, 12,13,14,15,16,17,18,19,20$ one divides the other. This is clearly not true…
This must be a problem with my misunderstanding, since other people have seemingly understood and answered the problem successfully.
Note that the full phrasing of the question (or one version of it) is: "Show that among any $n+ 1$ positive integers not exceeding $2n$ there must be an integer that divides one of the other integers."
Side question: in this post: Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other, everyone seems to express "the integers between $n-1$ and $2n$" as "the $(n-1)$-subset of $[2n]$". How does the latter idea imply the former? Does $[2n]$ denote an equivalence class? Even then, this makes no sense to me.
Any help is appreciated.
Best Answer
IIRC, the answer goes something like this.
Write the $j$-th integer as $a_j = 2^{b_j}c_j $ where $c_j$ is odd.
Since there are $n$ odd integers in $1:2n$, and there are $n+1\ a_j$, two of the $c_j$ must be equal, say $c_u = c_v$.
Then $a_u | a_v$ if $b_u < b_v$ and $a_v | a_u$ if $b_v < b_u$.
This is not original.