Interview Question: Musical Chairs for Quants

Sample Question #276 (probability brainteaser)
 
This is a classic…  There are n people, labeled 1-n, and n chairs, also labeled 1-n. The n people choose chairs in order 1 – n. The first person (labeled "1") picks out a chair randomly and sits in it. Each of the other n-1 people will try to sit in the chair with the same label; if that seat is not available, the person will pick a random available chair.
 
What’s the probability that the last person (labeled "n") will get the right seat, i.e., the seat labeled "n"?
 
Advertisements
This entry was posted in Sample Qs. Bookmark the permalink.

8 Responses to Interview Question: Musical Chairs for Quants

  1. Brett says:

    ANSWER
     
    This is a favorite on the quant interview circuit. I’ll provide a brief sketch.
     
    It’s important to recognize that there’s nothing magical about the "first" person who picks a random chair. After person 1, any person whose correspondingly labeled seat is unavailable automatically becomes the new "person 1." If you continue with this logic, it’s fairly easy to see that the final answer is 1/2.

  2. Brett says:

    Actually, you also need the following series of probability: P(person 2 not picking seat 2)=1/n, P(person 3 not picking seat 3)=1/(n-1), etc. Then calculate P(person n not picking seat n) by induction.

  3. quantyst says:

    In another website this problem was portrayed in a setting
    of one hundred airplane passengers among whom the first passenger was crazy and
    would pick his/her seat quite randomly (with uniform probability).  Any subsequent passenger will pick (using
    nominal pronoun) his seat if available, otherwise would pick randomly any
    available seat.  The question was to find
    the probability that the last passenger would end up with his own seat.  The problem was titled “The Crazy Airplane
    Passenger”.  I solved the problem in two
    ways, the long way and the short way.

    Here’s one way to conceptualize this problem for the short
    solution.  Imagine an urn containing n (=
    100) balls, of which one is yellow, another is red, and the remaining n – 2 (= 98)
    are blue.  Now, as often as need be, a
    ball is randomly drawn (with uniform probability) from the urn until a yellow
    ball or a red ball is drawn, at which point in time the experiment ends.  If the ball drawn is blue, then a random
    number of blue balls are pulled out of the urn and discarded, and then the
    experiment continues.  The question is:  what is the probability of this experiment
    ending by drawing a red ball (before a yellow ball)?  The answer obviously is ½ as the yellow ball
    and the red ball are symmetric relative to each other, or, to put it
    differently, neither of them has any special advantage over the other in being
    picked.

    If you compare the preceding paragraph with the musical
    chair or the crazy airplane passenger problem, you will see that they are
    essentially the same.  You may imagine
    the yellow ball representing the passenger/seat #1 and the red ball representing
    passenger/seat #n ( = 100), and the blue balls representing the other passengers/seats.  The case of the first passenger randomly
    picking seat #1 is like the case of the first ball drawn being the yellow ball,
    in which case the last passenger is guaranteed to pick his own seat.  The case of the first passenger randomly
    picking seat #n ( =100) is like the first ball drawn being the red ball, in
    which case the last passenger is guaranteed to NOT pick his own seat but seat
    #1.  And if the first passenger picks
    seat #k for k < n (= 100), then the k-th passenger acts among the remaining
    seats like the first passenger did among the original n ( = 100) seats.  All the parallels are there to be seen
    between the urn of balls and the passengers cases.

    The longer way to do this problem is to first derive a recursive
    equation and then to solve it.  The
    longer method is omitted here.   

  4. jary says:

    Good question. hope to see it in my interview.

  5. Sachin says:

    Since there are n people. The answer should also be true for a special case of this npeople n chairs problem. Let n=2 then there are two people 1 and 2. and two chairs.Now the problem is easy. P( second person getting the 2 chair) = 1/2 since he has only one way of doing that.NOw we need to check if this 2 in the denominator of the answer 1/2 is the n or value 2. SO we also think for n=3.Create the probability tree. the order of choices make by person 1 ,2 & 3 are as follows123132231213312321out of this six possbilities 2 have 3rd person choosing the 3rd chair.. hence the P( 3rd person choosing the 3rd chair) = 2/6=1/3so by induction we have solved it to for n people P(nth person getting the nth chair) = 1/nOther method : we want to find the probability to get the nth person taking the nth chair so the nth person can choose the nth chair in 1 way.. rest all the n-1 people can choose n-1 chairs in (n-1)! ways.. total ways of choosing n chairs by n people = n! waysso the P( nth person choosing the nth chair) = (n-1)!/n! = 1/n

  6. quantyst says:

    The fifth answer (dated 4/19/2008) is incorrect.The problem as stated is unfortunately a bit unclear.  That might explain why someone may misunderstand it.  The re-statement of the problem given by the third poster (dated 3/26/2008) in terms of the passengers waiting to be seated in a plane is much clearer.  The answer given by both the third poster (dated 3/26/2008) and the first poster (dated 3/26/2008) is correct.  The correct answer is indeed one-half.To be cute about it, the answer one-half is only correct for n>1.  In case n=1, the first and the last persons are one and the same.  So, the randomness is inoperative, and the last person picks his/her seat with probability 1.  But, this is academic, and as noted, a cute, remark.  The conceptualization given by the third poster (who is quantyst, who forgot to mention it the first time around), is very helpful in seeing the rather simplicity of the problem and its solution.  Another way to conceptualize the problem is to pose the question:  What is the probability of getting a 5 before a 3 when rolling a die repeatedly?  The answer is of course one-half.  It turns out that this problem is a close variant of the plane passengers problem, the balls in an urn problem, or the musical chairs problem.  Unlike the preceding, in rolling a die we don’t get rid of the numbers 1, 2, 4, 6, every time they come up.  So, they may come up again and again in subsequent rolls. Anyway, the parallels are there to be seen.

  7. Yanis Ps. says:

    Quant Career is right on the money. Intuition tells you that, by symmetry, the probability has to be =1.Being a Ph.D. in Pure Math I have come to the point that, while intuition is one of the most important tools a mathematician should carry with them at all times, everything needs to be proved formally. ( Even though in this case intuition could be accepted as a proof- "Symmetry" is the key word here).In any case, here is my mathematical solution:The answer to the problem should (typically) depend on n.So let A_n denote this probability.To calculate this probability has to do with what the first person’s choice is.If the first person chooses the the right chair the probability of the n^th person picking the n^th chair is =1. If he chooses the n^th chair then the probability of the n^th person picking the n^th chair is =0. If he chooses any of the rest n-2 chairs in the middle then this process starts anew. Therefore we have:A_n=1/n*1+1/n*0+1/n(A_2+A_3+…+A_{n-1}) for all n>2Calculating A_2 and A_3 by hand yields the same answer =1/2It’s not hard to then verify that A_n=1/2 for all n. ( or at least that 1/2 is one solution to the recursive formula above but then again the solution has to be unique as long as some initial conditions are in place). Q.E.D. Yanis

  8. Unknown says:

    I would just like to note that the probability tree in comment 5 includes two impossible cases: 132 and 312.  If the second chair is available, the second player must take it.  This leads to the expected solution of 1/2. 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s