mondrian_partition_area_sum
The areas of an admissible partition of the n-square sum to n squared.
Statement
theorem mondrian_partition_area_sum (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(h : mondrian_is_partition n P) :
(P.map mondrian_rect_area).sum = n ^ 2- Source
- arXiv:2610.19193, Section 1, and arXiv:2311.02385, Section 3 (available integer dimension pairs); helper for OP-280 and mondrian_no_perfect_partition.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- mondrian_cells_union_cardFor a list of rectangles with pairwise disjoint cell sets, the cardinality of their union equals the sum of their areas.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_cellsThe unit cells [i,i+1]×[j,j+1] of the integer rectangle [x₀,x₁]×[y₀,y₁], recorded as r = (x₀, x₁, y₀, y₁); a cell is named by its…
- mondrian_rect_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
- Used by 1
- mondrian_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
The proof, explained
By definition of a Mondrian partition, the rectangles in $P$ are pairwise disjoint and together cover the entire $n \times n$ grid. Because the rectangles are disjoint, the sum of their areas equals the cardinality of their union. Since their union is the $n \times n$ grid, which contains $n^2$ cells, the sum of their areas is $n^2$.
The number of cells in the union of rectangles in $P$ equals the sum of their individual areas.
An admissible Mondrian partition requires the rectangles in $P$ to be pairwise disjoint. Discarding the non-congruence condition leaves the pairwise disjointness hypothesis needed to apply `mondrian_cells_union_card`, establishing that the total number of cells in the union is the sum of the areas of the rectangles in $P$.
uses
mondrian_cells_union_cardhave hc := mondrian_cells_union_card P (h.2.2.1.imp fun h => h.1)
The number of cells in the $n \times n$ grid equals the sum of the areas of the rectangles in $P$.
By the definition of a Mondrian partition, the union of the cells of the rectangles in $P$ covers the entire grid $\{0, \dots, n-1\} \times \{0, \dots, n-1\}$ (`Finset.range n ×ˢ Finset.range n`). Rewriting this union with the grid in the previous equality yields the claim.
rw [h.2.2.2] at hc
The sum of the areas of the rectangles in $P$ is $n^2$. automation
Symmetrizing the equality and simplifying using `pow_two` equates the sum of rectangle areas to the cardinality of the $n \times n$ grid, which is $n \cdot n = n^2$.
uses
pow_twosimpa [pow_two] using hc.symm
mondrian_cells_union_card- If a list of rectangles are pairwise disjoint in their cell sets, the cardinality of the union of their cells is equal to the sum of their areas.
pow_two- In any monoid, the square of an element equals the element multiplied by itself ($a^2 = a \cdot a$).
- The simplification tactic `simpa` automatically computes the cardinality of the Cartesian product `Finset.range n ×ˢ Finset.range n` as `n * n` before rewriting with `pow_two`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem mondrian_partition_area_sum (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (h : mondrian_is_partition n P) : (P.map mondrian_rect_area).sum = n ^ 2 := by have hc := mondrian_cells_union_card P (h.2.2.1.imp fun h => h.1) rw [h.2.2.2] at hc simpa [pow_two] using hc.symm