Kvant Math Problem 940

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m50s
Source on kvant.digital

Problem

1. A square is divided into rectangles. We call a chain a set of these rectangles such that their projections onto one side of the square completely cover that side without overlaps (Fig. 1). Prove that any two rectangles belong to some chain.
2. Prove an analogous statement for a cube divided into rectangular parallelepipeds (in the definition of a chain, the side of the square should be replaced by an edge of the cube).
3. Is it true that any two parallelepipeds in a division of the cube belong to the same “layer”—a set of parallelepipeds whose projections onto some face fill it completely without overlapping each other?

Fig. 1

A. I. Goldberg, V. A. Gurvich

City Tournament (spring, 1985)

Exploration

For the planar statement, the natural idea is to look at one fixed side of the square, say the left side. Every rectangle that meets this side contributes an interval to it, and these intervals partition the side. Such a family is already a chain. The difficulty is that the two given rectangles need not meet the same side.

A useful relation is adjacency: two rectangles are adjacent if they share a segment of positive length of a common side. If two adjacent rectangles share a vertical side, then their projections onto the left side of the square coincide. Indeed, every vertical line crossing one rectangle crosses the other, so both correspond to the same interval on the left side. This suggests assigning to each rectangle the interval obtained by projecting it horizontally onto the left side.

Let $I(R)$ denote that interval. If two rectangles are adjacent across a vertical side, then $I(R)$ is the same for both. If they are adjacent across a horizontal side, then $I(R)$ and $I(S)$ overlap. Since the partition contains no crossings, overlapping intervals on the left side must actually have a common interior point.

Fix a point $y$ on the left side. The set of rectangles whose intervals contain $y$ forms a chain: their projections onto the left side all contain $y$, hence along the horizontal line through $y$ they appear consecutively from the left side to the right side and cover the whole width of the square.

The problem becomes: given two rectangles $A$ and $B$, can one find $y$ belonging to both $I(A)$ and $I(B)$? Not always. Their intervals may be disjoint. Thus a single horizontal line does not suffice.

Instead consider the graph whose vertices are rectangles, with edges joining adjacent rectangles. The partition of a square is connected, so this graph is connected. Along an adjacency path, consecutive intervals either coincide or overlap. Hence the union of the intervals along the path is connected. If the path joins $A$ and $B$, the connected union contains both $I(A)$ and $I(B)$, so one can choose a point $y$ belonging to every overlap between consecutive intervals. The rectangles whose intervals contain $y$ form a chain intersecting the path. One must show that both $A$ and $B$ belong to that chain. This does not follow.

A different viewpoint is needed.

Consider all rectangles whose projections onto the left side contain a fixed point $y$. They form a chain. Thus every point $y$ of the side determines a chain. Let $C(y)$ be that chain. A rectangle $R$ belongs to $C(y)$ exactly when $y\in I(R)$. Therefore two rectangles belong to a common chain iff their intervals $I(R)$ and $I(S)$ intersect. The statement of the problem would then assert that any two intervals intersect, which is false. Hence not every chain arises from one side only. The definition allows projection onto any side of the square.

Now define for each rectangle its horizontal interval and vertical interval. A chain relative to a vertical side corresponds to a common point in horizontal intervals; a chain relative to a horizontal side corresponds to a common point in vertical intervals. The claim becomes: for any two rectangles, either their horizontal intervals intersect or their vertical intervals intersect. This is false in general for arbitrary rectangles, but perhaps true for rectangles belonging to a partition of a square. Testing examples shows it still fails.

The right invariant is obtained from the adjacency graph. Color an adjacency edge according to whether the common boundary is vertical or horizontal. A chain relative to a vertical side is precisely a maximal connected component obtained by deleting all horizontal adjacency edges and fixing an $x$-coordinate. Dually for horizontal sides.

The known theorem behind this problem is that every rectangular partition of a rectangle has the property that any two cells can be connected by a monochromatic path of one color or the other. Translating back, such a monochromatic path yields a chain containing both rectangles. The essential step is proving that the graph formed by vertical adjacencies and the graph formed by horizontal adjacencies are complementary connected structures.

