Is it possible to tile an $8\times8$ board with dominoes ($2\times1$ tiles) so that no two dominoes form a $2\times2$ square?
Problem
Source: Puerto Rico TST 2014
Tags: combinatorics, Tiling
21.02.2016 21:25
Extra: At most how many dominos can be used?
03.03.2016 10:26
Introduce coordinates such that left, bottom corner has $(1;1)$. WLOG $(1;1)$ is covered by horizontal domino. Then, in order not to form $2\times 2$ square, $(1;2)$ must be covered by vertical domino. It's evident that by induction we will get, that $(n;n)$ is a left square of horizontal domino, and $(n;n+1)$ is a bottom square of vertical domino. Considering $(7;7)$ we will get a contradiction, cos $(8;8)$ must be the right and left square of horizontal domino at the same time. (Note that it works for any length of the side of the big square). From the first part, we deduce, that at least one little square is absent in $(2k+1)\times (2k+1)$ board. See first attachment to understand the construction of example of $2k^2+2k$ dominoes. From the first part, we deduce, that at least one domino is absent in $2k\times 2k$ board. See second attachment to understand the construction of example of $2k^2-1$ dominoes.
Attachments:


14.06.2017 12:47
Actually, no math is needed. If you start from a corner, there are only two possible ways to put a domino, vertical or horizontal. The rest of the moves you do are forced by the condition of not making a square with two of them, so the only possible configuration trying not to do the square is in the attachment, but it still makes a square, so its impossible not to.
Attachments:

29.10.2022 05:38
too trivial for tst