Covering a board problem 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.
 A: 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.
A: 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. 
