5
$\begingroup$

A $7 \times 7$ board is divided into $49$ unit squares. Tiles, like the one shown below, are placed onto this board. The tiles can be rotated and each tile neatly covers two squares. Note that each single tile consists of two unit squares joined at a corner. What is the minimum number of tiles that can be placed onto the board so that every uncovered square will be adjacent to at least one covered square?

Note: Two squares are adjacent if they share a common side.

My attempt: These tiles cover a shape like $$\begin{matrix}0&0&1&0\\0&1&1&1\\1&1&1&0\\0&1&0&0\\ \end{matrix}$$where $'1'$s are the covered squares/next to covered squares. Using $3$-coloring (to the $7\times7$ board) we need at least $7$ tiles. I found a way to do it with 8 tiles. But is there a way prove $7$ isn't enough (or is it actually enough)?

$\endgroup$
  • 2
    $\begingroup$ You can get the lower bound of $7$ without a coloring argument by just noticing that one tile covers $2$ squares and is adjacent to another $6$. So $6$ tiles will only give you at most 48 squares out of 49. $\endgroup$ – quarague Feb 22 at 10:09
  • $\begingroup$ Related question (corrected link): math.stackexchange.com/questions/451421/board-7-times-7-problem $\endgroup$ – Servaes Feb 22 at 11:56
5
$\begingroup$

You also cannot succeed with $8$ tiles. Each of the tiles can only cover one of the squares marked with an $\times$: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline \times &\;\,&\;\,&\times&\;\,&\;\,&\times\\ \hline &&&&&&\\ \hline &&&&&&\\ \hline \times &\;\;&\;\;&\times&\;\,&\;\,&\times\\ \hline &&&&&&\\ \hline &&&&&&\\ \hline \times &\;\;&\;\;&\times&\;\,&\;\,&\times\\ \hline \end{array} $$

Here is a solution with $9$ tiles:

$\endgroup$
  • $\begingroup$ Wow that's so nice... and I am blind. $\endgroup$ – abc... Feb 23 at 3:53
  • 1
    $\begingroup$ Very nice. For a slightly prettier solution with 9 tiles, you can start with a rotationally symmetric arrangement of 8 tiles covering all but the center square. Namely, put tiles on b1&c2, d2&e1, g2&f3, f4&g5, f7&e6, d6&c7, a6&b5, b4&a3; every square but d4 is covered. $\endgroup$ – bof Feb 23 at 5:40

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.