5
$\begingroup$

What is the smallest square which contains 11 non-overlapping (except boundary) unit squares?

This question is open but I would like to know a method to verify the best known answer at the moment.

I'm reading paper at here . In figure 2, there has been said that the best known packing has side length about 3.8772 and tilt angle about 40.182 degrees. How can I verify those values, as another source (Which Way did the Bicycle Go page 105) says that the side length is about 3.877083? I think I have to denote the tilt angle by $\alpha$, a side of the square by $x$ and form two equations but I don't see how to make those equations.

$\endgroup$
  • 2
    $\begingroup$ Smallest in what sense? You can trivially put them all in a $1\times 11$ rectangle, but the perimeter of this (for example) would be larger than that of the square given in the pdf... $\endgroup$ – Paul VanKoughnett Nov 3 '10 at 0:56
  • $\begingroup$ You may want to edit your question to say "square" where it says "rectangle" now, to agree with the question title and the linked paper. $\endgroup$ – Rahul Nov 3 '10 at 1:16
  • $\begingroup$ Oops. My blunder. Fixed. $\endgroup$ – Jaska Nov 3 '10 at 1:41
  • $\begingroup$ Could this be verified by computer? Namely assume that the center points of unit square are rationals $a_i/b_i$ where $\max\{a_i,b_i\}<k$, the angle $\alpha_i$ between side of square number $i$ is $\alpha_i$ taking discrete values and $k$ is fixed. Then there is finite numbers to be checked so some algorithm might give and approximation whether side lenght > 3.8771 or not. Then check that error is small enough. Other algorithm that comes to my mind is to solve the following problem effectively. Given an $n$-gon $A$ with given end point of edges. Can we put an unit square inside $A$? $\endgroup$ – user45685 Oct 22 '12 at 21:48
1
$\begingroup$

It's a pity this example isn't really describe anywhere. Assuming that there's a triple intersection at $(1,2)$, we get the equation

$$k - 3 - \sin\alpha - \cot\alpha\cdot(2 + 2\cos\alpha - k) = 0$$

Presumably you can get more equations by assuming that the tilted squares touch each other and corners of the straight squares, but these seem not to be satisfied by the given $k,\alpha$.


How to find more equations: the tilted squares come in three groups (two, two and one), and all seem to be just touching each other. For each of the groups, one vertex has one known coordinate (the middle group might have a known vertex at $(1,2)$, but I don't know if that's true). You can get equations from the fact that these groups touch certain corners of the straight squares, and from the (apparent) fact that they just touch each other.

The simplest way to get these equations is to define vectors $s,t$ for the sides of the tilted square (they can be expressed in terms of $\alpha$), and now all these touchings amount to pairs of points $p,q$ which are parallel to either $s$ or $t$. So $p-q$ is proportional to $s$ (or $t$), and we get an equation.

Unfortunately, pursuing this route, I get conflicting equations (conflicting in the sense that when I substitute $k$ and $\alpha$, they are contradictory). Maybe you can try and tell us if it works out for you.

$\endgroup$
2
$\begingroup$

I asked this by Walter Stromquist via email. Here is our mails:

Hello,

I am a mathematician from Finland. I read from the book "Which way did the bicycle go" that you have found a way to pack $11$ squares with side length 1 to a square with side length $3.8772$ or $3.877083$. Do you know which one is correct? I have asked this on Eleven unit squares inside a larger square but got no response. Is there any computation available for the side length?

Best wishes, Jaakko Seppälä

Hello, Jaakko,

Thanks for writing!

I didn't invent the nice packing for 11 squares. I just proved that you can't do better (or as well) with "45-degree packings." The nice packing appeared in a Martin Gardner column, and he attributed it to Walter Trump. Even though my paper came close, I don't think that anyone has proved that Trump's packing is optimal.

Here is one way to do the calculation. I doubt that it is the best way, but it worked for me.

Let's use the diagram of Figure 2 in my paper. (My paper is the one you linked to in Stack Exchange. The figure in Friedman's paper is reflected in a diagonal.)

Call the lower left corner $(0,0)$. Use $(0,y)$ for where a tilted square touches the left edge, and $(x,0)$ for where another tilted square touches the bottom edge. Use $d$ for the tiny vertical distance between the two squares on the right edge.

Use theta for the angle (about 40 degrees) from the lower edge to the lower-right edge of the tilted square.

The the component in the direction $\theta$ of the vector from $(0,y)$ to $(s-2,s-1)$ is $2$. This gives the equation

$[ (s-2,s-1) - (0,y) ] . ( \cos \theta, \sin \theta) = 2$.

Looking at some other vectors gives some more equations:

$[ (s-1,s-2) - ((1,1) ] . (\cos \theta, \sin \theta) = 2$

$[ (s-1, s-3-d) - (x,0) ] . (\cos \theta, \sin \theta) = 1$

$[ (1, s-1) - (s-1, s-2-d) ] . ( -\sin \theta, \cos \theta) = 2$

$[ (0,y) - (x, 0) ] . (-\sin \theta, \cos \theta) = 3$.

Playing the first two equations against each other gives $y = 2$. (That's cute; I never noticed that!) Then it isn't too hard to get equations for $x$ and $s$ in terms of $\theta$, and then and equation for $d$ in terms of $\theta$, $x$, and $s$. That leaves us one equation to test. So we try various values of $\theta$, compute $x$, $s$, and $d$, and then see whether the test equation holds. (Like I said, there must be a better way.)

Anyway, when I do that now I get

$\theta = 40.1819372903297$

$\textrm{side} = 3.877083590022810$.

I did this using Excel, so I wouldn't want to bet too much on the accuracy of the last two digits. But is is pretty clear that Stan Wagon is right, and the number in my paper is wrong. (Stan Wagon is a pretty careful guy, and he is a genius at computation.)

Welcome to the world of square packing! I hope you find many interesting things.

Walter

Hello,

Thank you very much! It was nice to see the computations. So finally I know which one is correct. It would be nice to share this to Stack Exchange but I think there might be some copyright issues.

Jaakko

No copyright issues at this end. Share as you like!

$\endgroup$
0
$\begingroup$

Check out the squares in squares page in Erich's Packing Center, and [http://www2.stetson.edu/~efriedma/papers/squares/squares.html#figure6](his survey paper he links to).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.