Only half a chance :(

Hey,
Seems like the last week problem sent you'll a bit hay-wire. I got two correct entries from Kapil Garg and Pradeep Sharma, but the logic/proof given by them were not pretty convincing. Pradeep Sharma, our very own Pandit, came really very close and almost cracked the problem.

Now, lets consider the condition when there are k people in the queue ( k>=2 ). By a little hand calculation you can see that probability that kth person gets kth seat kor k = 2 , is 0.5 . Again, for k = 3 , the possible configurations are (1,2,3) , ( 2,1,3) , (3,1,2) , (3,2,1 ). Here also, we have the probability to be 0.5. You may convince youself for k = 4 ,5 and so on, till you patience permits.
Here we can generalise the answer to be 0.5 for each k >=2 . Now lets see a rigid proof for this.
We use Mathematical Induction:

Lets say, F ( n ) denotes the probability that nth person sits in nth seat, the total number of people in the queue being n.
Also, lets say F ( n ) = 0.5 for all n >=2 .
Now we prove this for F ( n + 1 ) .

For the last person to sit on his seat, the first person must sit on any seat except n. Let she sits on seat k.
Now all the passengers from 2 to k-1 sit on their respective sits, with k , k + 1 , k + 2 ... n still remaining, the seats vacant being 1,k+1,k+2,...n .
This is similar to the initial case, just that the kth person is equivalent to drunk girl with his seat number being 1. Hence we have a recursive relation like:

F ( n + 1 ) = 1/(n+1) + sum for k = 2 to n { 1 / ( n + 1 ) * [F ( n + 1 - ( k -1 ) - 1 )] } .

The first 1/(n+1) means the girl sits on 1st seat. The other one is summation means the person sits on kth seat and now we remain with N + 1 - 1 - ( k - 1) people to be seated.

each F ( k ) is 1/2 and hence you can get the answer as 1 / 2.

While you convince yourself about the above solution, you can mail me for clarifications. I will soon have a new post ( Infact, I am working on it rite now :) ) .

Cheers,
Vivek
nitkkr.vivek@gmail.com