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 log2 n. If n = 2k + 1 then this "greedy" algorithm for filling the urinals works and every other urinal gets filled: f(2k + 1) = 2k-1 + 1. If n = 3 x 2k-1 + 1 then the worst possible thing happens and only every third urinal gets filled, and f(3 x 2k-1 + 1) = 2k-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.
Subscribe to:
Post Comments (Atom)
6 comments:
Would particles with same charge constrained to 1D have the same premise? I guess you'd have "infinitely many urinals" in that situation, though.
A bunch of guys parallel parking their cars in marked spaces along a street. They want to leave as much space as possible so there's no risk of scratching, and nobody will even try to park in the space next o an existing car.
Actually n=2^k and n=2^k+1 achieve the optimal f(n)/n = 1/2 as well.
Note that 4 = 3+1 is both optimal and worst :)
Oops, I meant n=2^k and n=2^k+2.
Choosing seats on the New York City subway. It's not exactly equivalent, because people sometimes shift seats when people get up, and sometimes people slide down fractional seats, and sometimes there are couples or families who want to sit next to each other, but the basic principle seems the same.
If each urinator went to a urinal two down from the previous one, the community would achieve a near-optimal packing. I think that people don't do this because the awkwardness doesn't drop suddenly to zero once the urinal distance is two, but decays gradually.
Post a Comment