Maximum Area Covered by an S-Shaped Tiling

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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