Lemmings on a Ledge


I got this problem from Rustan Leino, who was told it by Vladislav Shcherbina.

Manos Kapritsos told me a more elegant solution than I had come up with, so I wrote up his solution with a slight modification.


A ledge is 1 meter long. On it are $N$ lemmings. Each lemming travels along the ledge at a constant speed of 1 meter/minute. A lemming continues in the same direction until it either falls off the ledge or it collides with another lemming. If two lemmings collide, they both immediately change their directions. Initially, the lemmings have arbitrary starting positions and starting directions. What's the longest time that may elapse before all lemmings have fallen off the ledge?

Solution     Reveal