Vtyjkyuk

Please check my proof for 2.b. I think that there is a more direct proof using the pigeon hole principle, but the question asks that I use poset, hence my approach below.

Exercise 1.
Prove that in any partial order on a set $P$ of $n geq sr + 1$ elements, where $s, r$ are non-negative integers, there exists a chain of length $s + 1$ or an antichain of size $r+1$.

Exercise 2.
Let $a_1, dotsc, a_n$ be a sequence of $n$ distinct positive integers such that $n geq sr + 1$.
Use Exercise 1 to show that:
(a)
we can either find a subset of $A$ of $a_1, dotsc, a_n$ with $|A| = s + 1$ such that for every two elements in $A$ one element divides the other, or a subset $B$ with $|B| = r+1$ such that no element of $B$ divides the other;
(b)
in this sequence either there is an increasing subsequence of $s+1$ terms or a decreasing subsequence of $r+1$ terms.

(Original image here.)

Attempt at proof:

Let $A = (a_1, a_2,..., a_n)$ denote the sequence.

We define a poset $P$ with the relation:
$$forall i,j in [n], a_j geq^* a_j <=> |a_j| geq |a_i|, textand j geq i$$
(here $geq^*$ denotes the relation on the poset $P$, and $geq$ the usual relation on the integers).

Case 1: $P$ has a chain of size $(s+1)$. Clearly this is an increasing subsequence of length $(s+1)$.

Case 2: $P$ does not have a chain of size $(s+1)$. So by exercise 1, $P$ has an antichain of size $(r+1)$.

We claim that the elements of this antichain form a decreasing subsequence of size $(r+1)$. Indeed, if this is not true, there would exist elements $a_m$ and $a_n$ in the antichain such that $|a_m| geq |a_n|$ and $m geq n$. But this means $a_m geq^* a_n$, thus comparable and can't be in the same antichain. This is a contradiction.

So in this case, $A$ contains a decreasing subsequence of size $(r+1)$.