To recap (using latex this time), we had:
1) #1 accidentally sits in his own seat. Probability of this is 1/5.
2) #1 sits in 4's seat. 2 and 3 sit in their own seats, 4 selects either #5's seat (which we don't want) or #1's seat. Probability = 1/5 * 1/2.
3) #1 picks #3.
3.1) #3 picks #1 - 1/5 * 1/3
3.2) #3 picks #4, and #4 picks #1 - 1/5 * 1/3* 1/2
4) #1 picks #2.
4.1) #2 picks #1 - 1/5 * 1/4
4.2) #2 picks #4, #4 picks #1 - 1/5 *1/4 * 1/2
4.3) #2 picks #3, #3 picks #1. 1/5*1/4*1/3
4.4) #2 picks #3, #3 picks #4, #4 picks #1 - 1/5 * 1/4 * 1/3 * 1/2
A pattern begins to emerge:
and so we can conjecture:
I don't want to prove the relation (I don't think there's much use in doing that, when the relation just comes out of logicking where everybody must sit in each cases, anyway) but it makes it easy to prove that every one of these = 1/2 which is the heart of what P(n) should prove (i.e., P(n) = 1/2 is really what we're trying to prove). But keeping the n's around lends itself much better to complete induction.
The base case is the n = 2 case. (Not only is n = 1 not really relevant for the problem, it doesn't fit the pattern so we want to exclude it.)
Though we've presented cases n = 3 through 5, I'm not going to bother doing the rest and will happily let complete induction take care of that for me:
Inductive step: P(j) holds:
Then for P(n) it's pretty straightforward:
From the inductive step, all the previous probabilities are = 1/2, so the term in the brackets therefore becomes 1/2 * (n - 2) = n - 2 / 2
Combining:
So P(n) holds as well.
Of course, in real life this means nothing, because sure, you might be sitting in your own seat and sure, it might be a nice window seat, but your happiness on the flight is ultimately governed by a factor inversely proportional to your distance from crying babies...
No comments:
Post a Comment