Aléas numériques

Linux, infosec and whatever crosses my mind.


» Squares in Square

Today’s post will be about something a little bit different than usual: a mathematical problem that completly blew my mind over the past few days.

It all started when a friend sent me this tweet:

In addition to laughing, I was intrigued by what the figure was supposed to represent. This seemed to be a pretty unefficient way to pack squares, and what was $s = 4.675+$ supposed to mean?

The entrance of the rabbit hole

I searched for “efficient way to pack squares”, and ended up on the Square packing in a square Wiki page.

The Square packing in a square is a packing problem (a kind of optimization problem that want to know how much stuff we can put in a given thing) which objective is to determine how much squares of side size 1 can fit into a bigger square of side size $s$.

The number of smaller squares is noted $n$.

At first look, this seems to be a quite simple problem, right? But in fact, this problem one of the unsolved problems of the mathematics. If $s$ is an integer, the answer is indeed simple: $n = s^2$. But what if $s$ is a floating point number?

Digging a little bit deeper

As we just saw, the smallest value of $s$ that permits the packing of $n$ ‘smaller’ unit squares is known when $n$ is a perfect square1. For some other numbers (2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, and 48) we also know the most optimum packing strategy which what is called the natural (or trivial) packing. With this strategy, the unit squares are aligned with the sides of the bigger one, and $s$ is $\lceil \sqrt{n} \rceil$2.

Within the numbers mentioned above, only 5 and 10 are differents because they need tilted squares.

There is only one small number that is resisting mathematicians and remains unresolved: 11. The tightest known packing is inside a square of side $s \approx 3.789$, but it has not been proved it can’t be smaller yet.

Big numbers, big problems

I should mention that everything I wrote above is valid for small numbers only. For bigger ones, the previse number of smaller squares that can fit in a $s \times s$ square is unknown. A non-optimized solution is to pack $\lfloor s \rfloor \times \lfloor s \rfloor$ unit squares that will be aligned to the sides of the bigger square, but it will leave a big unused area (approximately equal to $2a\lparen a - \lfloor a \rfloor \rparen$), as wasted as me during the New Year Eve party.

People way smarter than me found that this wasted space can be dramatically reduced3, and I will not enter in the details here because the math behind is way too complex for me.

The frustration

When scrolling throught the compilation of best known packing schemes, one can only be frustrated by the space that is lost on some of the packing:

Hence, the numerous memes I found while investigating the topic:

Or:

I am on the verge of quitting everything and devoting the next 20 years of my life to proving that John Bidwell is wrong4.

Addition

As a wide man once said:

There’s a XKCD for everything!

And this is goddamn correct.

To be honest, I don’t really know where I’m going with this blog post. I’m quite bad at maths, but sometimes I find them really fascinating.

If you enjoyed this post or are interesting into checking more packing problem optimizations, here is a compilation of various shapes into other shapes and other problems. Enjoy!


I did a mistake? You want to say something about this post? Feel free to send me an email about this article by clicking here!


  1. A perfect square is an integer that is the square of another integer. An exemple is $\sqrt{9} = 3$. ↩︎

  2. Those symbols represent the ceiling function. For instance, with $n = 14$, we have $\sqrt{14} = 3.741…$, so $s = 4$. ↩︎

  3. https://mathweb.ucsd.edu/~fan/wp/spacking.pdf ↩︎

  4. All my former maths teachers will tell you that I’ll need to dedicate way more than 20 years. They’ll probably be right. Men lie, not grades. ↩︎