Lego Brickbox

At the holidays, many children received special promotional “Brick Boxes” from Lego, which may be taken back to the store and filled from the brick repositories on the back wall in the store. After Christmas, one child, “Norah,” saw one of her friends, “Tyler,” meticulously build a shape to fit exactly in his box. She asked me, “How much better do you think that Tyler did by building an exact shape than I did just by tossing what I wanted into the box?” Like many things, this turned out to be a much simpler question to ask than to answer! For the remainder of the article, we will use the natural unit of “Lego cubes” (LC), which are the size of a 1×1 Lego brick, as shown in Figure 1. So, a 2×4 brick has an area of 8LC, and so on.

First, an easy problem: The promotional brickbox is 11x11x9 LC, and has a capacity of 1,089 squares. Packing square bricks into a square box is very easy. This turns out to be the only easy thing about this problem.

Computing the distribution of random bricks tossed into a box is difficult, because each layer is dependent on the one below it. Also, real children do things that real children do, such as shake the box to make the Legos settle. A few minutes with a paper and pencil convinced me that this was not the proper approach. So, I decided to simulate. Now, computer simulation has some of the same difficulties – imagine playing a 3-D version of Tetris – but fortunately, this is not the only way to simulate. It is possible, for small problems, to simulate the system itself, which entails actual Legos, actual children and an actual box. And here’s where I stopped being in control and the problem took over.

I went to the store and purchased a (non-promotional) Lego brickbox. This one is different than the promotional version, because it is a large round cup, and now things get really interesting. Because while packing square Legos in a square box is easy, packing square Legos in a round cup is hard. My idea was to have a set of Lego bricks, 1×1, 1×4, 2×2 and 2×4 of different colors for a group of children to toss into the promotional (square) box. We could then determine what an “average” random fill of bricks might be. I didn’t concern myself too much with optimally packing the cup; I reasoned that it was so much larger than the box (946 vs. 670 cubic centimeters) that I wouldn’t need to worry too much about optimizing. Naïvely, based solely on volume, one might estimate that the large cup holds 1,678 bricks. This is a naïve measure because it simply divides the volume of the box by the volume of the bricks.

I turned out to be dead wrong; my brick purchase that haphazardly filled the cup only filled the box (when optimally stacked) a little more than half way! This is because it’s difficult to pack squares into a round container, even more so when you don’t try.

When analyzing putting bricks in round cups, there are two approaches one may take: The first is to consider how many squares may be packed in a circle in any arrangement, which is known as Square Packing [1]. The other approach is to ask how many integer lattice points may be contained in a circle of radius r. We usually think of building Legos with a lattice because we want to build layers on top of layers, so we choose this method. It turns out that a similar problem was studied by Gauss and is known as Gauss’ Circle Problem [2]. The key idea is to realize that the number of lattice points inside a square is the number pairs of integers (m,n) such that (insert image 6)which is, of course, the equation of a circle. In calculus we just take the limit as the area of the boxes tends to zero and arrive at the well known. However, requiring makes the problem much more complicated. Fortunately, Hilbert et al. come to the rescue, and the number of lattice points in the circle may be found by evaluating:

Where is the Gauss bracket or Floor function, which means “round down to the nearest integer.” If you restrict yourself to integer values of r, this formula will generate a named sequence [3]. Here we have used non-integer values for the radius of the circle because the cup does not have an exact radius in terms ofour foundational unit (bricks). This will still tend to over-estimate the number of bricks that will fit in a cup because it assumes that the lattice points have zero dimensions, and we know that our bricks have finite dimension; therefore, the calculations that follow are an upper bound.

This equation may be readily implemented in Excel. Because there is a “floor” function on the summands, for our purposes need only be evaluated up to. The base of the cup has a radius of approximately 4.4 LC and has a theoretical maximum of 61 bricks. I was able to achieve a base layer of 58, but this is probably because I’m not a great builder. The top of the cup has a radius of approximately 6 LC and has a theoretical maximum of 113 Bricks. I was able to achieve 98 in my build. Using these and assuming a linear trend in the cup (the sides of the cup look smooth and straight), we estimate that a theoretical maximum of 1,364 Lego bricks could fit in the round cup, with a more likely number being approximately 1,250. See Figure 4 for three different calculations of bricks-per-layer.

So the round cup holds about 200 more bricks than the box if you take the time to pack it. Real Lego enthusiasts use a greedy heuristic to fill their cups, putting large pieces in first, then filling the rest of the space with smaller pieces (“elements”), which for tractability were excluded from this analysis. The conclusion of this article is that while they didn’t really look like much, the promotional brickbox was a really nice gift.
As a final note, we observe that achieving an optimal fill of the round cup will be much more difficult than achieving an optimal fill of the square box. In fact, the amount of time that it takes a child to optimally fill a box is about the amount of time that it takes an adult to create the bottom level of the round box.

Next time: We answer our original question of how much better off one is by packing both the round and square cups than by randomly tossing bricks in.

Notes and References

1. There is a community of people interested in this problem, for starters, see Erich’s Packing Center: http://www2.stetson.edu/~efriedma/squincir/
2. There is a very nice description of the problem at mathworld: http://mathworld.wolfram.com/GausssCircleProblem.html. Additionally, Hilbert discusses the problem in “Geometry and the Imagination,” which I purchased during the course of writing this article.
3. Sloane’s A000328: 1, 5, 13, 29, 49, 81, 113, 149, 197, 253…