3
$\begingroup$

Take a 10x10 board. We're going to try to cover it with 2x2 squares that can overlap. Let an arrangement where the board is covered but one piece can be removed and the board still be covered be redundant. If one cannot do this, then the arrangement is non-redundant. The smallest non-redundant covering evidently is 25 squares.

(a) Show that there is a non-redundant covering with 35 squares. b) Show that every covering with 55 squares is redundant. c) Can these bounds be improved?

By messing around this seems to work and the bounds do not seem to be those that are above but I have no idea how to prove it.

$\endgroup$
  • $\begingroup$ is the question telling you to bound it ? $\endgroup$ – Roddy MacPhee Mar 13 at 8:02
2
$\begingroup$

The strategy is what it nearly always is: try to decompose into smaller problems.

Let $f(m,n)$ be the number of tiles in the largest non-redundant covering of $m \times n$.

Consider an $m \times 2$ grid. There are $m-1$ places where you can put a tile. The first and the last are necessary, to cover the first pair of corners and the last pair of corners. There can't be three consecutive squares, for then the middle one would be redundant. There can't be two consecutive gaps, for then there would be squares uncovered. So you're looking at strings of the form $1(101|01)^*1?$ of length $m-1$ and trying to maximise the $1$s. So $$f(m,2) = \begin{cases} 1 + \frac23 (m-2) & \textrm{if } m \equiv 2 \pmod 3 \\ 2 + \frac23 (m-4) & \textrm{if } m \equiv 1 \pmod 3 \\ 3 + \frac23 (m-6) & \textrm{if } m \equiv 0 \pmod 3 \\ \end{cases}$$

Now, an $m \times n$ grid has an edge of length $m$. If you cover that edge, you also cover the row next to it. So you get a bound $f(m,n) \ge f(m,2) f(n,2)$.

Is that bound tight? Not necessarily. If there's a $010$ in the horizontal pattern and a $010$ in the vertical pattern, then where those meet in the 2D product there's a single tile which doesn't overlap any others. You can remove it and replace it with four tiles whose corners meet, increasing the number of tiles by $3$. You may also be able to do interesting things by using different patterns for different rows.

I think this gets you an irredundant tiling with $48$ tiles for $10 \times 10$. An exhaustive consideration of $4 \times 4$ grids would allow you to identify all of the opportunities for using the interactions of horizontal and vertical patterns to squeeze in extra tiles.

$\endgroup$
  • $\begingroup$ Interesting result. Does this prove that there exists a non-redundant covering with 35 squares and that every covering with 55 squares is redundant? $\endgroup$ – GuauGuau754 Mar 13 at 15:32
  • $\begingroup$ The replacement you talked about can create a redundancy. None of the four tiles added will be redundant, but a nearby tile may become redundant. Your $f(m,2)\times f(n,2)$ method gives a $36$ tile covering, but I do not see how this can be improved . $\endgroup$ – Mike Earnest Mar 13 at 18:58
  • $\begingroup$ @MikeEarnest Is it not possible to reach the 48 tiles as posted above? $\endgroup$ – GuauGuau754 Mar 13 at 19:30
  • $\begingroup$ @MikeEarnest, you're right that it's a lot easier than I thought to create a redundancy, but it's not completely guaranteed. I've found a 37-tile covering based on the string 110101011, but I'm tempted to believe that it can't be improved further. $\endgroup$ – Peter Taylor Mar 13 at 20:02
  • $\begingroup$ Can you post that 37 tile covering? I can't find it. $\endgroup$ – GuauGuau754 Mar 13 at 22:29
1
$\begingroup$

Here is a non redundant covering with $36$ squares. Each square is labeled with the number of tiles covering it.

1 1 1 2 1 1 2 1 1 1 
1 1 1 2 1 1 2 1 1 1
1 1 1 2 1 1 2 1 1 1
2 2 2 4 2 2 4 2 2 2
1 1 1 2 1 1 2 1 1 1
1 1 1 2 1 1 2 1 1 1
2 2 2 4 2 2 4 2 2 2
1 1 1 2 1 1 2 1 1 1
1 1 1 2 1 1 2 1 1 1 
1 1 1 2 1 1 2 1 1 1

Here is how you can obtain a $35$ tile solution. Start with the $27$ tiles shown below. There are $8$ uncovered white areas, which should be covered with $8$ additional tiles which overhang the white areas either to the left or below (or both).

To prove $55$ tiles are redundant, use the pigeonhole principle. There will be $27$ holes. Each "hole" is a $2\times 4$ rectangle whose lower left coodinate is $(i,j)$ and whose upper right coordinate is $(i+4,j+2)$, where $i$ ranges over the set $\{0,3,6\}$ and $j$ ranges over $\{0,1,2,3,4,5,6,7,8\}$. Each tile falls in one of these holes. If there are $55$ tiles, then some hole must have $\lceil 55/27\rceil=3$ tiles. But when there are three tiles in a $2\times 4$ rectangle, the middle tile is redundant.

I do not know if $55$ can be improved.

$\endgroup$
  • $\begingroup$ Credits to Peter Taylor for coming up with the $36$ tile solution. $\endgroup$ – Mike Earnest Mar 13 at 19:15
  • $\begingroup$ It seems to be the bound as it is one more than twice the number of holes. $\endgroup$ – GuauGuau754 Mar 13 at 19:27
  • $\begingroup$ Also, how would I prove that there is a non-redundant covering with 35 squares? $\endgroup$ – GuauGuau754 Mar 13 at 19:31

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.