Child Care at STOC 2018 + Riddle

I’ve been asked to post the following message by the STOC 2018 local arrangements chairs – Ilias Diakonikolas and David Kempe.

We are pleased to announce that we will provide pooled, subsidized
child care at STOC 2018. The cost will be $40 per day per child for
regular conference attendees, and $20 per day per child for students.
For more detailed information, including how to register for STOC 2018
childcare, see http://acm-stoc.org/stoc2018/childcare.html

To have something slightly mathematical in this post, here’s a cute riddle: 100 passengers enter an airplane one at a time. The plane contains 100 seats and every passanger has a ticket with a seat number. The first passanger lost his ticket, so he randomly chooses a seat (uniformly). When any other passanger enters, if their seat is available they use it, and otherwise they randomly choose one of the available seats (uniformly). What is the probability that the last passanger got their correct seat.

seats

Finally the name of this blog makes sense!

Advertisements

7 thoughts on “Child Care at STOC 2018 + Riddle

      • Ah I see the question is whether the passengers that are pushed out of their seat will form a cycle before the last passenger arrives. Indeed sayan’s recursion is correct since if the first passenger chooses the seat of the k-th passenger (in arrival order) then it’s basically the same game on n-k passengers and the first passenger’s seat plus the n-k-1 seats of passengers k+1 and onwards.

  1. I’ve heard this riddle before, I think, and the trick was to think of the passengers as identical (sort of like that riddle with the ants on a ruler) so that it makes no difference if we change the rules so that when a boarding passenger find his/her seat occupied, he/she kicks the occupier out (so the occupier is always the passenger who boarded first), who then chooses another seat at random. If the first passenger chooses his/her own seat at any point, then the last passenger’s seat is free when he/she boards; if the first passenger chooses the last passenger’s seat at any point, then it isn’t. So the probability is 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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s