Sofia and Viktor are playing the following game on a $2022 \times 2022$ board: - Firstly, Sofia covers the table completely by dominoes, no two are overlapping and all are inside the table; - Then Viktor without seeing the table, chooses a positive integer $n$; - After that Viktor looks at the table covered with dominoes, chooses and fixes $n$ of them; - Finally, Sofia removes the remaining dominoes that aren't fixed and tries to recover the table with dominoes differently from before. If she achieves that, she wins, otherwise Viktor wins. What is the minimum number $n$ for which Viktor can always win, no matter the starting covering of dominoes. Proposed by Viktor Simjanoski
Problem
Source: Macedonian National Olympiad 2022 P4
Tags: combinatorics, game, table, dominoes, minimum
29.04.2022 16:59
Here's a sketch of the official solution. If Sofia covers the board with 2x2 squares and places 2 dominos in each square, then $n\geq 1011^2$, otherwise Sofia will just change the orientation of the two dominos in some square. For $n=1011^2$, Viktor's strategy is to fix the dominos containing an square with odd coordinates (they are exactly $n$). We shall prove that there isn't any other domino cover for the rest of the board. Suppose FTSoC that there is, and connect two squares with a black edge of they are in one domino in the first cover, and with a white edge for the second cover. Ignore the dominos which are common for both coverings (including the fixed ones). Hence each vertex has degree $2$, so the obtained graph is a union of alternating cycles with even length. Now consider the interior of some cycle in the board; note that it is covered by dominos, so there are even number of squares there. On the other hand, they are odd (this can be proven by induction on the number of "odd squares" in the interior), contradiction.
29.04.2022 18:19
@above can you please explain what do you mean by "interior of some cycle in the board"
29.04.2022 18:22
@above the squares that are inside the region, bounded by the cycle in the grid (and not including the squares of the cycle itself)
29.04.2022 22:07
@above thanks ,but I still do not understand the proof fully. So how I understood it, from the fact that from each square there is drawn one white and one black edge we have that every vertex in the graph has degree $2$, so there is at least one cycle. But how can you look at the interior of the cycle on the board if we have two separate covers?
29.04.2022 22:21
Well, you put these edges on one board and that's how you interpret both coverings on one board.
29.04.2022 22:51
Yes but is there not gonna be overlaping dominos?
29.04.2022 23:26
Never mind I get it now, thanks
02.11.2023 23:35
An outline of the solution: It is clear that $n\geq 1011^2$. Let S be $2\times2$ tetromino. If we can cover a shape L with a number of S's, call L "special". Let's mark each S's top right corner with 1. We will prove that if Victor chooses the dominoes including 1's, he guarantees to win. We will proceed by strong induction on the area of the "special" shape. Base cases are obvious. Construct a graph of which vertices are the marked squares and there is an edge between u and v iff the domino on u is adjacent to the domino on u. It is not difficult to prove that there are no cycles. Now, take the top right corner, which is marked with 1, and consider the domino on it. WLOG, it is horizontal. Follow a path starting at the corner. The last vertex on the path is a leaf, hence the path hits the boundary. If the path is not linear, then the shape can be divided into two "special" pieces (divide the shape such that the vertical edges are within a piece, and the horizontal edges are within the other piece.). By induction, we are done. If the path is linear, take the vertex below the first vertex (if there does not exist, we are done, removing the top right S.). Apply the same procedure. If this path is also linear, we know the location of dominoes between the two paths, and by induction, the hypothesis again proves to be accurate.