Next, the solution to the puzzle posed in the first column. The indiatimes.com link to the first column is here. You can view the puzzle itself on the indiatimes site. What follows is the full, unabridged, complete solution to the puzzle and so, if you are just here to check your answer to the puzzle, the answer we were looking for was just this : 0.5. Three characters to type out. That's all, folks.
No, wait. We wouldn't be a real puzzle column if we didn't post the correct solution to the puzzle as well as a proof of correctness, and so what follows is a detailed derivation of the solution and an accompanying proof.
In solving this puzzle, let us see if we can derive a solution for the problem when there are N passengers on Chandrayaan for some arbitrary N greater than 2. In investigating the solution to the problem, we can start off by trying to solve this for N = 2.
When there are just two passengers on the shuttle, the solution is simple. The first passenger may pick either Seat #1 or Seat #2. If the passenger picks Seat #1, then you, as the final passenger, will get your seat for sure (probability = 1.0). If the passenger picks Seat #2, then you will certainly not get your seat (probability = 0.0). So, the probability for N = 2 is clearly one half.
Let us now see if we can solve it for N = 3. When there are three passengers, the first passenger may pick Seat #1, #2 or #3 with equal probability. If the passenger picks Seat #1, then again, you, as the final passenger, will get your seat for sure (probability = 1.0) since Passenger 2 will pick Seat #2. If the passenger picks Seat #3, then you will certainly not get your seat (probability = 0.0). The average of that is again one half. Now, that leaves the case where Passenger #1 picks Seat #2. If this happens, Passenger #2 is now in the position of either picking Seat #1 or Seat #3. But this situation is exactly the same as that where N = 2. The probability of you, as the final passenger, getting your seat is half. So, the net probability is (1/3*1.0 + 1/3*0.0 + 1/3*0.5) = 0.5. So, again the probability of N = 3 is one half.
Now, assume general N = Z. Using Strong Induction, we assume that the probability for any N less than Z is one half. So, again, the first passenger walks in. There are three distinct possibilities for what happens next (three Events) :
(a) Passenger #1 picks Seat #1;
(b) Passenger #1 picks Seat #Z;
(c) Passenger #1 picks some other seat.
Under Event (a), Passenger #1 picks Seat #1. Passenger #2 through #Z-1 pick their respective seats. So you, as passenger #Z, will get your seat for sure (probability = 1.0). Under Event (b), Passenger #1 has already taken your seat and so you will NOT get that seat for sure (probability = 0.0). These two events are equally likely and the average probability is one half. Now, consier Event (c). If Passenger #1 picks Seat #X whre X is not equal to 1 or Z, then all passengers up to #X will pick their assigned seats. Passenger #X can now pick either Seat #1 or pick one of the remaining seats (choice is random). Now, if we renumber the original seat to be seat #X, then we have the exact same set up as before (exactly isomorphous). We know by the inductive hypothesis that this probability is half. So, probability under Event (c) is exactly one half as well. This means that the net probability of you, as Passenger #Z, getting your seat is exactly one half as well.
QED.
-+-
Update (Mar 21): Updated the post a bit.
-+-
Update (Mar 21): Updated the post a bit.
