Prove that these conditions happen in an increasing sequence of size $sr+1$ Imagine we have an increasing sequence of integer numbers like this :  
$ a_1 \lt a_2 \lt \dots \lt a_{sr+1} $  $ \forall i$  $a_i \gt 0$
Prove that one of these happens in this sequence :
a) There exists $s+1$ numbers that no pair of them divide each other.  
b) There exists $r+1$ numbers that each number divides the next number.
 A: This is an application of Mirsky's theorem:
https://en.wikipedia.org/wiki/Mirsky%27s_theorem
Consider the partial order on $A = \{a_1,...,a_{sr+1}\}$ whereby $a \succ b $ iff $b$ divides $a$. A chain is a totally ordered subset of the partial order, i.e., a sequence where each element divides its successor. 
An antichain is a subset where none of the elements within the subset are ordered. In other words, for each subset, no pair within the subset divides each other. 
Mirsky's theorem states that there exists a partition of the set $A$ into antichains, such that the number of antichains in this partition is exactly the length of the longest chain (and in fact this is the minimum partition size).
Suppose that there exist at most $r$ numbers such that each number divides the next number, i.e., the length of the longest chain is $\leq r$. Then by Mirsky's Theorem, there exists a partition of the set $A$ into $r$ antichains. But since $A$ has $rs+1$ elements, the pigeonhole principle tells us that at least one antichain has $s+1$ elements; in other words, there exist $s+1$ numbers such that no pair divide each other.
