Show that $S$ contains $n+1$ different numbers $a_1,\cdots, a_{n+1}$ such that $a_i | a_{i+1}$ for each $1\leq i\leq n.$ 
(Romanian IMO/BMO Team Selection Tests April 2005 Day 1 Problem 2). Let $n$ be a positive integer and $S$ a set of $n^2 + 1$ positive integers with the property that every $(n+1)$-element subset of $S$ contains two numbers one of which is divisible by the other. Show that $S$ contains $n+1$ different numbers $a_1,\cdots, a_{n+1}$ such that $a_i | a_{i+1}$ for each $1\leq i\leq n.$

I think there should be an elementary solution that doesn't require theorems such as Dilworth's Theorem regarding posets. For the elementary solution, it could be useful to use the pigeonhole principle, induction, or a proof by contradiction. It might also be useful to come up with a sufficiently-sized example of such a set of positive integers in the first place. For $n=1$, $S$ has two elements, one of which is divisible by the other and the claim trivially holds.

Here's a proof for the $n=2$ case that I came up with myself:

For $n=2$, $S$ needs $5$ integers. Write $S = \{b_1,b_2,\cdots, b_5\}, b_1 < b_2<\cdots < b_5$. Every $3$-element subset of $S$ has $2$ elements one of which divides the other. Suppose $S$ does not have $3$ different numbers that divide each other consecutively. Then consider the first three elements of $S$. We may find $a_1,a_2$ among them with $a_1 | a_2$. Then by assumption $a_2$ cannot divide any other element of $S$. Assume first that $a_1 = b_1$. If $a_2 = b_2$, then considering $\{b_2,b_3,b_4\}$, we see that $b_3 | b_4.$ Considering $\{b_2,b_3,b_5\},$ we see that $b_3 | b_5.$ Considering $\{b_2,b_4,b_5\},$ we see $b_4 | b_5.$ But this gives a contradiction since we can choose $\{b_3,b_4,b_5\}$ as the 3-element subset.
Now assume $a_2 = b_3$. Considering $\{b_3,b_4,b_5\},b_4 | b_5.$ Considering $\{b_2,b_3,b_4\},$ we see that $b_2 | b_3$. Considering $\{b_1,b_2,b_4\},$ we see that there is no possibility left (that won't lead to a contradiction).
Finally, assume $a_1 = b_2,a_2=b_3.$ Considering $\{b_3,b_4,b_5\}, b_4 | b_5.$ Considering $\{b_1,b_2,b_4\}$, we see that there is no possibility left. Hence the claim must hold for $n=2$.

Here's the technical solution I found online.

We can define a poset on $S$ by $x\leq y$ iff $x|y$. The condition that there does not exist an $n+1$ element subset such that no element divides another translates into the condition that there is no antichain of length $n+1$ in $S$. An antichain is any sequence of pairwise distinct elements of $S$ none of which are comparable according to the ordering on the poset on $S$. Hence the longest antichain in $S$ is of length at most n, so by Dilworth's theorem, $S$ can be written as the union of at most n chains. Since $S$ has $n^2+1$ elements, this implies one of these chains has a length of at least $n+1$.

Version of Dilworth's Theorem used: Let $P$ be a finite poset. Then the smallest set of chains whose union is $P$ has the same cardinality as the longest antichain.

 A: Here is a simple proof that uses the pigeonhole principle.

Call a sequence of different numbers in $S$ a divisible sequence if each number except the first number in the sequence is divisible by the number preceding it. We are asked to show there is a divisible sequence of at least $n+1$ numbers.
Towards a contradiction, suppose any divisible sequence contains at most $n$ numbers.
For each number $s$ in $S$, let $D_s$ be one of the longest divisible sequences that start with $s$. So we have $n^2+1$ sequences (pigeons). The length of each   $D_s$ is one of $1,2,\cdots, n$, ($n$ holes). Hence, at least $\lceil\frac{n^2+1}{n}\rceil=n+1$ $D_s$'s must have the same length.
Consider the first elements of those at least $n+1$ $D_s$'s. One of them, $x$ must be divisible by another of them, $y$. We can prepend $D_x$ by $y$ to obtain a divisible sequence starting with $y$ that is longer than $D_x$ and hence also $D_y$, which contradicts with the definition of $D_y$.
A: This is more of an extended comment than an answer, but it may be worth noting that this problem's setup is "morally equivalent" to that of posets, in the following sense:
Claim. For every finite poset $P$ with elements $x_1,\dots,x_m$, there exist positive integers $y_1,\dots,y_m$ for which, for $1\leq i,j\leq m$, $x_i\leq x_j$ if and only if $y_i\mid y_j$.
Proof. For each $i$, let $S_i\subset\{1,2,\dots,m\}$ be the set of $j$ for which $x_i\leq x_j$. Let $p_1,\dots,p_n$ be distinct primes, and define
$$y_i=\prod_{j\not\in S_i}p_j.$$
Then, if $x_i\leq x_j$, $x_i\leq x_k$ whenever $x_j\leq x_k$, so $S_j\subset S_i$, meaning
$$y_i=\prod_{k\not\in S_i}p_k\ \bigg|\ \prod_{k\not\in S_j}p_k=y_j.$$
Conversely, if $y_i\mid y_j$, then $p_j$ cannot divide $y_i$ (since $p_j\nmid y_j$), so $j\in S_i$, meaning $x_i\leq x_j$. $\square$
So, Dilworth's theorem is equivalent to the following:

Call a sequence $(a_1,\dots,a_k)$ a divisible sequence if $a_1\mid a_2\mid \cdots\mid a_k$. For a set $S$ of positive integers, the maximum size of a subset $T\subset S$ for which no distinct elements of $T$ divide each other is equal to the minimum number of divisible sequences into which $S$ may be partitioned.

In particular, the solution of ApassJack can be rephrased, using "chain" instead of "divisible sequence," to give a proof of Dilworth's theorem.
