Minimum descending stacks Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules:

The first card goes to the top of a stack

For every new card k,or

(i) the k is put on the top of an already existed stack, if the value of the top card of a existed stack is bigger than the value of the card k or

(ii) we create a new stack righter than the other stacks and with the card k.

The game is completed after n rounds when there are no more cards on the first pack of cards.

The problem asks to find the optimal algorithm for minimum stacks and prove that this one is the optimal. Thanks in advance.
Use the following strategy $S$: Put each card $c$ on the stack with the smallest top card $c'$ such that $c' &gt; c$.

Consider a generic strategy $T$, and iteratively simulate $S$ and $T$. 
Let $s_i = (s^i_1, s^i_2, \dots, s^i_{h_i})$ be the values on the top of the stacks after placing the $i$-th card $c_i$ according to strategy $S$, in increasing order. Define $t_i = (t^i_1, t^i,_2, \dots, t^i_{k_i})$ similarly for strategy $T$.

Claim: $\forall i=1,\dots,n$, we have: i) $h_i \le k_i$ and ii) $s^i_j \ge t^i_j$ for all $j = 1, \dots, h_i$.

The proof is by induction on $i$.
For $i=1$ we have $h_1=k_1=1$ and $s^1_1 = t^1_1 = c_1$.
For $i&gt;1$ we have two cases.

Case 1) $S$ places $c_i$ in a new stack. Then, by hypothesis we must have $c_i &gt; s^{i-1}_j \ge t^{i-1}_j$ for every $j = 1, \dots, h_{i-1} $. It follows that $k_i \ge h_{i-1} + 1 = h_i$, proving i). Notice that ii) is also verified since, for $j=1,\dots, h_{i-1}$, we have $c_i &gt; s^i_j = s^{i-1}_j \ge t^{i-1}_j = t^i_j$ by induction hypothesis, and $t^i_{h_i} \le c_i = s^i_{h_i}$.

Case 2) $S$ places $c_i$ in an existing stack. Let $\ell$ be the index such that $s^{i}_\ell = c_i$.
We clearly have $k_i \ge k_{i-1} \ge h_{i-1} = h_i$, proving i).
As far as ii) is concerned, for every $j = 1, \dots, \ell-1$ we have $c_i &gt; s^{i-1}_j \ge t^{i-1}_j$, and hence $s^i_j \ge t^i_j$.
Also, $s^i_\ell = c_i = \min\{s^{i-1}_\ell, c_j\} \ge \min\{t^{i-1}_\ell, c_j\} = t^i_\ell$.
Finally, for $j=\ell +1, \dots, h_i$, we have: $s^i_j = s^{i-1}_j \ge \max\{c_i, s^{i-1}_j\} \ge \max\{c_i, t^{i-1}_j\} \ge t^i_j$.

Instantiating the claim with $i=n$ yields $h_n \le k_n$, showing that $S$ is minimizing the number of stacks.