For a less chaotic analogy than Lego, let’s suppose you’re grappling with your movie collection, though books or objects around a room would work equally well. In a paper on the arXiv, Kimball Martin and Krishnan Shankar of the University of Oklahoma codified the mathematics of tidying by creating a system of two zones. One zone is completely organised—your shelves of alphabetised DVDs—and the other is a disordered hodgepodge—a pile of recently watched films next to the television.
Each night, you decide on a film at random. You hunt down the right DVD, watch the movie, and then chuck it on the pile before going to bed. Eventually you decide the pile is too big and put it all back into the shelves, whereupon the process starts afresh.
Martin and Shankar pose a simple question. If you want to minimise the time spent finding movies without wasting time tidying up too often, how big should you let the pile grow, if at all?
Let’s think about finding the movies. Depending on whether you watched the movie recently, you’ve got to look for it in either the shelves or the pile. Crucially, though, there’s a big difference in efficiency between the two.Searching the shelves is efficient. You know they’re in alphabetical order, so you do a binary search. Start in the middle and check if you’ve over- or under-shot the right place. If you’ve over-shot, you move to half-way between the start and the middle; if you’ve under-shot, you move half-way between the middle and the end. You then check again and go left or right within that half, and so-on, until you land on the right DVD. Very few checks are needed to find the movie; with a 100-strong collection, you’ll never need to look at more than seven discs.
On the other hand, searching the pile is inefficient. You know nothing about its organisation, so you have to examine each disc one by one. Sometimes you’ll be lucky and find your film straight away, but sometimes you’ll be unlucky and it’s the last one you check. On average you’ll look through half the discs each time, so once you’ve piled up 14 of your collection of 100 movies, the heap becomes just as slow to search through as the 86 remaining on the shelves.
Since the pile is so bad to search, then, shouldn’t you should always tidy up? Actually, no.
Suppose you can remember whether a movie is in the pile or not. Now, the more movies there are in the pile, the fewer left on the shelves, so searching the shelves gets faster. But provided the pile is small enough, looking through it is at least as fast as searching the shelves. You know where to look thanks to your basic memory, so a small pile guarantees you a time saving: either it’s on the shelves, which take less time to search than when they’re full, or it’s in the pile, which takes less time to search than the shelves. It’s win–win.
We mustn’t forget the effort of cleaning up the pile, though. Putting back a single movie amounts to a binary search of the shelves for its proper location. For a modest pile, this takes roughly the same amount of time per movie (because the number on the shelves doesn’t change by a big fraction), so the cleanup effort associated with each DVD is the same irrespective of the pile’s height.
This means that all you care about are the time-saving benefits of having the pile. So, if you can remember things, you should be a little messy.But what if you can’t remember anything? This time it’s not clear that untidiness is beneficial. A big pile is always too slow to search, so let’s again assume the pile is small. It’s best to look through the shelves first, since your movie is most likely to be there, but if it turns out to be in the pile then you’ve put in a lot of effort without reward. So does the benefit of having fewer movies in the shelves outweigh the extra effort of finding a movie that turns out to be in the pile?
In fact, Martin and Shankar proved that even if you have zero memory, it’s still beneficial to keep a modest heap. Lazy goldfish everywhere, rejoice!
It’s a harder problem to pin down exactly how tall you’re allowed to let the ghastly pile grow. At the modest extreme, they worked out that if you’re someone with a good memory but no more than eight movies—a globetrotting academic, perhaps?—then you should only tidy up once everything’s in the pile. In other words, you should be super lazy.The calculations get trickier for larger numbers, but they do give a rough upper limit on your permissible sloth: for 100 DVDs, you shouldn’t let the pile grow more than 26 discs high. Bigger collections don’t do much better, though. If you own 1000 DVDs, you’re only allowed a pile 40 high, and for a huge collection of 10,000 movies the magic number is a mere 53.* Even so, any allowed laziness is surely a good thing.
So there you have it. To live your life to the optimal full, mathematics says you shouldn’t always tidy up. So put on another movie, break out the Lego, and embrace the authors’ final acknowledgement: “We also thank our parents for never making us clean up our rooms.” Both you and your kids will be very happy.
* For N DVDs, the limit is 4log2N.