AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_area_sum

theoremverified

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

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$.

  1. 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$.

    line 4

    uses mondrian_cells_union_card

      have hc := mondrian_cells_union_card P (h.2.2.1.imp fun h => h.1)
  2. 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.

    line 5

      rw [h.2.2.2] at hc
  3. 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$.

    line 6

    uses pow_two

      simpa [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$).

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

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
See it in the graphDiscuss this resultChallenge it