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.

Finally the name of this blog makes sense!

Advertisements

1/100?

The nice thing about the riddle is that this is not the answer. Try the case of three passengers and you’ll see that you don’t get 1/3.

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.

Exactly!

If p(n) is the desired probability for n passengers, then I get the following recursion,

p(n)=(1/n)(1+p(n-1)+p(n-2)+…+p(2))

p(2) = 1/2

p(3) = 1/3+1/6

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.

nice! (the recursion indeed works out to be 1/2 for all n..)