8
$\begingroup$

A square with a side length of exactly 1000 can obviously be packed with exactly a million unit squares.
If we increase the side length to 1001, then 2001 more squares can fit.

But if we increase the side length by only 1/4, can you still squeeze in an extra square?

$\endgroup$
  • 5
    $\begingroup$ When you post puzzles that aren't of your own invention, it's necessary (at a minimum) to clearly state the original author. If the source contains a spoiler (for example, if the source is some scientific paper from, say, November 1974), you can withhold the attribution until answers have been posted, but you should mention that you are doing so. $\endgroup$ – Bass Oct 18 '20 at 11:44
  • 6
    $\begingroup$ @Bass This is puzzle of my own invention. $\endgroup$ – SE - stop firing the good guys Oct 18 '20 at 11:47
  • 1
    $\begingroup$ @Bass You could post your comment as an answer, as others probably don't understand it. Also the OP might not have seen this paper. $\endgroup$ – WhatsUp Oct 18 '20 at 14:20
7
+100
$\begingroup$

Answer:

Yes

Approach: Let's see whether we can get the construction proposed by everybody's favorite Hungarian frequent traveler and alluded to in several comments to work. This is not a given because it is an asmptotic result and 1000.25 is a rather small number considering the construction works with the 11th root of that.

Overview:

Let us walk through the construction for 10,000.25. For this side length a straight forward non optimized implementation gives me 100,000,395 squares. It look as follows:

enter image description here The bulk---84,437,721---squares are arranged in the standard pattern in the large square. Let's zoom in a bit for the next big chunk:

kk Zooming in at the top right corner we see that the two next largest structures are composed of tilted stripes each wide one square and long 812 squares which is just above the width left (811.25). The stripes are therefore slightly tilted and stacked. 9,943 in the horizontal structure at the top and 9,133 in the vertical structure at the right. Together, the three big structures account for 99.9% of the total. Still, the tricky bit is squeezing out the missing permille from the four leftover trapezoid areas. I'm emphasizing these numbers to drive home the point that in the end there is very little slack. Every square counts!

enter image description here At larger maginification we see that large parts of these are also covered in the "naive" way, using on grid rectangles of various dimensions. Let us zoom in one more time to study the non rectangular components.

enter image description here This is the conceptually trickiest bit. We see that unit width stripes are used again but they are not parallel but sligthly tilt as the walls close in. You can also see that my implementation is not optimized, for example, there is clearly space for a few more squares in the triangular cranny where the stripe pattern ends. Also, how to round asymptotic prescriptions to finite integers may make a slight difference.

Now for the small (1000.25) problem:

enter image description here Looking at roughly the same area we can guess that the tilted stripes strategy suffers from finite size. This can be understood as follows: The progressive tilting is not something we want, it is the least bad option. But only under certain constraints. For it to be better than,say just regular grid arrangement leaving gaps at the diagonal edge the tilt range must be small. This requires the height to change slowly, in other words the slope of the slanted side must be shallow. This slope is the tilt of the parallel tilted stripes which depends on the fractional part of the side length and on the absolute size. Because it depends on the ratio of the space missing which equals 1 - the fractional part over the width of the compound which becomes more and more favorable with growing side length.
However subtle the effect, in the end we are a few squares short of what we need at 999,467. But wait, the tilting stripes are clearly not optimal, be this because of my suboptimal implementation or because of principal finite size, no matter which, let's just get rid of them.

enter image description here And fall back to the good old rectangle instead. Looks better, doesn't it? Numbers are also better at ... 999,999 squares, I'm not making this up. Is that it, then? Wait, there is one last tweak: The parallel stripes regions do not extend as far as they could. This makes sense if you are going for the tilting stripes later because they need a certain height to function properly, but as we ditched them, there is no benefit for us. So let's fix that.

enter image description here That is what it looks like, the ends are no longer trapezoids but triangles.

What do the numbers say?

1,000,001 squares, exact. Tada!

$\endgroup$
  • $\begingroup$ Very nice! How many more can you fit? $\endgroup$ – SE - stop firing the good guys Oct 22 '20 at 7:16
  • $\begingroup$ @SE-stopfiringthegoodguys Oh, no. I won't be drawn! 1,000,001 is my last word. $\endgroup$ – Paul Panzer Oct 22 '20 at 7:41
1
$\begingroup$

I'm thinking the answer is

No. I base this answer on the image below which is the largest square that i can see is feasible (the grey areas are the other unit squares such that some rows and columns have been shifted into the empty space provided). But if the dash line is 1/4 then the square is only 1/8 square units.
If this is the best geometric formulation then in order for the square to be 1 unit, the dashed line would have to be sqrt(1/2) = approx. 0.7 in length. enter image description here

$\endgroup$
  • 2
    $\begingroup$ As the comment says, this problem is known as square packing in square and has been studied by Erdos and Graham, who showed that one can reduce the wasted space to $o(a^{7/11})$ for an $a \times a$ square. $\endgroup$ – WhatsUp Oct 18 '20 at 16:46
  • $\begingroup$ Erich's Packing Center has quite a few constructions similar to this one, where the green square is composed of multiple unit squares, for several values of $n^2+1$, but I don't believe you can pull it off with a gap smaller than $\frac{1}{2}$ $\endgroup$ – AxiomaticSystem Oct 19 '20 at 0:33

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.