A Riddle

So for my slog problem, what I really want to do is talk about the relationship between context-free grammars, context-sensitive grammars, and regular expressions, but I have a lot of notes for those and I don't know if I'll have time to type up those notes.

In the absence of that, here's something a friend and I were discussing...

Consider a plane consisting of 100 seats. Unfortunately, the airline company which is probably American Airlines has managed to botch up all the boarding passes, so nobody who boards the plane has anything printed under the 'seat' field on their boarding pass. If they don't know their seat number, they have been instructed to select at random. Luckily, most people recall their original seat number, and everybody on the plane is extremely non-confrontational (maybe they're Canadian): if they approach their seat and find someone already sitting in it, they won't make a fuss, they merely select another seat at random.

If the first person who boards the plane is the only one who forgets where he's sitting, and therefore picks a seat at random, what is the probability that the last passenger to board will be sitting in his originally-assigned seat?




I initially worked this problem out using induction, but perhaps not formally, I just sort of went on a case-by-case basis.

n = 1: Nothing interesting happens if there is only one seat on the plane. :)

n = 2: Two seats on the plane. The first guy picks at random, so he's got a 50% chance of picking the seat that was his own completely by accident. This means that the chance the final boarder will sit in his original seat is 50%, since there's really no other seat for him to select.

n = 3: Three seats. The first guy picks at random and now we have three cases...
A) He picks his own seat (probability 1/3). Then the second passenger boards and remembers his own seat, and sits in it. And also the final passenger boards and sits in his own seat.
B) He picks the final boarder's seat (probability 1/3 too). We don't want this option.
C) He picks not his own seat, but not the final boarder's. Here, we have two subcases...
C.1) He picks the second-last boarder's seat. The second-last boarder then has to decide at random because his seat is already taken. There are two seats remaining. He can pick the seat that was the first boarder's (1/2 chance of this) or he can pick the seat that was the final boarder's (1/2 chance of this). We don't want the latter option.

So the chance that the final boarder selects his own seat = 1/3 + 1/3*1/2 = 1/2 or 50%.

Hm.

n = 4: Four seats on a plane. First guy picks at random.
A) 1/4 chance he picks his own seat perfectly by accident.
B) 1/4 chance he picks the final boarder's
C) 1/4 chance he picks the second last guy's seat (#3). #2 therefore sits in his own seat, because he finds it empty when he boards, but #3 will pick at random. Like in n = 3 we have two subcases:
C.1) #3 picks #4's seat. (We don't want this one)
C.2) #3 picks #1's seat.
D) 1/4 chance he picks the second guy's seat (#2). #2 picks at random and has three seats to choose from which means three subcases...
D.1) 1/3 chance he picks #1. then #3 and #4 sit in their own original seats.
D.2) 1/3 chance he picks #3's seat. #3 then also selects randomly. There are two seats remaining, so 1/2 chance he picks #1's seat, and 1/2 chance he picks #4's.
D.3) 1/3 chance that #2 picks #4's seat.

Summing this case up the chance that #4 sits in his own seat is 1/4 + 1/4*1/2 + 1/4*1/3*1/2 + 1/4*1/3
which equals 1/2 = 50%. Curiouser and curiouser.

More in a bit, I have to finish this and latex it up.