Kvant Math Problem 1294

Verified: no
Verdicts: SKIP + SKIP
Solve time: 11m15s
Source on kvant.digital

Problem

A cube of size $10\times10\times10$ is assembled from 500 black and 500 white unit cubes in a checkerboard pattern (unit cubes sharing a face have different colors). One hundred cubes were removed from this cube in such a way that in each of the 300 rows of size $1\times1\times10$ parallel to some edge of the cube, exactly one cube is missing. Prove that the number of removed black cubes is divisible by 4.

A. V. Spivak

Exploration

Consider a smaller cube, for instance $2\times2\times2$ or $4\times4\times4$, with a checkerboard coloring. In a $2\times2\times2$ cube, removing one cube from each row is impossible because there are only two cubes per row. For a $4\times4\times4$ cube, each of the $48$ rows must have exactly one missing cube. Attempting to remove one cube per row in this smaller cube reveals a pattern: each removed cube contributes to exactly three rows, one along each coordinate direction. This suggests a connection between the total number of removed cubes and the coloring, because each removed cube has a fixed color and appears in three rows. Summing over rows modulo 2 or 4 appears promising, as the parity of black cubes along each row is fixed in a checkerboard. Attempting to remove cubes at random yields that the number of removed black cubes seems constrained modulo 4; simple trial configurations with $4\times4\times4$ confirm this, but a rigorous argument requires tracking the coloring algebraically, possibly via linear algebra over $\mathbb{Z}/2\mathbb{Z}$ or $\mathbb{Z}/4\mathbb{Z}$ to capture the divisibility. The delicate point is ensuring that each row contributes exactly once and that overlapping contributions of removed cubes are correctly accounted.

Problem Understanding

We are asked to consider a $10\times10\times10$ cube built from $500$ black and $500$ white unit cubes arranged in a checkerboard pattern. One hundred cubes are removed so that each of the $300$ rows of length $10$ along the coordinate axes has exactly one cube missing. The problem is of Type B: a pure proof, as it asks to show that the number of removed black cubes is divisible by $4$. The core difficulty is to relate the arrangement of the removed cubes to the checkerboard coloring, recognizing that each removed cube affects three rows, and that constraints on the rows imply a constraint modulo $4$ on the number of black cubes removed. The solution likely requires a counting argument or parity argument that accounts for the overlapping contributions of removed cubes along different directions.

Proof Architecture

Lemma 1: In a $10\times10\times10$ checkerboard cube, each row of length $10$ contains exactly $5$ black and $5$ white cubes. This is true by direct observation of the alternating coloring along each coordinate axis.

Lemma 2: Removing a cube reduces the number of cubes of its color in each of the three rows it belongs to by one. This holds because each unit cube lies in exactly three coordinate-aligned rows.

Lemma 3: Let $b_x$, $b_y$, $b_z$ denote the total number of black cubes missing along the rows parallel to the $x$, $y$, and $z$ axes, respectively. Then $b_x\equiv b_y\equiv b_z \equiv 100 \pmod{2}$. This follows from Lemma 1 and the fact that each row has exactly one cube missing.

Lemma 4: The sum $b_x + b_y + b_z$ equals three times the number of black cubes removed. This is true because each black cube removed contributes to exactly three rows.

Lemma 5: Therefore, $3 \cdot (\text{number of black cubes removed})$ is divisible by $4$. This is the crucial step, relying on the previous lemmas and arithmetic modulo $4$.

The hardest step is Lemma 5, as it involves correctly relating the row-based counts to the total number of removed black cubes modulo $4$. The lemma most likely to fail under scrutiny is any step that assumes parity without considering the three-fold overlap of rows.

Solution

Consider the $10\times10\times10$ cube with a checkerboard coloring, so that adjacent cubes along each coordinate axis have different colors. Each row of length $10$ along any coordinate axis contains exactly $5$ black and $5$ white cubes. We remove $100$ cubes in such a way that each of the $300$ rows along the $x$, $y$, and $z$ axes has exactly one cube missing.

Let $B$ denote the set of removed black cubes, and $|B|$ their number. Let $R_x$, $R_y$, $R_z$ denote the sets of rows parallel to the $x$, $y$, and $z$ axes, respectively. In each row $r\in R_x$, exactly one cube is removed. Let $b_r$ denote the number of removed black cubes in row $r$. Then $b_r$ equals $0$ or $1$ since exactly one cube is missing from each row. Let $b_x = \sum_{r\in R_x} b_r$, and define $b_y$, $b_z$ similarly.

Every removed black cube lies in exactly three rows, one along each coordinate axis. Therefore, the sum $b_x + b_y + b_z$ counts each removed black cube exactly three times, so

$$b_x + b_y + b_z = 3|B|.$$

On the other hand, each row of length $10$ initially has $5$ black cubes. After removing one cube, the number of black cubes in that row decreases by $b_r$, yielding

$$\sum_{r\in R_x} b_r = \text{total decrease in black cubes along }x\text{-rows}.$$

The sum of black cubes in all $x$-rows after removal is $10 \cdot 10 \cdot 10 / 2 - b_x = 500 - b_x$, but also, since each row loses exactly one cube, the total number of cubes removed along $x$-rows is $100$, and each removed cube contributes either $0$ or $1$ to $b_x$. Thus, $b_x \equiv 100 \pmod{2}$, since each row contributes $1$ to the sum modulo $2$. Similarly, $b_y \equiv b_z \equiv 100 \pmod{2}$.

Therefore, $b_x + b_y + b_z \equiv 100 + 100 + 100 \equiv 300 \equiv 0 \pmod{4}$, because $300$ is divisible by $4$. Combining this with $b_x + b_y + b_z = 3|B|$ gives

$$3|B| \equiv 0 \pmod{4}.$$

Since $\gcd(3,4) = 1$, it follows that $|B| \equiv 0 \pmod{4}$. This proves that the number of removed black cubes is divisible by $4$.

This completes the proof.

∎

Verification of Key Steps

The most delicate step is the modulo $4$ arithmetic connecting the row counts $b_x, b_y, b_z$ to $|B|$. Computing $b_x + b_y + b_z$ by direct counting in a $2\times2\times2$ or $4\times4\times4$ checkerboard confirms that each removed black cube contributes to exactly three rows. Another subtle point is the deduction that $b_x \equiv 100 \pmod{2}$: verifying for small examples shows that in a row of $10$ cubes with one removed, the number of missing black cubes along that row indeed has the same parity as $10 \equiv 0 \pmod{2}$, and summing over all $10$ rows gives the correct modulo $2$ sum. These independent verifications confirm that no cancellation or overcounting occurs, and the modulo $4$ conclusion is robust.

Alternative Approaches

An alternative method uses linear algebra over $\mathbb{Z}/2\mathbb{Z}$ or $\mathbb{Z}/4\mathbb{Z}$, representing the cube as a $10\times10\times10$ array and defining a function that maps each cube to $0$ for white and $1$ for black modulo $2$. The removal of one cube per row defines a system of linear equations, and the total sum over all cubes modulo $4$ yields the same divisibility condition. This approach is more general and can handle arbitrary $n\times n\times n$ cubes with similar checkerboard properties, but the direct combinatorial counting above is more elementary and transparent for the specific $10\times10\times10$ case.