Kvant Math Problem 705

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m45s
Source on kvant.digital

Problem

On a rectangular sheet of graph paper, several rectangular cards are placed so that their sides lie along the grid lines. The cards cover the sheet in two layers, that is, each cell of the sheet is covered by exactly two cards.

Suppose each card has dimensions $1\times 2$ cells. Prove that it is possible to select some of the cards so that they cover the sheet in a single layer. (Cards cannot be moved.)

Does this remain true if the cards

can have arbitrary dimensions?
have dimensions $1\times 3$ cells?

G. A. Galperin, V. V. Proizvolov

Exploration

Represent each cell of the sheet by a vertex. When all cards are $1\times2$, every card covers two adjacent cells, hence corresponds to an edge joining the two corresponding vertices. Since every cell is covered by exactly two cards, every vertex has degree $2$. Thus the resulting graph is $2$ regular, so it is a disjoint union of cycles. On an even cycle one may choose alternating edges, obtaining a perfect matching. The only point that requires checking is that every cycle is even. The graph comes from a chessboard colored grid, hence it is bipartite, and every cycle in a bipartite graph is even.

For arbitrary rectangles the previous graph model disappears. The condition that each cell belongs to exactly two cards gives a system of equations of the form $x_A+x_B=1$, where $A$ and $B$ are the two cards covering a given cell. If the graph whose vertices are the cards and whose edges correspond to nonempty regions covered by exactly two cards contains an odd cycle, the system is inconsistent. Thus one should look for a rectangular realization of an odd cycle.

For $1\times3$ cards the graph on cells becomes a $3$ uniform hypergraph. A $2$ regular $3$ uniform hypergraph need not possess a perfect matching. The smallest obstruction is the $6$ vertex configuration with four triples

$${1,2,3},\quad {1,4,5},\quad {2,4,6},\quad {3,5,6}.$$

Each vertex belongs to exactly two triples, but no subfamily covers every vertex exactly once. This configuration can be realized by $1\times3$ cards.

The crucial point is the domino case: proving that the cycles are even and that alternating choices on each cycle produce a single covering.

Problem Understanding

This is a Type D problem. We must determine whether a suitable subfamily of the cards can always be chosen so that every cell is covered exactly once.

For $1\times2$ cards the statement should be true because the double covering defines a $2$ regular bipartite graph, and such a graph decomposes into even cycles. Choosing alternating dominoes on each cycle leaves every cell covered exactly once.

For arbitrary rectangles the statement is false. An odd cycle in the card incidence graph produces contradictory parity conditions.

For $1\times3$ cards the statement is also false. There exist double coverings corresponding to a $2$ regular $3$ uniform hypergraph with no perfect matching.

Proof Architecture

The first lemma states that a double covering by dominoes defines a graph whose vertices are the cells and whose edges are the dominoes; every vertex has degree $2$.

The second lemma states that this graph is bipartite, hence every connected component is an even cycle.

The third lemma states that on every even cycle, selecting alternating edges covers each vertex exactly once.

The negative answer for arbitrary rectangles is obtained from an explicit odd cycle of cards. The equations imposed by the cells force alternating values around the cycle and become inconsistent when the cycle length is odd.

The negative answer for $1\times3$ cards is obtained from a concrete $2$ regular $3$ uniform hypergraph with no perfect matching, together with a realization by $1\times3$ cards.

The hardest point is the domino case, because one must show that the graph is a union of even cycles and that the alternating choice indeed yields a single covering.

Solution

Assume first that every card is a $1\times2$ rectangle.

Associate a vertex with each cell of the sheet. To every domino associate the edge joining the two cells covered by that domino.

Since every cell is covered by exactly two dominoes, exactly two edges are incident with each vertex. Hence every vertex has degree $2$.

Color the cells of the grid in the usual chessboard fashion. Every domino covers one black cell and one white cell, so every edge joins vertices of opposite colors. The graph is bipartite.

A finite graph in which every vertex has degree $2$ is a disjoint union of cycles. Since the graph is bipartite, every cycle has even length.

Consider one such cycle. Choose every second edge around the cycle. Each vertex of the cycle is incident with exactly one chosen edge. Performing this construction independently on every cycle produces a set of dominoes such that every cell belongs to exactly one chosen domino.

Thus a single layer can always be selected when all cards are $1\times2$.

Now consider arbitrary rectangular cards.

Construct five rectangular cards whose pairwise overlap pattern forms a cycle

$$R_1R_2R_3R_4R_5R_1,$$

with no other overlaps, and such that the regions

$$R_1\cap R_2,; R_2\cap R_3,; R_3\cap R_4,; R_4\cap R_5,; R_5\cap R_1$$

partition the sheet. Every cell then belongs to exactly two cards.

Suppose a single layer could be selected. Let $x_i\in{0,1}$ indicate whether $R_i$ is chosen. On every region $R_i\cap R_{i+1}$ exactly one of the two cards must be chosen, so

$$x_i+x_{i+1}=1$$

for all $i$, indices taken modulo $5$.

From

$$x_1+x_2=1,\qquad x_2+x_3=1$$

we obtain $x_1=x_3$. Continuing around the cycle gives

$$x_1=x_3=x_5, \qquad x_2=x_4.$$

The equation $x_5+x_1=1$ then becomes

$$2x_1=1,$$

which is impossible.

Hence the statement is false for arbitrary rectangles.

Finally consider $1\times3$ cards.

Take six cells labelled $1,\dots,6$ and four cards corresponding to the triples

$$T_1={1,2,3}, \quad T_2={1,4,5}, \quad T_3={2,4,6}, \quad T_4={3,5,6}.$$

Each cell belongs to exactly two cards:

$$1\in T_1,T_2,\quad 2\in T_1,T_3,\quad 3\in T_1,T_4,$$

$$4\in T_2,T_3,\quad 5\in T_2,T_4,\quad 6\in T_3,T_4.$$

Suppose a subfamily covered every cell exactly once. Let $y_i\in{0,1}$ indicate whether $T_i$ is chosen. The six cells give the equations

$$y_1+y_2=1,\quad y_1+y_3=1,\quad y_1+y_4=1,$$

$$y_2+y_3=1,\quad y_2+y_4=1,\quad y_3+y_4=1.$$

The first three equations imply

$$y_2=y_3=y_4.$$

Substituting into $y_2+y_3=1$ yields

$$2y_2=1,$$

a contradiction.

Therefore no single layer exists. This configuration can be realized geometrically by $1\times3$ cards, so the statement is false for $1\times3$ cards as well.

The answers are: true for $1\times2$ cards, false for arbitrary rectangles, and false for $1\times3$ cards.

$$\boxed{\text{Yes for }1\times2,\ \text{No for arbitrary rectangles,\ No for }1\times3.}$$

Verification of Key Steps

For the domino case, the degree of a vertex equals the number of dominoes containing the corresponding cell. Since each cell is covered exactly twice, every vertex has degree $2$. No other interpretation of the coverin