# Tiling an L-shape with "almost square"s

Define an "almost square" as a rectangles with aspect ratio between $$1/2$$ and $$2$$. What is the minimal number of interior-disjoint almost-squares required to tile the following L-shape (where $$n$$ is an integer)?

Background: It is known (e.g. Richard Kenyon, 1996) that tiling an $$n \times (n-1)$$ rectangle with squares requires $$O(\log n)$$ squares. This number grows to infinity as $$n$$ grows. However, if we relax our requirements and agree to tile the rectangle with almost squares, then one almost-square is sufficient. In practical scenarios, almost-squares can be almost as good as squares, and their number (in this case) is significantly smaller.

My question is: Does this fact extend to more general polygons? Specifically, is it possible to tile the L-shape in the above diagram (which is an $$n \times n$$ square, missing a single $$1 \times 1$$ square at the corner) with axis-parallel almost-squares whose number is constant (independent of $$n$$)?

Note: This question is related: https://math.stackexchange.com/questions/873586/size-of-minimal-covering-overlapping-and-disjoint
• It might help to include an example of an almost-square tiling to attract a wider audience. Jul 22, 2014 at 16:08
• You start out by defining almost-squares as similar $1\times 2$ rectangles, and then you say that just one of them can tile an $n\times (n-1)$ rectangle. These statements seem in conflict. Mar 7, 2021 at 15:57
• @RavenclawPrefect an almost-square is not a 1-by-2 rectangle - it is a rectangle whose aspect ratio is between 1/2 and 2. Mar 7, 2021 at 17:45
• Ah, I see. Thanks for the clarification! I think I get $2,2,3,3,3,3,4$ rectangles for $n=2, 3, 4, 5, 6,7,8$ respectively (assuming "between" does not imply strict inequality) - does that match your calculations? Mar 7, 2021 at 18:01

Consider the problem as a tiling of an $$n\times n$$ square, where we have already fixed a $$1\times 1$$ in the corner. Given a partial placement of rectangles in the $$L$$-shape, let $$a$$ be the highest $$x$$-coordinate of any point on a rectangle and $$b$$ the highest $$y$$-coordinate of any point on a rectangle (where we parametrize the big square as $$[0,n]\times [0,n]$$).

Obviously, we start with $$(a,b)=(1,1)$$. Now, consider how $$a$$ and $$b$$ can change as we add rectangles. If we add the "wrong" rectangles, $$a$$ and $$b$$ will grow dramatically, but we can choose them in whatever order we like. Consider the rectangles occupying the points $$(a+\epsilon,0)$$ and $$(0,b+\epsilon)$$: the rectangles just on the "other side" of the current borders. They must be distinct from each other, and at most one of them can occupy the point $$(a+\epsilon,b+\epsilon)$$. Consider the other rectangle. If we add it, then one of $$a$$ and $$b$$ stays fixed, and the other increases by one of the dimensions of the rectangle, so we have either $$(a,b)\mapsto (\le a+2b,b)$$ or $$(a,b) \mapsto (a,\le b+2a)$$ (by the constraints on the ratio of our rectangles). Since we are trying to get $$(a,b)$$ as large as possible, we can forget about the $$\le$$ signs in these moves and just always pursue the maximum. Call these Move $$1$$ and Move $$2$$, respectively.

What is the fewest number of applications of Move $$1$$ and Move $$2$$ to get from $$(1,1)$$ to $$(n,n)$$? Note that if $$a, then the pair $$(a+2b,b)$$ is strictly larger than the pair $$(a,b+2a)$$ once we reverse the order of the latter (since our target is symmetric, we don't care about order). So the optimal strategy is to always alternate between Move 1 and Move 2, and our series of $$(a,b)$$ values goes $$(1,1), (1,3), (7,3), (7,17), (41,17), \ldots$$, with terms coming from $$\text{A}001333$$.

This puts a lower bound $$k$$ on the number of moves, which is asymptotically $$\log_{1+\sqrt{2}}(n)$$. But, conveniently, $$k$$ is also an upper bound!

To see this, note that we can easily add a rectangle at each step so that the rectangles placed so far completely tile the region $$[0,a]\times[0,b]$$, and then just clip off the final one or two rectangles when we exceed the bounds of our $$n\times n$$ square. So the only risk is that this clipping-off may bring the ratios outside of $$[1/2,2]$$.

Let $$(a,b)$$ be the furthest we get before either value exceeds $$n$$; WLOG, say $$a. With some thought, it is apparent that this only poses a problem for clipping if $$b>n/2$$; our solution is to shrink our $$a\times b-2a$$ rectangle so that its top border is at $$y=n/2$$, and proceed from there. Now our only concern is that this modification will have rendered the modified rectangle to have an unacceptable ratio, but with a bit of tedious algebra one can check that we're okay as long as $$a\le 3b$$, which is easily verified.

So the final answer is that the number of necessary rectangles is the smallest $$k$$ such that

$$\frac{(1-\sqrt{2})^k + (1+\sqrt2)^k}2\ge n$$

• Wonderful answer, thanks! I have to read it in more depth. So we still need $\Omega(\log{n})$ pieces, even if the pieces are allowed to be almost-squares. Mar 7, 2021 at 20:11