One Dimensional Ants

Ants on a stick may only march left or right, all with the same constant speed. They never stop, short of falling off the stick. When two ants bump into each other they bounce and reverse their directions.

Assume 25 ants were randomly dropped on a 1 meter stick and move with constant speed of 1 m/sec. 25 ants create real commotion marching this way and that way, bouncing off each other, and occasionally falling off the stick.

  1. Is this certain that eventually all the ants will fall off the stick?
  2. If so, in the worst case scenario, how long it may take for the stick to become ant free?

For a solitary ant it may take anywhere from 0 to 100 seconds to reach an edge of the stick and then fall off, depending on its position and orientation. The worst case scenario occurs when the ant is originally located at one edge of the stick and is oriented towards the other end. Generally speaking, the exact time for the stick to become ant free depends on the distribution of ants and their initial orientations. The worst case scenario, for a given number of ants, is such a configuration of their initial locations and orientations that results in the longest time for all of them fall off the stick.

Solution

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

P. Winkler [Mind-Benders, pp 36-38, A Lifetime, pp 177-180] lists the sources of the problem and offers an enlightening solution.

Solution

Imagine that each ant carries a flag. Let's stipulate that when they bump into each other, in addition to reversing their directions, they exchange the flags. The usefulness of the introduction of the flags stems from the following observations:

  • There are no flagless ants as there are no antless flags, implying that a stick is ant free if and when it is flag free, and vice versa.
  • The flags never change their (individual) directions and each moves with the given constant speed towards the end of the stick at which it is doomed to fall off.

    • Since within 100 seconds each flag will have fallen off the stick, 100 seconds is the longest for the stick to become flag (and hence ant) free.

    A slight modification of the solution may be even more suggestive. Instead of endowing each ant with a flag, let's paint each with a special kind of individual colors. Let's request that at the time of a meeting the two ants exchange their colors. Since otherwise the ants are indistinguishable, observing their movements one would never see them bumping into each other. The ants will just go through each other as if each was the only ant around.

    References

    1. P. Winkler, The Adventure of Ant Alice, in A Lifetime of Puzzles, E. D. Demaine et all (eds), A K Peters, 2008
    2. P. Winkler, Mathematical Mind-Benders, A K Peters, 2007

    Related material
    Read more...

    Worst-Case Scenario

  • More than half of the integers from {1, 2, ..., 2n}
  • Chvatal's Art Gallery Theorem
  • I. Sharygin's Problem of Criminal Ministers
  • Mastermind: an interactive gizmo

    • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71220326