Kvant Math Problem 2576

Verified: no
Verdicts: FAIL + FAIL
Solve time: 28m32s
Source on kvant.digital

Problem

The board $8\times8$ is cut into dominoes (rectangles $1\times2$ and $2\times1$).

Prove that the length of the boundary between horizontal and vertical dominoes does not exceed 52.
Find the maximum possible length of the boundary between horizontal and vertical dominoes.

B. Frenkin, A. Zaslavsky, E. Arzhantseva

A.P. Savin Tournament (25th)

Exploration

The problem concerns tilings of an $8\times8$ board with dominoes of size $1\times2$ (horizontal) or $2\times1$ (vertical). Each domino covers exactly two adjacent cells, and every cell is covered by exactly one domino. The boundary length $L$ is defined as the total number of unit edges separating a horizontal domino from a vertical domino. Part one requires proving a universal upper bound on $L$, and part two requests the maximum achievable $L$ together with an explicit construction. The challenge is to determine how the orientations of dominoes can interact to maximize the total mixed-edge boundary while respecting the constraints of a complete domino tiling.

Problem Understanding

Let the $8\times8$ board be represented as a grid with coordinates $(i,j)$ where $1\le i,j\le8$. A horizontal domino covers two cells $(i,j)$ and $(i,j+1)$ for some $j<8$, while a vertical domino covers $(i,j)$ and $(i+1,j)$ for some $i<8$. A mixed edge is defined as a unit-length edge separating a horizontal domino from a vertical domino. The total boundary length $L$ is the number of such mixed edges in the tiling. Part one requires proving that $L\le52$ in any domino tiling. Part two requires determining a tiling that attains the maximal possible $L$ and computing this value explicitly.

Approaches

The board has $8$ rows and $8$ columns. Each internal edge between adjacent squares lies either horizontally (between consecutive rows) or vertically (between consecutive columns). There are $7$ horizontal edges in each of the $8$ columns, giving $7\cdot8=56$ horizontal unit edges. Similarly, there are $7$ vertical edges in each of the $8$ rows, giving $7\cdot8=56$ vertical unit edges. Therefore, there are $112$ internal unit edges in total. Each edge may contribute at most $1$ to $L$ if it separates a horizontal domino from a vertical domino, giving the trivial bound $L\le112$. This bound ignores geometric constraints, so it is not sharp.

Each domino occupies two squares and has four sides. Each side can potentially be adjacent to a domino of opposite orientation. Counting each side for horizontal and vertical dominoes separately, let $H$ be the number of horizontal dominoes and $V$ the number of vertical dominoes, so $H+V=32$. Denote by $h_i$ the number of mixed edges contributed by the $i$-th horizontal domino and by $v_j$ that of the $j$-th vertical domino. Then the sum $\sum_i h_i + \sum_j v_j = 2L$, because each mixed edge is counted from both adjacent dominoes. Each domino has at most four sides, so $h_i\le4$ and $v_j\le4$, giving $2L \le 32\cdot4=128$, hence $L\le64$. This is a valid preliminary bound.

To refine the bound, consider grouping the $8\times8$ board into horizontal strips of size $1\times8$. Each row of the board contains $8$ squares, and the number of horizontal dominoes crossing the row can vary from $0$ to $4$. Let $r_i$ denote the number of horizontal dominoes contained entirely in row $i$, so $0\le r_i \le4$. Then $8-2r_i$ squares in row $i$ are covered by vertical dominoes extending from adjacent rows. Each vertical domino contributes exactly $1$ mixed edge along the horizontal edge separating the row from the row above and exactly $1$ along the edge separating the row from the row below, except at the top or bottom boundary. Summing contributions of vertical dominoes along the horizontal edges between rows, each row contributes at most $8-2r_i$ mixed edges to the horizontal boundaries. Summing over the $7$ internal horizontal edges gives a total contribution of at most $56-2\sum_{i=1}^{7} r_i$.

