## Tuesday, August 02, 2005

Oh, heck, open for solutions. Go wild.

At a terminal gate at Calgary airport, you have 100 young, male members of the CPC, standing patiently in line to board their 100-seat plane where they will fly to Parliament Hill to demonstrate against same-sex marriage because, as we all know, allowing same-sex marriage would cheapen the sanctity of their sitting in the dark of their parents' basement, snarfing down Cheeto-s and masturbating to online, photoshopped pictures of Rachel Marsden. But I digress. Onward.

Every passenger has a boarding pass with a pre-assigned seat number but, as the very first passenger makes his way down the JetWay, he loses his pass. Because of this, upon entering the plane, he simply picks a random seat and sits down.

Subsequently, each passenger, upon entering, goes to his pre-assigned seat and, if it's empty, sits there. If someone is already in it, he randomly picks an empty seat and sits there instead. And so on, and so on.

What are the odds that the very last passenger to board will actually get to sit in his original, pre-assigned seat?

dAVE said...

dammit! I was hoping to see some answers this morning. I saw this yesterday, and said "oh this is easy". Then I thought about it some and said...hmmm...
I got nothing.

AWeb said...

The probability is 1/2. It's a recursive problem, and for any # of passengers the answer is the same. There is a 1/100 chance everyone gets their correct seat (crazy guy picks own seat at random), and also 1/100 chance crazy gut sits in seat 100, and the problem is over.

Otherwise, it comes down to, at some point, a passenger having to choose a random seat because the crazy guy is in his. When this occurs, the passenger is equally likely to choose seat 100 (we 'lose'), or the crazy guy seat (everyone else gets own seat afterwards). A passenger faced with this choice is equally likely to choose either. If he chooses neither (picks another random seat), this just passes a similar choice to another passenger later.

CC said...

Very good. In fact, regardless of the number of passengers, there are only two possible outcomes, each of them equally likely:

1) the last passenger gets his own seat, or
2) the last passenger gets the seat that was originally assigned to the very first passenger who lost his boarding pass.

Surprisingly, there are no other possibilities. See the solution here.

dAVE said...

oh.
duh.