«
»

Puzzle : Kissa Kursi Ka ( A matter of a seat )

Well,

I have read this puzzle a couple of times but never did I put my mind to it. Once deepanjan and I sat together to solve it. We both came up with two different solution, both correct. My laziness made me procrastinate posting the solution here. Anyways, now that I am on it, let me directly go to the puzzle.

Problem : There is an airplane and 100 passengers are given boarding pass for the same. The first passenger lost his boarding pass and he did not remember the seat number assigned to him. So, when this first passenger boards the plane he chooses one seat uniformly randomly. Rest of the passengers, board the plane in the sequence of 2 to 100. If a passenger finds his seat vacant, he will sit there, if not, he chooses a vacant seat uniformly randomly. The question is, what is the probability that the last person ( 100th in this case ) will find his seat vacant when he boards the plane?
Number 100 has nothing to do with the puzzle and we can as well state that there are n passengers.

Solution 1 : Well, I have come up with this solution. I started initially with 2,3,4,5 passengers and found the probability manually. So I conjectured that the probability is 1/2 in all the cases. Now, the task remains is to prove that it is indeed the case for any n. I remembered my favorite professor sundar vishwanathan and a very powerful mathematical tool that he taught us to use in a very elegant way. And mathematical induction indeed helped me proving my conjecture.

Base case : n=2.

Clearly, the first person sits in the 2nd person’s seat with probability 1/2. So the last person ( 2nd person in this case ) finds his seat vacant with the probability 1/2.

Hypothesis : For any n \geq 2 probability that the last person finds his seat vacant is 1/2.

Induction Step : Let there be n+1 passengers.

Let P(A_{n+1}) = probability that n+1 th person finds his seat vacant when there are total n+1 seats.

Let P(B) = probability that at least one person of the first n persons ( say k th person ) found his seat vacant hence he sat in his own seat.

P(A_{n+1}) = P(A_{n+1} \cap B ) + P(A_{n+1} \cap \neg B)

P (A_{n+1}) = P(B) P(A_{n+1}|B) + P(\neg B)P(A_{n+1} | \neg B)

It is clear that P(A_{n+1}| \neg B) is 1/2. Because, when none of the first n person find their seat vacant, it must be the case that 1st person seats in 2nd seat, 2nd person seats in 3rd seat and so on. Because they arrive in sequence, if 1st person seats in 3rd seat, then 2nd person would find his seat vacant. Or if 2nd person seats in 1st seat, then 3rd person would find his seat vacant. So after n-1 person take their seats, only two seat ( 1st and n+1 th ) remains vacant. Now the n th person chooses the 1st seat with the probability 1/2 which is precisely the probability that the last person ( n+1 th ) person would find his seat vacant given that none of the first n could find their seat vacant.

P(A_{n+1}|B) = P(A_n) = 1/2. The reason is that, if at least one person of the first n persons could find his seat, then we can view it as if k-th seat was already taken when the first person boarded the plane. We can view it like that because we are given that event B has happened and now we have to find the probability of all other events that are occurring. So original problem of n+1 person and n+1 seats reduces to n person and n seats for which we can use induction hypothesis.

Let P(B) = x.

So, P(A_{n+1}) = (1/2)x + (1/2) (1-x) = 1/2 ( x + 1 - x ) = 1/2.
So irrespective of how many persons and seats are there, the probability remains constant.

Solution 2 : Deepanjan came up with this solution. Given n person, his solution looks like this.

Let P_i denote the fact that i-th person does not find his seat vacant.

P_2 = 1/n because the first person chooses the 2nd seat with probability 1/n.

P_3 = 1/n + P_2 ( 1/(n-1) ) = 1/n + (1/n)(1/(n-1)) = 1/(n-1) because, either first person choose the 3rd seat with the probability 1/2 or the 2nd person find his seat taken and chooses 3rd seat with probability 1/(n-1).

Similarly, P_4 = 1/n + P_2 (1/(n-1)) + P_3 (1/(n-2)) = P_3 + P_3(1/(n-2)) = 1/(n-1) + 1/((n-1)(n-2)) = 1/(n-2)

In general, it should be easy to see that for P_i = 1/(n-i + 2 ). Hence, for the last person when i=n we have P_n = 1/(n-n+2) = 1/2. The probability that n-th person finds his seat vacant would be 1 – (1/2) = 1/2.

–Saurabh Joshi

Tags: , ,

This entry was posted on May 28, 2008 at 6:48 am and is filed under math, puzzle. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to “Puzzle : Kissa Kursi Ka ( A matter of a seat )”

  1. Increasing or decreasing subsequence « Me, Myself and Mathematics Says:
    May 30, 2008 at 9:41 am | Reply

    […] found this problem here. Solution to the second puzzle given in that post is already posted in Kissa Kursi Ka. I tried a couple of approaches to solve the first one but could not succeed. Finally, Deepanjan […]

  2. vikas Says:
    June 3, 2008 at 7:00 am | Reply

    A simpler proof would be if you observe that the last person will either find his seat empty or the seat assigned to passenger 1. Any other seat if empty till last would have already been taken by the person to whom it was assigned.
    So now among these two possibilities, any person before the last would have no preference for either of the two so the probability that any of them is vacant till the last has to be same which is 1/2

  3. Amit Chandel Says:
    October 7, 2008 at 2:31 pm | Reply

    Let us denote seat numbered i as S_i, and person numbered j as P_j

    @Vikas
    if I consider 3 passangers only then it can happen that P_1 sits at S_2, and P_2 sit at S_3. So P_3 will neither see P_1 on his seat nor an empty seat. So I am sorry I cannot buy your argument.

    I have also applied induction to arrive at 1/2 in this way:
    Let f(n) denote the probability that the last person will see his seat empty given there are n passangers.
    Base Case: n=2 f(2) = 1/2 . Obvious!
    Now we have to prove that f(n) = 1/2 assuming f(m) = 1/2 for all 1 < m < n. Here we go.

    P_n can see his seat empty in two cases:
    Case #1: P_1 sits on S_1. Prob(Case #1) = 1/n
    Case #2: P_1 sits neither on S_1 nor on S_n. He chooses S_k where 1 < k < n.
    If he sits on S_k, when P_k comes, he will see S_1 empty, P_2 on S_2, P_3 on S_3, …., and P_1 on S_k. Lets ignore seats from 2 to k and passangers P_1 to P_(k-1). So we removed k-1 seats and k-1 passangers. Lets re-number the seats and passangers reducing all by k, except S_1. We get the same problem with k passangers and k seats.
    So probability of last person getting his seat in this situation = (prob of case#2 happening) * (probability of last person getting his seat given case#2 i.e. under modified problem )
    = ( P_1 neither sit on S_1 not on S_n) * f(k) where 1 < k < n
    = ( (n-2)/n ) * (1/2) = (n-2)/(2n)

    hence f(n) = 1/n + (n-2)/2n = 1/2.

  4. Saurabh Joshi Says:
    October 8, 2008 at 5:51 am | Reply

    @amit,
    if you read carefully vikas’ argument is write. It’s upto you to buy the argument or not, but if not then you should produce a counter-example which you did not.

Leave a comment