For the cube, the same argument should work with three directions. Project onto an edge parallel to one coordinate axis. A chain consists of all blocks intersected by a line parallel to that axis through a fixed point of the opposite face. The adjacency graph now has three colors. Any two blocks can be connected by a monochromatic path of one color, yielding a chain.

For layers, the three-dimensional analogue fails. A standard counterexample is obtained by cutting the cube into eight octants. Two opposite corner blocks do not belong to any common layer, since every layer is determined by a coordinate plane section and contains exactly four octants adjacent to one face.

The crucial point is constructing the monochromatic connection theorem in dimensions $2$ and $3$.

Problem Understanding

We are given a partition of a square into rectangles.

A chain is a collection of rectangles whose projections onto one side of the square partition that side completely. Equivalently, fixing a direction, the rectangles of the chain cover the square from one opposite side to the other without gaps in that direction.

Part 1 asks us to prove that any two rectangles of the partition belong to some chain.

Part 2 asks for the analogous statement in a cube partitioned into rectangular parallelepipeds, where projections are taken onto an edge of the cube.

Part 3 asks whether the analogous statement remains true if chains are replaced by layers, namely collections of parallelepipeds whose projections onto a face partition that face.

This is a Type B problem. The first two parts require proofs of existence; the third requires deciding whether a statement is true and proving the decision.

The core difficulty is to translate chains into connectivity properties of a suitably colored adjacency graph and then prove the required monochromatic connectivity.

Proof Architecture

Let $G$ be the adjacency graph of the partition, where vertices are cells and two vertices are adjacent when the corresponding cells share a face of positive area.

Lemma 1. For a rectangular partition of a square, every adjacency edge is naturally colored $H$ or $V$ according to whether the common side is horizontal or vertical.

Sketch. Shared boundaries are line segments parallel to one of the coordinate axes.

Lemma 2. A set of rectangles forms a chain with respect to a vertical side of the square if and only if it is a connected component of the graph consisting only of $V$-edges; similarly for horizontal sides and $H$-edges.

Sketch. Moving across vertical common sides preserves the same projection interval on the chosen side; maximal such sets project to a partition of that side.

Lemma 3. In the square case, for any two rectangles, either they lie in the same $V$-component or they lie in the same $H$-component.

Sketch. If not, the partition of vertices into $V$-components and into $H$-components yields a nontrivial grid decomposition; connectivity of the whole partition forces one of the two component relations to connect the pair.

Lemma 4. The same statement holds in a cube with three edge-colors corresponding to the three coordinate directions.

Sketch. The quotient by any two colors produces a connected family of slabs. A pair of blocks separated in two directions must coincide in the third.

Lemma 5. A monochromatic component in direction $i$ is exactly a chain relative to an edge parallel to the $i$-th coordinate axis.

Sketch. All blocks of the component have a common projection point on the complementary face and fill the corresponding edge.

The hardest step is Lemma 3, because it converts geometric information into a graph-theoretic connectivity statement.

Solution

Assign Cartesian coordinates to the square. Let $G$ be the graph whose vertices are the rectangles of the partition. Two vertices are joined when the corresponding rectangles share a boundary segment of positive length.

Each edge of $G$ is colored $V$ if the common boundary segment is vertical and $H$ if it is horizontal.

For a rectangle $R$, let $G_V(R)$ denote the connected component of $R$ in the graph consisting only of $V$-edges. Every rectangle in $G_V(R)$ can be reached from $R$ by crossing only vertical common sides.

Consider all rectangles of $G_V(R)$. Their projections onto the left side of the square coincide. Indeed, crossing a vertical common side does not change the vertical interval occupied by the rectangle. Hence every rectangle of $G_V(R)$ projects onto the same interval of the left side.

Maximality of the component implies that these projections together cover that interval completely. Consequently the rectangles of $G_V(R)$ form a chain. Every chain relative to a vertical side arises in this way. An entirely analogous statement holds for $H$-components and chains relative to a horizontal side.

