Partial Hoarder

A couple of years ago, one of the strings on my guitar broke.  New strings mixed with old don't sound great, so I bought a new set.  Or, I thought I did.  I never got around to putting the strings on, or possibly never got around to buying them.  I can't remember.  Recently, I decided it was time to put strings back on my guitar and start playing again.  I've searched high and low, but I haven't found the strings yet, suggesting that perhaps I never bought them.

Many of my things are stored away in boxes, and in looking for the strings, I managed to consolidate the contents into fewer boxes than I started out with.  But what to do with the extra boxes?  Throw them out? Never!

In my search, I also happened across a book that I had been looking for since last year.  As I tried to find space for the book on my shelf, I had to face the reality that I have let my books get out of order.

The newly emptied boxes and the disordered bookshelf got me thinking about the following two problems.

The Russian Box Problem

Suppose you move a lot, on average once a year, say.  After you've moved enough times, you tire of having to hunt down boxes for the next move, so you start hoarding boxes.  I've got some pretty sweet tomato boxes that I've had for so long that they might be considered antiques by now.  There are trade offs to keeping all of these boxes, though.  You save yourself the trouble of having to find new ones, but create the problem of storing them.  Space is limited, so you want to store them in the most efficient way possible.  One way to save space is by nesting boxes, putting boxes inside boxes inside boxes, etc.  Call a set of nested boxes a Russian Box, after the famous Russian dolls.

How can you sort your boxes into the smallest possible number of Russian boxes?  That is, what is the minimum number of Russian boxes needed so that each box in the given set is in exactly one Russian box.

The answer gives one possible way to minimize the amount of space needed to store the boxes.

(There may still some way to divide the boxes into more Russian boxes than the minimum number, but uses less space.  Also, if the small boxes are significantly smaller than the large ones, then it might be possible to save even more space by putting multiple un-nested small boxes inside the large box.)

The Russian Books Problem

This is not about books in the Russian language, but rather about arranging books like the boxes in the previous section.

When arranging books on a bookshelf one may place aesthetics over alphabet and decide to sort books according to size.  It might be desirable, then, to place books so that they are decreasing (or at least non-increasing) in size from one end to the other.  We'll assume that the thickness of the book, i.e. number of pages, doesn't matter, but the height and width of the covers do, because it is only the covers that are making contact when they are on the bookshelf.

Thus, what we want to do is organize the books so that one book is smaller in both height and width than the book before it.  Unfortunately for people who want to sort their books this way, publishers publish books in a range of sizes and shapes, so that one book may be taller but narrower than another book.  In that case, it is impossible to have the desired arrangement.

If it is impossible, one might ask for the next best thing.  What is the next best thing?  That is subjective, I suppose.  One possible answer is to ask for an ordering of the books with the smallest number of violations.  By violations here, I mean the number of places in which a book is larger in either dimension (or both dimensions) than the book preceding it.

Perhaps to some people, it would seem unnecessary to insist that books be ordered by both their height and width, since you mainly see the front of the book when it's on the shelf.  But when it comes time to move again and put those books back into the boxes that were the subject of the first section, I find it handy to arrange the books in decreasing order of size (or increasing, if you turn the box around).

The Russian box problem and the Russian book problem have a similar flavour (thus the chosen similarity in the names).  Boxes are placed inside larger boxes, and books are placed beside (and to the right, say) larger books.  The problems are not exactly the same, though.  For one thing, we are ordering the boxes according to 3 different dimensions, length, width, and height, while books are ordered according to only 2, height and width.  For another thing, you cannot put one box inside the other if both have the same size, but you can put two books side by side even if they have the same height and width.  Thirdly, there is more freedom when trying to fit one box into another.  If a box doesn't fit upright, it might still fit it is rotated onto one of its sides.  A book on the other hand, will always be placed so that its binding at the front of the bookshelf.

Despite these differences, however, both problems are essentially just different versions of the same type of problem.  Both of the desired relations can be used to define what is called a partial order. 

Everyone is familiar with the concept of order for numbers.  We say that 2 is bigger than 3, for example, or 1 is smaller than 100.  More generally, given any pair of distinct numbers, one of them will be smaller than the other.

Less familiar is the notion of a partial order, though it's not too hard to find examples from common experiences.  For example, ancestry defines a partial order.  Your parents are your ancestors, and you are your children's ancestor.  On the other hand, you are (probably) not your cousin's ancestor nor are they yours, even though you have at least one common ancestor.  People who are not related to you at all don't even enter the picture.  So some pairs of people can be ordered by ancestry, but some cannot.  Thus we say that ordering people by ancestry is a partial order, because it only partially orders (possibly perished) people.  You may have some foods that you prefer over others, whereas you like some other foods just as much.  Thus, your food preferences might also define a partial order.

Being able to nest one box inside another defines a partial ordering on the boxes.  A book being smaller in both height and width than another defines a partial ordering on the books.

Partially ordered sets have been studied in depth by mathematicians.  In fact, it's a subject of ongoing research.  Although the research is not done in the language of boxes and books, one of the topics of interest for the people who study these things is essentially the same as solving the box and book problems stated above.  It's been a while since I've studied the topic in any depth myself, so I don't know offhand how hard it would be in general to find a solution.

What's remarkable (to me) is that I never set out to find a ``real life'' application for these mathematical ideas.  The problems that I laid out earlier were simply problems that I wanted to solve.  The box problem was new, but I had thought about the book problem a few times in the past.  I felt there was a mathematical aspect to them, which is why I eventually decided to write them down in the first place.  But I didn't know exactly how mathematics would enter the picture.  It was only after I started writing that I realized I had seen problems in this area before.