## 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.

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.

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“.

This entry was posted in Riddles and tagged , . Bookmark the permalink.

### 19 Responses to Two Math Riddles

1. Rani says:

Funny, riddle #2 appeared here just two months ago:
http://weblog.fortnow.com/2008/08/math-problems-on-vacation.html

2. yuliy says:

Gil, I think both of the riddles are in Pete Winkler’s book(s) of _puzzles_: in fact, he has many variations of the one on ants…

3. Hey, Gil. Why didn’t you tell me you’d joined the ranks of the math-bloggers! Thanks for the pingback.

The first riddle has a variation I first heard from Alireza back at Yale. A particularly inept group of soldiers is in a line, at attention. They’re told to “right-face”, but they don’t know right from left. Some turn right, while others turn left.

If two neighboring soldiers are facing each other, each assumes he got the direction wrong, and about-faces to look the other way. Of course, this sometimes brings two new soldiers face-to-face. The process repeats until they all stop turning. How can you tell before they start turning which direction each soldier will face at the end?

I really love the first riddle. It seems very hard to solve when first hearing it, and it has a 1-line solution. There is a variant that I came up with but was never able to solve: Now the ants are billiard balls, and they’re moving in straight lines on a 1 meter by 1 meter board. When two balls hit each other, they bounce in the standard billiard-ball way. Each ball has speed of 1 meter per second. What is the starting configuration that maximizes the time that it takes for all of the balls to fall off the board?

5. jhusdhui says:

Elad: what’s the difference in the 2d version? 2 billiard balls, elastically bouncing, will behave as if they pass through each other (assuming they’re points).

It’s been discussed here:

6. jhusdhui says:

Thought I would add a link (also a shameless plug) to a nice extension of the ant riddle:
http://almostsurely.wordpress.com/2008/10/24/more-riddles/

7. Gil Kalai says:

Dear Rani, Yuliy, John, elad and Jhusdhui, many thanks for the remarks and interesting links.

Ori (jhusdhui), thanks, you’re right. Somehow I thought that they don’t act like they pass through each other.

You might be interested in a discussion about the influence of votes in the Israeli Kenesset. I explicitly suggested we call Ori to settle the differences. The discussion is available by clicking on my name here.

10. Sweet post, I have a confession to make though… I think i’m a true puzzle addict. I can’t even make love without fantasizing about sudoku or crosswords 😦

11. Sid Hollander says:

I was watching some ants on several meter sticks and saw different results.
Stick #1- Two ants on 10 cm and 90 cm not facing each other.- Both off in 6 seconds
Stick #2- Two ants on very close to 50 facing or not – Both off in about 30 seconds
Stick #3- Two ants on 10 cm and 90 cm facing each other.-Both off in 54 seconds
Stick #4- One ant anywhere but an end- off in < 1 minute

12. 777 says:

Hi Gil, those are very fun!

I solved the second riddle in a slightly different way:
If Joe happen to sit in his own seat then everyone’s happy; if Joe happen to sit in Jim’s seat, then Jim will not have his seat at the end. Those two events happen with the same probability of 1/100. If none of the two seats are taken then whenever someone finds their seat occupied, the following two events will end the story: 1) if he takes Joe’s seat, we have a closed loop of cyclic permutation of serval people, all the later passengers, including Jim, will take their own seat; 2) if he takes Jim’s seat, then we are done because Jim will not have his seat. 1) and 2) are equally likely to occur at any given time. Hence at the end it will be exactly 1/2 chance that Jim’s seat is taken.

13. Brooke W says:

I think for this riddle Joe’s chances are 50% of having his seat taken. Awesome riddle. Had me thinking for a bit. Let me know if you like this riddle I wanted to share: 5+5+5=550

• Gil Kalai says:

Dear Brooke, yes, very nice.