Gurmeet.Net
Puzzles

Ants in a Circle

Puzzle

Suppose n ants are placed on a circle with a diameter of one meter. Each ant location is chosen independently, uniformly at random. An ant chooses between clockwise or anti-clockwise direction, uniformly at random, and starts scampering along the circle. All ants move at the same speed: one meter per second. When two ants bump into each other, they reverse their direction of travel. One of the ants is named Alice. What is the probability that Alice returns to the same point as she started, one minute after the ants start their scampering?

Source

The Puzzle Toad at CMU.

Solution

Please see Solution (PDF).

Previous Puzzle: Coins in a Row

30 coins of arbitrary denominations are laid out in a row. Simran and Tavleen alternately pick one of the two coins at the ends of the row so as to pick up as much money as possible. If Simran makes the first move, could Tavleen ever collect more money than Simran, if Simran makes the optimal choices?

Next Puzzle: Fifteen Sum

Alice and Bob take turns to pick numbers from 1 thru 9, without replacement. The first to possess three distinct numbers that sum to 15 wins. Does Alice have a winning strategy?

9 Nov 2012
© Copyright 2008—2017, Gurmeet Manku.