2
$\begingroup$

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)?

L-shape

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
$\endgroup$
4
  • $\begingroup$ It might help to include an example of an almost-square tiling to attract a wider audience. $\endgroup$ Jul 22, 2014 at 16:08
  • $\begingroup$ 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. $\endgroup$ Mar 7, 2021 at 15:57
  • 1
    $\begingroup$ @RavenclawPrefect an almost-square is not a 1-by-2 rectangle - it is a rectangle whose aspect ratio is between 1/2 and 2. $\endgroup$ Mar 7, 2021 at 17:45
  • $\begingroup$ 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? $\endgroup$ Mar 7, 2021 at 18:01

1 Answer 1

2
$\begingroup$

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]$).

enter image description here

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<b$, 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<b$. 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$$

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 7, 2021 at 20:11

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.