A Puzzle For You All

[TheNewNo2]

This is this week's Riddler from FiveThirtyEight, which I here present in a more railway-esque format.

You are last in a queue of 100 people to board a train at a terminus. Your carriage has 100 seats, each of which is reserved by someone in the queue. The first person in the door doesn't care about seat reservations, and just sits in a random seat. Every person after that will sit in their own seat if it's free, but, being British, are too polite to do more than tut if their seat is taken, and if unable to take their own seat will choose a random empty seat.

When you board the train, there will be exactly one free seat - what is the chance that it's the one you reserved?

It's a nice little brain-teaser.

 

[DarloRich]

I am off to buffet - will you watch my seat?

 

[Minilad]

I always get a seat on my train. And I don't have to reserve it either

 

[GrimsbyPacer]

99%, as the random sitter has 100 possible seats to sit in.
Is that correct?

Edit, could 'the first person through the door' who's so selfish they sit where they like, also be a queue jumper from last in the queue??

Edit 2, it can't be the queue jumper as only 1 seat is empty, one empty seat means everyone is sitting in the right place when you board.

Edit 3, there's a 1% chance the selfish person will sit in the correct seat... if they don't and 98 more people will get on, one of which has a 1 in 99 to 1 in 2 chance to sit in your seat depending on when the person with no seat gets on. So there's chance varying between 50% and almost zero most of the time... but it it's a 100% chance 1% of the time.

Edit 4, The Correct Answer is 1%, if there's 100 seats and 99 people sitting where-ever they want, only 1 time in every 100 will your seat be free.

 

[DaleCooper]

I think it's slightly better than 1/3 perhaps 0.34.

 

[brianthebrain]

1% chance?

 

[tony_mac]

99%, as the random sitter has 100 possible seats to sit in.

I made it 99/100 as well, but with more complicated working out.
(Actually, my working-out was mostly superfluous, but I think the answer is still correct)

 

[GB]

50/50 at a guess but I was never any good at these things!

 

[Gutfright]

I think it's slightly better than 1/3 perhaps 0.34.

This is close to a rough estimate I came out with.

I haven't done all the maths, but... if you assume there's a 1% chance on average that each individual passenger will take your seat, then the odds of your reserved seat being free would be (99/100)^99, which comes out to slightly less than 0.37

 

[Busaholic]

Then the train gets cancelled and there's a mad rush to join another train which has 200 on already. None of the 100 get a seat, except of course Miriam Margoyles, who is last on to the train, and is offered a seat by 99 of the 100 seated passengers: she throws a bottle of water over the recalcitrant seat-hogger, who sells his story to the Sun.
Is this the correct answer?

 

[90019]

None - the first person sat in your reserved seat.

 

[Dent]

None - the first person sat in your reserved seat.

Where did you get that from? The description does not make any such statement.
--- old post above --- --- new post below ---
It's actually 50%.

There are only two seats you could possibly end up with: yours or the first person's. All the other seats will be taken either by the right person or someone who got there before them.

At every stage where someone could take one of these two seats they are equally likely to take either of them, so they are both equally likely to be left when you get there.

 

[St Rollox]

I wouldn't try sitting on seat that's been reserved by a Glaswegian.

 

[PaxVobiscum]

None - the first person sat in your reserved seat.

Where did you get that from? The description does not make any such statement.

Just bitter experience talking - he must have encountered the same student who made a bee line for mine at Aberystywth.

(I let him live).

 

[bb21]

This is indeed a little puzzling. If I calculate correctly, the probability is indeed 0.5, amazingly, although I am sure there is a simpler explanation than one I came up with, given how many clever people there are on this forum. That said I have yet to see a convincing argument so far. My approach was proof by induction.

 

[DaleCooper]

I've just noticed the odd wording of the question:

When you board the train, there will be exactly one free seat - what is the chance that it's the one you reserved?

There could hardly be a non-integer number of seats left could there?

 

[GrimsbyPacer]

This is indeed a little puzzling. If I calculate correctly, the probability is indeed 0.5, amazingly, although I am sure there is a simpler explanation than one I came up with, given how many clever people there are on this forum. That said I have yet to see a convincing argument so far. My approach was proof by induction.

How can it be?
Remember if the first person sits in the wrong seat (99 times out of 100), so does the person who reserved that seat and so on.
Look at it this way seat 99 is taken by the first person, seats 2-98 are taken correctly, and the 99th passenger can't sit in seat 99, the passenger will either sit in 100 (your seat), or 1 (first person's) very well.

But... if the first persom sat in seat 2, the 2nd person have a high chance (98 out of 99) of sitting in someone elses seat again, causing more movements and by the time your on between 2 & 99 passengers have sat in the wrong place. 50% chance is the best chance assuming only the 99th is affected. But if the 2nd to 10th passengers are the only ones all in the wrong place, then they could only sit in the first person's seat, each others, and yours, lowering the chance.

 

[fishquinn]

There could hardly be a non-integer number of seats left could there?

You obviously haven't travelled on a Northern 150/1!

 

[D6975]

deleted

 

[TheNewNo2]

I've just noticed the odd wording of the question:

There could hardly be a non-integer number of seats left could there?

I used to be a mathematician, it's just the way we say things. Saying "there is one seat free" could be implied as meaning "there is at least one seat free", so adding "exactly" removes any ambiguity.

 

