Source

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.

Problem

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

One minute, by the following reasoning.

Imagine that each lemming starts with a unique nametag, and that whenever two lemmings collide they exchange nametags. In this scenario, each nametag will never change direction, and will continually move at 1 meter/minute until it falls off the ledge. So, the longest time a nametag might spend before falling off the ledge is one minute. Since there's always a one-to-one correspondence between lemmings and nametags, the same goes for each lemming.