Two Math Riddles

Usually I am not particularly good at telling math riddles or solving them, and I was not planning on presenting math riddles here. But these days, when mathematical blogs break new ground and enter uncharted territories, let me make an exception and tell you two riddles.

1) (Told to me by Sergiu Hart; taken from a MSRI news-teller to the best of my memory.)

You have a 1 meter long (one ant thin) wooden stick and you put on it n ants in arbitrary locations. Each ant is facing one end of the stick. The ants move 1 meter per minute and when two ants meet they both start moving in the opposite directions. If an ant reaches an end of the stick it falls from it.

After how much time you can be sure that no ants will remain on the stick?

2) (Told to me (with the solution) most recently by Sasha Barvinok, who heard the problem on “Car talk“.)

An airplane has 100 seats, and 100 passengers were assigned seats. The first passenger, ‘Joe,’ enters the plane and rather than sitting in his assigned place, he sits in a random place. The next passengers come one by one and every passenger sits in his assigned seat if it is empty, and in a random empty seat if his seat is already taken. What is the probability that the last passenger ‘Jim’ will sit in his assigned seat?

If you want to solve these riddles on your own do not read the rest of this entry.

 

In our case the stick is very very very thin – ant thin.

 

 

Answer to 1) The answer is one minute.

Consider a different story with magical ants such that when two ants meet they simply pass each other and continue moving. In this case every ant will reach the end of the stick and fall down in at most one minute. Regard the ants as indistinguishable particles. Now you cannot distinguish between the situation in the first version and that of the second version.  

Answer to 2) The answer is 1/2. 

Consider a similar story with aggressive non-polite passengers. After Joe took his random seat, every passanger that sees his seat taken bumps Joe from the seat, sits in his assigned seat, and poor Joe goes on to sit in another random seat. Note that when k+1 passengers are sitting down all but Joe sit in their assigned places and Joe sits in a random place among his assigned place and the places of the remaining passengers.  Therefore, when the last passenger enters, his place is empty with probability 1/2 and occupied by Joe with probability 1/2. 

Ahh but now consider the passengers as indistinguishable. The occupied seats in the first version of the story with polite passengers will be the same as in the second version!

Here is the original presentation and solution of the problem in “Car talk”. The problem and its solution was described also in John Amstrong’s blog “the Unapologetic Mathematician,” it was offered also, as Rani commented,  in “computational complexity”, and, as Yuliy remarked, you can find both these riddles in Pete Winkler’s two beautiful books. Further nice riddles can be found in the probablog “almost surely“.