Covering a $kn+1\times kn+1$ region on a $(k+1)n-1\times (k+1)n-1$ square grid

Question

We are given a $\left((k+1)n - 1\right)\times \left((k+1)n-1\right)$ square grid and tiles of size $1\times n$. We can place the tiles anywhere on the board, provided that they never cover the same area more than once. The tile orientation (horizontal or vertical) does not matter.

The question asked is can we put some number of these tiles on the board so that there exists a $(kn+1)\times(kn+1)$ region which is fully covered by the tiles?

After a few attempts I suppose the answer is negative. I have tried various tricks with coloring the grid, but with no success. I think it's crucial that we can never fit $k + 1$ tiles oriented horizontally in the same row (an analogous observation is true for columns), so maybe there is a clever way of coloring based on that.

The question originally asked for the case $k=3, n=5$ under the assumption the $(kn+1)\times(kn+1)$ region must not share any border with the whole grid. However, as was suggested in the comments, this assumption is not necessary.

Answer 1

As hinted, here's a much simpler solution to the much simpler case, which allows for a much easier generalization. Through various tweaks of the setup, this resulted in a very different (to me) solution, which is why I posted it separately. I can delete the other solution if that is desired.

In a $ 5 \times 5$ grid covered with $ 1 \times 3$ tiles, we cannot cover a $ 4 \times 4$ square.

Consider the following coloring of the $ 5 \times 5 $ grid.

$$\begin{array}{ccccc} a &b &-a-b &a &b \\ c &d &-c-d &c &d \\ -a-c &-b-d &a+b+c+d& -a-c& -b-d \\ a &b &-a-b &a &b \\ c &d &-c-d &c &d \\ \end{array}$$

Observe that

• Each $1 \times 3$ tile has sum 0.
• The board has sum $a+b+c+d$. (EG Using $ 1 \times 3 $ tiles, we can cover all but the top left $2 \times 2$ squares, which have sum $a+b+c+d$)
• Hence, no matter how / how many $1 \times 3$ tiles are placed, the leftover uncovered squares have sum $a+b+c+d$. This is the invariant in the coloring.

Now, suppose that there are $1\times 3$ tiles that can cover a $ 4 \times 4$ area. Observe that

• The top left square of this $4 \times 4$ area must fall in the top left $2 \times 2 $ grid.
• Suppose the top left square of the $4 \times 4$ area is $a$ (resp $b, c, d$), then the $ 4 \times 4$ area will cover all squares with $a$ and $-a$ (resp ....).
• Hence, it's impossible for the leftover uncovered squares to have a sum with $a$ in it.
• This contradicts that the uncovered sum is $a+b+c+d$, so such a $4 \times 4$ covering does not exist.

---

Now, for the generalization

Fix integers $ k \geq 2, n \geq 2$. Using $ 1 \times n$ tiles to cover a $(kn-1) \times (kn-1)$ grid, we cannot cover a $(k-1)n+1 \times (k-1)n+1$ square.

Consider the following coloring:

• In the top left $ (n-1) \times (n-1) $ grid, use colors $ a_{i, j}$.
• In the $n$th column, first $n-1$ rows, use negative of the row sum. IE $a_{I, n} = - \sum_j a_{I, j}$.
• Likewise, for the $n$th row, first $n-1$ columns, use negative of the column sum. IE $a_{n, J} = - \sum_i a_{i, J}$.
• Then $a_{n, n} = \sum_{i,j} a_{i,j}$.
• Repeat this coloring all over the board. (EG Repeat for a $kn \times kn$ grid, then truncate the last row and column.)

Observe that

• Each $ 1 \times n$ tile has sum 0.
• The board has sum $\sum a_{i,j}$. (EG Using $ 1 \times n $ tiles, we can cover all but the top left $(n-1) \times (n-1)$ squares, which have the desired sum.)
• Hence, no matter how / how many $1 \times n$ tiles are placed, the leftover uncovered squares have sum $\sum a_{i,j}$. This is the invariant in the coloring.

Now, suppose that there are tiles that can cover a $ (k-1) n + 1 \times (k-1)n + 1 $ area, which we'd refer to as $S$. Observe that

• The top left square of $S$ must fall in the top left $(n-1) \times (n-1) $ grid.
• Suppose the top left square of $S$ falls on $ a_{i,j}$, then $S$ will cover all squares which contain $a_{i, j}$ or $-a_{i, j}$.
• Hence, it's impossible for the leftover uncovered squares to have a sum with $a_{i, j}$ in it.
• This is a contradiction.

---

Note: With this coloring, we can even strengthen the $5 \times 5$ grid case, to show that we cannot even cover squares that include

$$\begin{array}{ccccc} x & & &x \\ &x &x & \\ & x &x & \\ x & & &x \\ \end{array}$$

Answer 2

(This is not a complete solution yet. You are asked to generalize the approach.)

We first prove a much simpler case.

In a $ 5 \times 5$ grid covered with $ 1 \times 3$ tiles, we cannot cover a $ 4 \times 4$ square.

Prove: Consider the following coloring of the $ 5 \times 5 $ grid.

$\begin{array} {ccccc} 1 & -i & -1+i & 1 & -i \\ i & -1 & 1-i & i & -1\\ -1-i & 1+i & 0 &-1-i &1+i\\ 1 & -i & -1+i & 1 & -i \\ i & -1 & 1-i & i & -1\\ \end{array}$

Notice that

• The sum of all of the squares is 0.
• Each $ 1 \times 3 $ tile covers a sum of exactly 0.
• The sum of the uncovered squares is 0.
• The number of uncovered squares is exactly $1 \pmod{3}$.

Hence, for any covering with 9 or fewer uncovered tiles, the tiles that are uncovered must be of the following type:

• 1 individual cell that contains a $0$, and larger sets that contain this.
• 1 copy each of $1, i, -1, -i$, and larger sets that contain this.
• 1 copy each of $ 1+i, 1-i, -1+i, -1-i$, and larger sets that contain this.
• 2 copies each of $-1-i$ and $1+i$, and larger sets that contain this.
• 2 copies each of $-1+i$ and $1-i$, and larger sets that contain this.

It is clear that in each of these cases, we will not have a fully covered $4 \times 4$.

Now, generalize this argument to

Fix integers $ k \geq 2, n \geq 2$. Using $ 1 \times n$ tiles to cover a $(kn-1) \times (kn-1)$ grid, we cannot cover a $(k-1)n+1 \times (k-1)n+1$ square.

• What should the grid look like?
• What should the "notice like" be?
• What is a classification of the uncovered tiles?
• Can we improve this approach further?