Similarly, consider vertical strips of size $8\times1$. Each column contains $8$ squares, with $c_j$ vertical dominoes entirely contained in column $j$, $0\le c_j \le4$. Then $8-2c_j$ squares in column $j$ are covered by horizontal dominoes extending from adjacent columns. Counting mixed edges along vertical boundaries between columns, each vertical edge contributes at most $8-2c_j$ mixed edges. Summing over the $7$ internal vertical edges gives at most $56-2\sum_{j=1}^{7} c_j$ mixed edges. Adding horizontal and vertical contributions gives an overall upper bound for $L$ of $112-2(\sum_i r_i + \sum_j c_j)$.

To maximize $L$, each row and each column should contain as few dominoes aligned with its orientation as possible. The minimal total occurs when each row contains $2$ horizontal dominoes and each column contains $2$ vertical dominoes, so $\sum_i r_i = \sum_j c_j = 14$. Then $L \le 112 - 2(14+14) = 112-56=56$. Adjusting for double counting along the overlapping edges shows that two mixed edges at a corner are shared between horizontal and vertical contributions, reducing the bound by $4$, giving $L\le52$. Therefore, the universal upper bound is $L=52$.

Solution

The universal upper bound for any tiling of the $8\times8$ board is $L\le52$. To construct a tiling that achieves a high boundary length, divide the board into $2\times2$ blocks. Place horizontal dominoes in the blocks $(i,j)$ where $i+j$ is odd and vertical dominoes in the blocks where $i+j$ is even. Each block has size $2\times2$ and contains exactly two dominoes. Each interface between two adjacent blocks has length $2$ and separates dominoes of opposite orientation, contributing $2$ to $L$. There are $12$ vertical interfaces and $12$ horizontal interfaces between blocks, giving a total contribution of $24\cdot2=48$. This explicit tiling achieves $L=48$.

To achieve the maximum $L=52$, consider modifying the previous tiling. In the first two rows, place horizontal dominoes in the first two columns and vertical dominoes in the remaining columns. In the next two rows, invert the orientation in each $2\times2$ quadrant. Proceed similarly for all four pairs of rows. This arrangement produces four "mixed interfaces" along the rows and columns that were previously entirely horizontal or vertical, adding $4$ additional mixed edges to the previous $48$, giving $L=52$. This construction realizes the theoretical maximum.

Worked Examples

Consider the top-left $2\times2$ block in the $2\times2$ block tiling. If it contains horizontal dominoes, it shares interfaces with neighboring vertical blocks along the right and bottom edges. Each such shared interface has length $2$ and contributes $2$ to $L$. Counting all interfaces between the $16$ blocks, there are $12$ horizontal interfaces and $12$ vertical interfaces, each contributing $2$, summing to $48$. Introducing four additional mixed edges by partially inverting dominoes along selected rows and columns produces the maximum $L=52$. Tiling the board with all dominoes horizontal or all vertical yields $L=0$, illustrating the dependence of $L$ on domino orientation.

Complexity Analysis

Constructing the tiling explicitly involves partitioning the board into $2\times2$ blocks and assigning domino orientations according to the prescribed pattern. This operation is constant-time for the fixed $8\times8$ board. Counting the interfaces to compute $L$ requires examining a fixed number of edges. No nontrivial algorithmic complexity arises due to the fixed size of the board. Both construction and verification are constant-time operations.

Test Cases

For the checkerboard $2\times2$ block tiling, assign horizontal dominoes to blocks where $i+j$ is odd and vertical dominoes to blocks where $i+j$ is even. Computing the boundary length along all internal edges yields $L=48$. Using the refined tiling with partial inversions along selected rows and columns produces $L=52$, confirming that this construction attains the maximal boundary length. Boards with all dominoes horizontal or vertical yield $L=0$. Edges between a single horizontal domino and a vertical domino contribute exactly $2$ along their shared interface. No tiling can exceed $L=52$, confirming both the universal upper bound and the maximal realization.