Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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:
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!
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.
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:
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.
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.
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!
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.
