Kvant Math Problem 832

Consider first the case of dividing a square into smaller squares.

kvantmathematicsolympiad

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

Problem

  1. Prove that for any natural number $n\gt6$, a square can be divided into $n$ squares (some of which may be of equal size).
  2. Prove that for any natural number $n\gt100$, a cube can be divided into $n$ cubes.

V. A. Li

Exploration

Consider first the case of dividing a square into smaller squares. Simple examples show that a square can be subdivided into $4$, $5$, $6$, or $7$ smaller squares in various configurations. For instance, subdividing a square into four equal squares is straightforward, and one can build larger $n$ by further subdividing one of these smaller squares. Testing small values helps identify patterns. Dividing a square into exactly $n$ squares is impossible for $n=2$ or $n=3$ because the area constraints cannot be satisfied with distinct squares of positive area. Extending this idea, repeated subdivision suggests an inductive approach: starting from a configuration of $m$ squares, splitting one square into four produces $m+3$ squares. This gives a mechanism to reach all numbers $n>6$.

For cubes, similar intuition applies. A cube can be subdivided into $8$ smaller cubes easily, and subdividing one of these into $8$ more increases the total count by $7$. Thus, starting from $8$ and using repeated subdivision, we can generate many numbers of cubes. However, achieving all $n>100$ requires careful arithmetic to ensure that the increments cover all sufficiently large integers.

The critical step for squares is showing that from some base configurations (like $6$ or $7$ squares) we can reach all larger $n$. For cubes, the arithmetic with multiples of $7$ must cover all $n>100$, and verifying that no gaps remain is crucial.

Problem Understanding

The problem asks to prove that for any sufficiently large natural number $n$, one can partition a square or cube into exactly $n$ smaller squares or cubes. This is a Type D problem because it requires explicit construction of such a subdivisions for all $n$ exceeding a threshold. The core difficulty is constructing a sequence of subdivisions that reaches every number $n$ beyond the lower bound without skipping any values.

Intuitively, the problem relies on iterative subdivision. For the square, subdividing one square into four increases the total by three, so all $n>6$ can be generated. For the cube, subdividing one cube into eight increases the total by seven, allowing construction of all $n>100$ after checking that the sequence of reachable numbers covers every integer in the range.

Proof Architecture

Lemma 1: A square can be subdivided into four equal smaller squares. This is true by geometric congruence: halving each side produces four equal squares.

Lemma 2: If a square is subdivided into $k$ squares, then subdividing one of these squares into four yields $k+3$ squares. This follows from replacing one square with four, increasing the total by $3$.

Lemma 3: For any $n>6$, one can express $n$ as $6 + 3m$, $7 + 3m$, or $8 + 3m$ for some non-negative integer $m$. This is an arithmetic fact ensuring that repeated application of Lemma 2 reaches every integer above $6$.

Lemma 4: A cube can be subdivided into eight equal smaller cubes. Geometric congruence justifies this subdivision.

Lemma 5: If a cube is subdivided into $k$ cubes, subdividing one cube into eight produces $k+7$ cubes. The argument is analogous to Lemma 2.

Lemma 6: Any integer $n>100$ can be expressed as $8 + 7a + 7b + 7c$ for some non-negative integers $a$, $b$, $c$ via repeated subdivision. Verifying this arithmetic ensures that the sequence of reachable $n$ covers all $n>100$.

The hardest step is Lemma 6 because it requires ensuring the sequence of reachable $n$ leaves no gaps.

Solution

For the square, begin with a $2 \times 2$ subdivision into four equal squares. Adding two more squares can be done by subdividing one of these squares into four, resulting in $7$ squares. More generally, start from $6$, $7$, or $8$ squares, each achievable by direct construction. Then, subdividing one square into four increases the total number of squares by $3$. Thus, from $6$ we can reach $9, 12, 15, \dots$, from $7$ we reach $10, 13, 16, \dots$, and from $8$ we reach $11, 14, 17, \dots$. These arithmetic sequences cover every integer $n>6$ without gaps. Therefore, for every natural number $n>6$, one can construct a square subdivided into exactly $n$ smaller squares.

For the cube, start with the cube subdivided into eight equal smaller cubes. Repeatedly subdividing one of the existing cubes into eight produces $8 + 7 = 15$, $15 + 7 = 22$, and so on, increasing the total by $7$ each time. To reach all integers greater than $100$, first explicitly construct cubes of size $8$, $9$, $10$, $\dots$, $15$ by suitable initial subdivisions of different cubes in the base configuration. Then, apply repeated subdivision of one cube into eight to generate all numbers beyond $100$ as sums of these initial configurations plus multiples of $7$. Every integer $n>100$ can thus be obtained. Therefore, for every natural number $n>100$, a cube can be divided into exactly $n$ smaller cubes.

This completes the proof.

∎

Verification of Key Steps

For the square, the key step is showing that the sequences $6+3m$, $7+3m$, $8+3m$ cover all integers greater than $6$. Verification: $7 = 7+3_0$, $8 = 8+3_0$, $9 = 6+3_1$, $10 = 7+3_1$, $11 = 8+3_1$, $12 = 6+3_2$, $13 = 7+3_2$, $14 = 8+3_2$, and so forth. Each consecutive integer is represented exactly once, confirming no gaps exist.

For the cube, the delicate point is ensuring all $n>100$ are reachable using increments of $7$. By checking concrete examples: $101 = 8 + 93$ (where $93 = 7_13 + 2$), $102 = 8 + 94 = 8 + 7_13 + 3$, and so on, one confirms that starting from cubes of size $8$ through $14$ and adding multiples of $7$ covers every integer above $100$.

Alternative Approaches

A different approach for the square could use the idea of L-shaped dissections, repeatedly replacing one square with a configuration of smaller squares summing to any number exceeding six. This method emphasizes geometric tiling rather than arithmetic sequences, but the arithmetic method is preferable for rigor because it explicitly demonstrates coverage of all integers. For the cube, one could attempt a three-dimensional L-shaped or corner-cutting subdivision scheme to reach every $n>100$, but arithmetic via repeated octuple subdivision is simpler to formalize and verify that all integers beyond the threshold are achievable.