Two Puzzles

1. Given a sequence of r*s+1 distinct integers (r>=1, s>=1) prove that there exists either an increasing subsequence of length r+1 or a decreasing subsequence of length s+1.
Its a nice puzzle having a clean elegant solution. Though it is not really an aha! puzzle yet the solution does not involve much mathematical trickery. The way I got the solution was to first fix r at 2. So then we are looking at sequences of length 2s+1. Once you find the solution to this, it is easy to generalize it to arbitrary r. But I think this is a tough puzzle and I felt really good when I could solve it :)

2. There are 100 seats in an airplane and 100 passengers each of whom has been assigned a boarding pass which contains there seat number. They board the plane one by one. Unfortunately the first passenger has lost his boarding pass, so he sits on a random seat. Every subsequent passenger, if he finds his seat vacant takes it otherwise sits randomly on any of the empty seats. So what is the probability that the last passenger finds his seat vacant?
I had heard this puzzle couple of years back and am not sure whether I was able to solve it then. When I reread it again yesterday, I could not recall the solution but I did remember that there is a simple elegant solution to it. After some thought and much frustration I finally got the answer and felt relieved more than anything else. But the solution is nice. You can also generalize it to find probability of kth passenger finding his seat vacant.