by Jonathan Kujawa
The mathematics of the everyday is often surprisingly deep and difficult. John Conway famously uses the departmental lounge of the Princeton mathematics department as his office. He claims to spend his days playing games and doing nothing with whomever happens to be in the lounge, but his conversations about seemingly mundane questions has led to no end of delightful and deep mathematics. Chatting with math folks about the everyday can quickly lead to undiscovered country.
A much loved tradition among any group of mathematicians is talking math in the department lounge at afternoon tea. Nearly every department has such a tea. Some are once a week, some every day. There may or may not be cookies. What is certain, though, is that everyone from the retired emeriti to undergraduate students are welcome to stop by for a revitalizing beverage and a chat. More often than not it leads to talk about interesting math. You can begin to imagine why John Conway hangs out in the Princeton math lounge and Alfréd Rényi joked “A mathematician is a device for turning coffee into theorems” [1].
You might think the conversation swirls around the work of the latest winners of the Abel prize or folks trying to impress by describing the deep results of their morning's efforts. There is some of that. But just as often the conversation turns into an energetic discussion about the mathematics of the everyday. Several years ago I was involved in a heated discussion about whether or not the election laws of the State of Georgia could allow for a certain local election to become caught in an endless loop of runoff votes. The local media's description of the electoral rules seemed to allow this absurdity. Of course the argument could easily be resolved with a quick Google search, but where's the fun in that? A search was done, but not until all possible scenarios were thoroughly thrashed out and a nickel wagered.
My colleagues, Kimball Martin and Ravi Shankar, asked themselves an innocuous tea-time question: “How often should you clean your room?” Easy to ask, the question is surprisingly difficult to solve. In math problems come in three flavors: so easy as to be not very interesting, so hard as to be unsolvable, and the sweet spot in the middle where the questions are both interesting and solvable. When to clean your room turns out to be a question of the third kind.
To have a chance in using math to answer a question you have to figure out what you're really asking. In the end Kimball and Ravi settled on the following scenario. Imagine you have a collection of objects which are all in order. For example, they could be books in alphabetical order on a shelf. After you've read a book you drop it on the large pile of books on your desk. From time to time you think of a book you'd like to read (let's say you'd like to reread the collected works of Shel Silverstein). Since the books in the pile are in no particular order, if the Shel Silverstein book is in the pile you have to go through the books one by one to find it. It's much faster to find the book when it's on the shelf. On the other hand, it takes time to put the books back on the shelf.
For example, if you only have a one book it's no faster to find it on the shelf then on the pile. Time spent reshelving is completely wasted. On the other hand, the Stockholm Public Library has over two million volumes and even a relatively small pile of, say, fifty thousand books would be a librarian's nightmare.
There is a clear tension between time wasted because of the messiness of the pile and time wasted by putting books back on the shelves. To be as efficient as possible we'll need to find the optimum balance between the two [2]. In short, a little messiness is good, a lot is bad, and somewhere in between is when should you clean your room.
There are still known unknowns which need to be settled. Kimball and Ravi make all of these things precise under various possible scenarios [3]. They make reasonable although not entirely realistic assumptions which we'll discuss in a moment. The upshot is this: If you want to minimize the amount of time spent on searching and cleanup, then there is an optimal size to the pile of books. If it's too small, you're spending too much time cleaning up. If it's too large, then you're spending too much time searching through the unordered pile. That is, once your pile exceeds this optimal size, you should stop and reshelve all the books.
Kimball and Ravi write mopt for the number of books in the optimally sized book pile. They compute this optimal number for up to 35 books:
But what if you run the Stockholm Public Library? You have over two million books in your collection. How large of a pile should you allow?
Kimball and Ravi prove what should be called the Felix-Oscar Theorem [5]: If you have n books, then optimal pile size for a library of n books is no more than 4log2(n) books. That is, you should clean up once the pile of unshelved books contains more than 4log2(n) books.
If you're run the Stockholm Library this means you should clean up once there are 84 unshelved books. Since the Stockholm Library doesn't have huge pile of books at their front desk somebody must be wasting their time reshelving.
If you were paying attention, you'll notice that Kimball and Ravi say the pile should be no more than 4log2(n). The actual optimal pile size may be smaller. Based on other estimates and computer calculations they conjecture that the real answer is that you should allow 3log2(n) books in an optimally sized discard pile. At the moment nobody knows for sure and it is still an open question to calculate the optimal pile size.
What about those known unknowns? First off we have to make precise how you decide which book you'd like to read. In real life you might like to read Shel Silverstein every summer, while you only read James Joyce's Ulysses once (and Gravity's Rainbow is just there to impress people). For simplicity's sake Kimball and Ravi assumed you are equally interested in all books and you simply decide at random which one to read. In the last section of the paper they discuss other scenarios and make a convincing argument that the equal interest model gives you the largest possible optimal pile. That is, whatever your personal preferences may be, the discard pile should never be larger than the one they propose.
The next big question is how do you go about searching for a book? Do you always correctly remember before you start to search whether the book is on the shelf or in the pile? Or are you like that guy in Memento and have to start your search with no memories whatsoever? And how do you calculate the amount of time it takes to search and to clean up? Kimball and Ravi give several plausible scenarios and consider what happens in each case. But they don't consider all reasonable possibilities and there is still lots of interesting math to be uncovered.
How is it that in all his time hanging out in the Princeton lounge John Conway never pondered this classic tea-time question? We can't say but it may be worth noting that one reason Dr. Conway works in the lounge is that his office was declared a hazard by the fire marshal due to the mountains of clutter.
As Shel Silverstein put it in “Messy Room”:
Whosever room this is should be ashamed!
His underwear is hanging on the lamp.
His raincoat is there in the overstuffed chair,
And the chair is becoming quite mucky and damp.
His workbook is wedged in the window,
His sweater’s been thrown on the floor.
His scarf and one ski are beneath the TV,
And his pants have been carelessly hung on the door.
His books are all jammed in the closet,
His vest has been left in the hall.
A lizard named Ed is asleep in his bed,
And his smelly old sock has been stuck to the wall.
Whosever room this is should be ashamed!
Donald or Robert or Willie or–
Huh? You say it’s mine? Oh, dear,
I knew it looked familiar!
[1] To which Paul Turán is said to have added the corollary, “Weak coffee is suitable only for lemmas”.
[2] Of course time spent doing these calculations is not counted. Time spent on math is never a waste :-).
[3] If you'd like to see the gory details you can find the paper on Kimball's webpage.
[4] The other two rows are the result of slightly different scenarios and, in any case, you see they give nearly the same answer as mopt.
[5] The Felix and Oscar of Neil Simon, of Jack Lemmon and Walter Mattheu, and of Tony Randall and Jack Klugman. Not the modern and excruciating Matthew Perry vehicle.
[6] From Beth Rhodes' delightfully illustrated book based upon Shel Silverstein's poem “Messy Room”. You can find it here.