The hidden mathematics of bathrooms

From the xkcd blog: urinal protocol vulnerability.

The basic premise here is the following: there's a long row of urinals (n of them), and a line of men who want to use them. The first man picks a urinal at the end. Each man after that picks one of the urinals which is the furthest from any of the occupied urinals. Nobody ever leaves. How many men have to show up before one of them will be forced into using a urinal adjacent to one that's already occupied? Call this number f(n).

You might think that f(n)/n approaches some limit, but it doesn't; it oscillates between 1/3 and 1/2 based on the fractional part of log₂ n. If n = 2^k + 1 then this "greedy" algorithm for filling the urinals works and every other urinal gets filled: f(2^k + 1) = 2^k-1 + 1. If n = 3 x 2^k-1 + 1 then the worst possible thing happens and only every third urinal gets filled, and f(3 x 2^k-1 + 1) = 2^k-1 + 1. (Yes, that's the same number, and the function's constant in between.) f(5) = f(6) = f(7) = 3, f(9) = ... = f(13) = 5, and so on.) Oscillations like this -- periodic in the logarithm of the problem size -- happen a lot in problems involving binary trees counted by the number of nodes. Still, it was a bit surprising to see this, because I'd never thought about the problem in the case of "unphysically" large n.

Exercise for the reader: invent a mathematically equivalent version of this problem that doesn't involve urinals.