Why does Patience sorting find the longest increasing subsequence?

Question

According to Wikipedia (link), patience sort finds the longest increasing subsequence of a given sequence. Lets say the longest increasing subsequence of seq has length correct(seq)

Patience sort works like this:

Parameters: A sequence of integers called seq
Output: A number between 0 and the length of seq. Lets call it patienceSort(seq)
Algorithm (in Python):

def patienceSort(seq):
    piles = []
    for el in seq:
        for i in range(len(piles)):
            # If there is a pile with a strictly greater element on top,
            # place current element on that pile
            if piles[i][-1] > el:
                piles[i].append(el)
                break
        # if there is no such pile, create a new one
        else:
            piles.append([el])
    return len(piles)

What I've understood:

(I) We can guarantee that at every time the top of piles (piles[i][-1]) is ordered in increasing order.

(II) For numbers in the same pile: Numbers are ordered...

(II.1) ... by time (first one in the pile came first)

(II.2) ... by value (first one in the pile has highest value)

(III) The numbers on top of the piles are not necessarily an increasing sequence within seq

(IV) The right pile is always the latest one that was created

Example for (III):

      37
20    38
30    39
40    40
50    70
pile1 pile2
seq = [50,40,70,30,40, 39,38,37,20]
[20,37] is not an increasing sequence in seq

For each card (which is not on the first pile), you can store a pointer to the top of the pile before when you add it to the pile. This way, you can get an increasing sequence by following the pointers and inverting the list. So:

patienceSort(seq) <= correct(seq)

Question

Why is patienceSort(seq) >= correct(seq)

Answer 1

With the two insights from (II) it is obvious that no increasing sequence can use two cards (or more) from one pile.

This means: No increasing sequence can use more cards then the number of piles. But patience sort returns the number of piles.

So: patienceSort(seq) >= correct(seq)

See also: Slides from Princeton with pictures.

Thank you very much Yuval Filmus :-)