The first floor men’s room in Carnegie Mellon’s Baker Hall has four urinals. Every time I visited this facility I remarked the pointlessness of the fourth urinal: as the universal law of the men’s room mandates a buffer of at least one urinal, a bank of four urinals can only accommodate two men. The construction company might as well have saved some money and installed only three.
This observation alone would not be worth writing about; recently, however, I discovered that generalizing it results in a mathematical system with some very interesting properties. The system is based on three axioms:
Axiom 1: The first man who enters the men’s room must select an end urinal.
Axiom 2: Any subsequent entrant must select the urinal that maximizes the space between him and his nearest neighbor.
Axiom 3: A buffer of at least one urinal must be maintained between any two men.
These axioms create a mapping y =U(x) between the number of actual urinals (x) and the number of effective urinals (y). The pairs (1, 1) and (2, 1) are trivial, and we’ve already seen the pairs (3, 2) and (4, 2). It’s easy to see that adding a fifth urinal increases the number of effective urinals to three, but that a sixth is superfluous; thus (5, 3) and (6, 3).
A first guess at the function that produces this mapping might be U(x) = ceiling((x+1)/2), where ceiling(x) is the smallest integer not less than x (see the Wikipedia entry on floor and ceiling functions). This function produces the mapping (7, 4), which seems to make sense; if there are seven urinals, men can occupy urinals 1, 3, 5, and 7.
Such an arrangement, however, would violate Axiom 2! The first two men to enter the toilet will take urinals 1 and 7; what about the third? In order to maximize the space between himself and his nearest neighbor, he must take urinal 4. The poor fourth man must either wait or piss in the sink, as there is no way to create the requisite 1-urinal buffer. Thus, the efficient arrangement (1, 3, 5, 7) is impossible.
Consider the situation after the third man enters the room, in which urinals 1, 4, and 7 are occupied. We can treat this as two banks of four urinals, with urinal 4 serving as the right endpoint for one bank and the left endpoint for the other. With this in mind, we can define the Urinal Mapping Function recursively:
U(1) = 1
U(2) = 1
U(3) = 2
for x > 3, U(x) = U(ceiling((x+1)/2)) + U(floor((x+1)/2)) – 1
I used this function to generate the mapping out to x = 10,000; here’s the function depicted graphically:
The linear increases followed by long flat plateaus constitute an interesting pattern (fractal?). Observe the first 26 values of U(x): 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10. Notice that there are two twos, three threes, five fives, and nine nines. All other values (except for 1) appear exactly once. This pattern holds true for the remainder of the sequence; for example, any number of urinals between 4,097 and 6,115 yields 2,049 effective urinals. I therefore submit the following hypotheses:
Hypothesis 1: U is a surjection.
Hypothesis 2: each value U(x) appears either once or exactly U(x) times.
Hypothesis 3: If a value U(x) > 2 appears more than once, it is odd.
I don’t know how to prove these hypotheses or why they might be true. I am also at a loss to identify what properties all repeated values of U(x) share. I’ll leave these problems to our mathematically inclined readers.
Another way to look at the problem is to ask what fraction of actual urinals are effective urinals. This is easily done by examining the behavior of U(x)/x, which is illustrated below:
We see that the ratio oscillates between a maximum of just over 1/2 – specifically, (x + 1)/ 2 – and a minimum of floor(x/3) + 1. Looking at the local maxima and minima, two concepts suggest themselves:
Definition: A number of urinals n is maximally efficient if U(n) > U(n-1).
Definition: A number of urinals n is maximally inefficient if U(n) = U(n-1) and U(n) < U(n+1).
In other words, a number of urinals is maximally efficient if removing one would reduce the number of effective urinals, and a number of urinals is maximally inefficient if adding one would increase the number of effective urinals but removing one would not make a difference. 1, 3, 5, 8, 9, and 17 are maximally efficient, while 2, 4, 7, 13, and 25 are maximally inefficient. I’ll leave it to readers to figure out the properties of maximally efficient and maximally inefficient numbers.
I’m excited to have stumbled upon an apparently new mathematical system; the sequence generated by the Urinal Mapping Function is not found in the On-Line Encyclopedia of Integer Sequences. It seems to be a very rich and interesting system; I suspect that the properties presented here are merely the tip of the iceberg. I will continue to ponder the matter, and I encourage readers to present their insights in the comments section.