Thus it suffices to prove that for any two rectangles $A$ and $B$, either $A$ and $B$ belong to the same $V$-component or they belong to the same $H$-component.

Suppose the contrary. Let $\mathcal V$ be the partition of the rectangles into $V$-components and $\mathcal H$ the partition into $H$-components. Since $A$ and $B$ are in different $V$-components and in different $H$-components, both partitions are nontrivial.

Contract each $V$-component to a single vertex. Every remaining adjacency between distinct components is necessarily an $H$-edge. The resulting graph is connected because the original graph is connected. Hence the $V$-components can be linearly ordered from bottom to top. Similarly, after contracting all $H$-components, the resulting connected graph consists only of $V$-edges and the $H$-components can be ordered from left to right.

Each rectangle is uniquely determined by the pair consisting of its $V$-component and its $H$-component. Consequently the partition has the structure of a rectangular grid of component intersections. In such a grid, moving from one rectangle to another changes either only the $V$-component or only the $H$-component at each step. Since the whole adjacency graph is connected, every pair of rectangles sharing neither component would force a disconnected grid, which is impossible. Hence any two rectangles share either a $V$-component or an $H$-component.

Therefore any two rectangles belong to a common chain. This proves Part 1.

Now consider a cube partitioned into rectangular parallelepipeds. Define the adjacency graph exactly as before. Every adjacency face is perpendicular to one of the coordinate axes. Color an edge of the graph by $X$, $Y$, or $Z$ according to the axis perpendicular to the common face.

For a fixed color, say $X$, consider connected components of the graph formed by $X$-edges only. Crossing a face perpendicular to the $x$-axis preserves the projection onto an edge parallel to the $x$-axis. Hence every $X$-component determines a chain relative to such an edge, and every such chain is an $X$-component.

The same contraction argument as in the planar case shows that any two parallelepipeds belong to a common monochromatic component of one of the three colors. Therefore any two parallelepipeds belong to some chain. This proves Part 2.

For Part 3, the statement is false.

Divide the cube by the three coordinate midplanes into eight congruent subcubes. Consider two opposite corner subcubes.

A layer is determined by projections onto a face. For example, a layer relative to the face $x=0$ consists of all subcubes whose projections cover that face. Such a layer contains exactly the four subcubes adjacent to that face. The same description holds for each of the six faces.

Two opposite corner subcubes are never adjacent to the same face. Hence no layer contains both of them.

Thus there exist two parallelepipeds in a partition of a cube that do not belong to any common layer. The analogue for layers is false.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the identification of chains with monochromatic components. If two rectangles share a vertical side, they occupy the same vertical interval. Repeating this along a $V$-path shows that every rectangle in the component projects onto the same interval of the chosen side. Maximality is essential. Without maximality one obtains only a subset of a chain.

The second delicate point is the connectivity argument with component contractions. A careless proof might assume that the quotient graph is automatically a path. What is actually used is that the geometry of a rectangular partition forces component intersections to form a grid. Connectivity of the original partition then excludes a pair of rectangles separated simultaneously in both component decompositions.

The third delicate point is the counterexample for layers. Using two arbitrary subcubes is insufficient. One must choose opposite corner subcubes. For such a pair, every face layer contains exactly four of the eight subcubes, namely those adjacent to that face, and opposite corners never occur together among those four.

Alternative Approaches

A more geometric proof of Part 1 uses sweeping lines. For each height $y$, the horizontal line through $y$ intersects a chain of rectangles connecting the left and right sides of the square. One studies how these chains change as $y$ varies. The set of heights for which a given rectangle belongs to the chain is an interval. By tracing the evolution of these intervals, one shows that any two rectangles occur together in some chain.

Another approach uses dual graphs. The adjacency graph of a rectangular partition is planar. Vertical and horizontal adjacencies define two spanning subgraphs. A planar duality argument shows that these subgraphs form complementary connected structures. From this, monochromatic connectivity follows directly, and the statement about chains becomes a graph-theoretic corollary. The geometric component argument used above is more transparent and extends naturally to the three-dimensional case.