An $8 \times 8$ chessboard is covered completely and without overlaps by $32$ dominoes of size $1 \times 2$. Show that there are two dominoes forming a $2 \times 2$ square.
Problem
Source: Bundeswettbewerb Mathematik 2019, Round 1 - Problem 1
Tags: combinatorics, combinatorial geometry
05.08.2019 21:05
A way to prove it is through brute force, i.e. put a domino tile on the top left row corner and then start placing dominos with the intention of avoiding the creation of any $2 \times 2$ square. As it turns out there is only one way to do it and in the resulting board one such square is filled.
05.04.2020 20:19
Can anybody show the solution?
18.07.2020 18:19
Assume there exists a configuration such that there isn't a square. Consider the number of $2 \times 2$ squares on a chessboard, it's 49 (can overlap, but can't leave board). Call a $2 \times 2$ occupied if there's a full dominoe in it (notice one dominoe can occupy exactly $1$ or $2$ squares $2 \times 2$'s).The dominoes touching the edge of the board with their longer side are occupying exactly one $2 \times 2$ square (i.e. the one they're inside of). Let there be $k$ such dominoes. Obviously $k \le 14$. We'll place $32$ dominoes at the end, so basically $32-k$ of them will be in exactly two $2 \times 2$'s. So the total number of occupied $2 \times 2$'s will be $2 (32-k)+k = 64-k \ge 64-14=$50. By Dirichlets we get a contradiction.