[DaleCooper]

There is one piece of information missing from the question, the position of my seat relative to the entrance door. The further it is from the door the better are my chances of finding it unoccupied.

 

[Eeveevolve]

50/50 at a guess but I was never any good at these things!

I call that correct aswell. You do or you dont. 50/50

 

[DaleCooper]

I call that correct aswell. You do or you dont. 50/50

But not necessarily the same number of "dos" as "don'ts".

 

[Eeveevolve]

But not necessarily the same number of "dos" as "don'ts".

But it is something Kirk or Spock would use to confuse a computer.

 

[bb21]

There is one piece of information missing from the question, the position of my seat relative to the entrance door. The further it is from the door the better are my chances of finding it unoccupied.

In these problems, it is assumed that the probability of randomly choosing any seat is the same, otherwise the problem would not be solvable.

I will post my solution later today when I get home.

 

[crispy1978]

Good puzzle. I can think of a highly convoluted way of working it out, but there must be a quicker way!

What I always tend to do with problems like this is simplify it down - so try it with 4 seats, and see how you work it out. Then move to 5 and see if you can spot the pattern...

Going to have my tea, but will have a think and work it out!
--- old post above --- --- new post below ---
50%.

Basically, the only thing that matters is whether the first person sits in their seat or my seat, i.e. 50%. Anything else is irrelevant. That will be the same whether person 1 sits in person 2 or person 99's seat. So, it is still 50/50 whether your seat is taken or not. Probably not explained very well, but I know what I mean!!!

 

[DaleCooper]

Basically, the only thing that matters is whether the first person sits in their seat or my seat, i.e. 50%. Anything else is irrelevant. That will be the same whether person 1 sits in person 2 or person 99's seat. So, it is still 50/50 whether your seat is taken or not. Probably not explained very well, but I know what I mean!!!

What if the first person sits in a seat other than their own or yours? In that case the person whose seat they occupy could sit in yours.

 

[bb21]

So here is my solution. I know I said I would post it last night but was too knackered to bother at the end. The solution assumes that the reader understands the basics of probability.

----------

Let's start with two people. For argument's sake let's label the first person P1, and yourself P2, with P1's allocated seat S1, and yours S2. As the first person to board, P1 gets to choose his seat at random, so obviously the probability of picking S1 is 1/2, hence the probability of not picking S2, thereby leaving P2 with his allocated seat 1/2.

Probability of P2 ending up with S2:
1/2

----------

Now let's consider the situation with 3 people. P1 gets to choose his seat at random, so the probability of choosing S1 is 1/3. In that case, P2 has to choose S2, so the conditional probability of P3 (you) ending up with S3 in that scenario is 1.

Of course P1 could equally have chosen S3, at a probability of 1/3. In that case, the conditional probability of P3 ending up with S3 is 0.

We now have to consider the scenario of P1 choosing S2, at a probability of 1/3. In this particular case, P2 has two choices, since his allocated seat is gone. He could choose either S1 or S3 equally at a conditional probability of 1/2 for either. Look at it another way, this is equivalent to the situation where we have only two people, the first person having a random choice of seats. We know that the probability of you ending up with your allocated seat in that situation is 1/2, should we consider the case with only two people in isolation of the condition that P1 already chose S2.

Probability of P3 ending up with S3:
1/3 x 1 + 1/3 x 0 + 1/3 x 1/2 = 1/2

----------

Let's look at the situation with four people next. P1 has a 1/4 probability of choosing S1, in which case P4 ending up with S4 has conditional probability of 1. Likewise P1 has a 1/4 probability of choosing S4, leaving the conditional probability of P4 ending up with S4 0.

Should P1 choose S2, we end up with the equivalent situation of the previous scenario, where with 3 people, the first person is given a free choice. We know that in that case, the probability of the last person ending up with his allocated seat is 1/2.

Should P1 choose S3, P2 will have to sit in S2, and we end up with the equivalent situation of having only two people (P3 and P4), with the first person (P3) having a free choice. We also know from previous analysis that the probability of the latter person (P4) ending up with his allocated seat is 1/2.

Probability of P4 ending up with S4:
1/4 x 1 + 1/4 x 0 + 1/4 x 1/2 + 1/4 x 1/2 = 1/2

----------

From the above, hopefully a pattern should emerge. I won't write out the complete proof by induction with the "n" and "n + 1".

Hence the answer, whatever the number of people, is actually 1/2.

 

[GrimsbyPacer]

Or...
P1 sits in S2, P2 sits in S3, P3 sits in either your seat or the P1 seat.
Yes that is 50% assuming the first person sits in the wrong seat, 99/100 chance, the 1% of the time where P1 sits in the correct place ruin the calculation though.

 

[bb21]

Are you talking about the case with 3 people, or the one with 100 people?
--- old post above --- --- new post below ---

It's actually 50%.

There are only two seats you could possibly end up with: yours or the first person's. All the other seats will be taken either by the right person or someone who got there before them.

At every stage where someone could take one of these two seats they are equally likely to take either of them, so they are both equally likely to be left when you get there.

I like your logic.

The first part is obviously correct. The second, while fairly intuitive, I struggle to justify it mathematically.

But I think you are correct, having thought about it again. I think crispy1978 was talking along the same lines.

A fine problem indeed.