5
$\begingroup$

Define an s-tile as a path of squares that makes two turns in opposite directions.

For instance, if one chooses the lower left corner, the middle square of the bottom side, the center, and the middle square of the right hand side of a 3 by 3 square, one has an s-tile (starting from the lower left, you turn left first to get to the center, then right to get to the middle square on the right edge).s-tiles must have length at least 4. If a 1000 by 1000 grid is tiled with s-tiles only, what is the maximum area that can be covered?

My take: there is the tiling that just leaves $999 \cdot 2$ squares alone, where the leftmost and rightmost edges of the grid are not tiled except for one square on them. I doubt that this is optimal, and I have no clue how to find an optimal tiling.

$\endgroup$
  • $\begingroup$ Are z-tiles allowed? $\endgroup$ – Bram28 Dec 27 '18 at 17:05
9
$\begingroup$

Here's a scalable tiling of a $5n \times 5n$ square with S-tiles that only misses two squares (given as an example for $n = 7$):

Choose $n = 200$ to get a solution for the original problem.

It is not possible to miss less than 2 grid squares. To prove this, I first need a definition:

Let $P$ be a polyomino (a finite polygon composed of grid squares). The interior angles of $P$ are each either $90^\circ$ (convex) or $270^\circ$ (concave). Let $e$ be any edge of $P$, and let $A,B,C,D$ be consecutive corners of $P$ such that $e = \overline{BC}$. I call $e$ critical if the interior angles at $A, B, C, D$ are all convex.

Example polyomino, critical edges are marked in red:

Claim: For any critical edge $e$ of a polyomino $P$, it is impossible to place disjoint S-shapes inside $P$ such that all grid squares adjacent to $e$ are covered.

Proof by infinite descent: Suppose the claim is false. Then there must be a counterexample with polyomino $P$ and edge $e$, such that the length of $e$ is minimal among all counterexamples. So there must be at least two S-shapes covering $e$. Consider the first grid square adjacent to $e$ and the S-shape $S_1$ covering it according to the counterexample. Since $e$ is critical, Since $e$ is critical, $S_1$ cannot cover all the grid squares adjacent to $e$.

Now consider the polyomino $P'$ formed by removing $S_1$ from $P$, and let $e'$ be the remaining part of $e$ that is still an edge of $P'$. Observe that $e'$ is still critical in $P'$ because of how $S_1$ must lie in $P$.

Visualization: The blue S-shape is $S_1$, and the red edge is $e$:

However, by our assumption that $P$ is a counterexample, we can still cover the remainder of $e$ using S-shapes disjoint from $S_1$ and each other. This means that the $(P',e')$ we just constructed is a counterexample to our claim such that $e'$ is shorter than $e$. This is a contradiction to our choice that $(P, e)$ is a minimal counterexample, therefore our assumption (that a counterexample to the claim exists) is false and the claim is true.

Back to the original $1000\times 1000$ grid problem: Each of the grid's four edges is critical, so for any placement of S-shapes into the grid there must be some square by every edge that is not covered. Each grid square touches at most two edges, so we need at least two uncovered grid squares in any possible placement of S-shapes into the grid. $\square$

Edit: Here's another, very flexible method to tile arbitrary rectangles. You can choose the widths of yellow strips arbitrarily as long as two adjacent yellow strips aren't too wide.

enter image description here

$\endgroup$
  • $\begingroup$ By adjusting the middle column you can tile $5n \times 5n+k$ for any $k \ge -3$ with only two corners untiled. $\endgroup$ – Peter Taylor Dec 20 '18 at 14:21
  • $\begingroup$ @PeterTaylor I just found an even more general method, check out the edit. $\endgroup$ – Magma Dec 20 '18 at 14:35
  • 1
    $\begingroup$ @PeterTaylor Also I believe you mean $5n \times (4n + k)$ for all $k > 0$. $\endgroup$ – Magma Dec 20 '18 at 15:03
  • $\begingroup$ While polyominos of arbitrary size fit the description, I believe they make for little challenge. I find more it more interesting to limit the selection to s-tetrominos, n-petominos and z-pentominos. All $n\times n$ grids with $n>=8$ can be covered with these three to the exclusion of opposing corners. $\endgroup$ – Daniel Mathias Jan 5 at 1:27
4
$\begingroup$

Piggybacking off of Misha's answer, it is possible to cover an $n\times n$ grid with only four uncovered tiles:

. C C C C
. C B B B
C C B A A
B B B A .
A A A A .

Furthermore, I am pretty certain that every edge in a partially s-tiled grid must have an uncovered tile, so that at least two tiles must be uncovered, meaning the optimal number is between $2$ and $4$.

$\endgroup$
  • $\begingroup$ Any ideas for a proof? Induction on $n$ for an $n$ by $n$ grid might do it. $\endgroup$ – Don Jon Dec 18 '18 at 19:46
  • $\begingroup$ No idea... My track record with this variety of tiling problem is not good. @DonJon $\endgroup$ – Mike Earnest Dec 19 '18 at 3:28
3
$\begingroup$

As a starting point, we can definitely cover all but $8$ squares.

To begin with, in any $n \times (n+1)$ rectangle, we can cover all squares except two opposite corners. Use the following scheme (each letter corresponds to one tile):

 AAAAAAA
AABBBBBB
BBBCCCCC
CCCCDDDD
DDDDDEEE
EEEEEEFF
FFFFFFF

We can divide up the $1000 \times 1000$ square into two $499 \times 500$ rectangles and two $501 \times 500$ rectangles, and use the $n \times (n+1)$ scheme to cover each rectangle. Only two squares in each rectangle are left uncovered: $8$ squares total.

$\endgroup$
  • $\begingroup$ Nice observation. It certainly seems quite optimal (though of course it may not be); only a proof remains. $\endgroup$ – Don Jon Dec 18 '18 at 6:41
  • $\begingroup$ After playing around with the problem some more, I wouldn't be surprised if we can cover all but $2$ squares. I found a way to do this for many dimensions, including a $999\times 999$ grid, but not for a $1000\times1000$ yet. $\endgroup$ – Misha Lavrov Dec 18 '18 at 6:52

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.