op1525_flip_mono_pair_sum
For a finite set of pairs with c marked monochromatic, the sum over all individual-vertex flips of the resulting monochromatic-pair count is (2m−4)c+2m, where m is the number of pairs.
Statement
theorem op1525_flip_mono_pair_sum {I : Type*} [Fintype I] (s : I → Bool) : let c : ℤ := ∑ i : I, if s i then 1 else 0 (∑ i : I, 2 * (if s i then c - 1 else c + 1)) = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ)
- Source
- The monochromatic-pair deck average in the complete pair-part route to OP-1525.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
We compute the sum of the updated monochromatic-pair counts over all individual-vertex flips. For each pair $i$, the term $2(\text{if } s(i) \text{ then } c - 1 \text{ else } c + 1)$ is rewritten pointwise as $2(c+1) - 4 \cdot \mathbf{1}_{s(i)}$. Summing across all pairs, the constant part evaluates to $2|I|(c+1)$ and the indicator part sums to $4c$ by the definition of $c$. Expanding and rearranging terms in $c$ yields $(2|I| - 4)c + 2|I|$.
Define $c$ as the count of monochromatic pairs and set up the target equation.
We introduce the local definition $c = \sum_{i \in I} (\text{if } s(i) \text{ then } 1 \text{ else } 0)$, representing the number of monochromatic pairs, and restate the theorem's goal using this abbreviation.
classical let c : ℤ := ∑ i : I, if s i then 1 else 0 change (∑ i : I, 2 * (if s i then c - 1 else c + 1)) = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ)
Each term $2(\text{if } s(i) \text{ then } c - 1 \text{ else } c + 1)$ in the sum is algebraically equal to $2(c + 1) - 4(\text{if } s(i) \text{ then } 1 \text{ else } 0)$.
Using `Finset.sum_congr`, we reduce the equality of the two sums over $I$ to checking that their summands agree for each $i \in I$. A case analysis on the boolean value of $s(i)$ resolves this: if $s(i) = \text{false}$, both sides simplify to $2(c+1)$; if $s(i) = \text{true}$, the left-hand side is $2(c-1)$ and the right-hand side is $2(c+1) - 4$, which are equal by ring arithmetic.
uses
Finset.sum_congrcalc (∑ i : I, 2 * (if s i then c - 1 else c + 1)) = ∑ i : I, (2 * (c + 1) - 4 * (if s i then 1 else 0)) := by apply Finset.sum_congr rfl intro i _ cases h : s i <;> simp [h] <;> ring
The sum $\sum_{i \in I} (2(c + 1) - 4(\text{if } s(i) \text{ then } 1 \text{ else } 0))$ evaluates to $(2|I| - 4)c + 2|I|$.
Applying `Finset.sum_sub_distrib` splits the sum into $\sum_{i \in I} 2(c+1) - \sum_{i \in I} 4(\text{if } s(i) \text{ then } 1 \text{ else } 0)$. By `Finset.sum_const`, `Finset.card_univ`, and `nsmul_eq_mul`, the sum of the constant $2(c+1)$ over all elements evaluates to $|I| \cdot 2(c+1)$. Factoring out 4 via `Finset.mul_sum` leaves $4 \sum_{i \in I} (\text{if } s(i) \text{ then } 1 \text{ else } 0)$, which equals $4c$ by the definition of $c$. Expanding and collecting terms via ring arithmetic yields $|I| \cdot 2(c+1) - 4c = (2|I| - 4)c + 2|I|$.
uses
Finset.sum_sub_distrib,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,Finset.mul_sum_ = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ) := by rw [Finset.sum_sub_distrib] simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, ← Finset.mul_sum] have hh : (∑ i : I, if s i then (1 : ℤ) else 0) = c := rfl rw [hh] ring
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.sum_sub_distrib- The sum of a difference over a finite set equals the difference of the sums: $\sum_{x \in s} (f(x) - g(x)) = \sum_{x \in s} f(x) - \sum_{x \in s} g(x)$.
Finset.sum_const- The sum of a constant value $b$ over a finite set $s$ equals the cardinality of $s$ times $b$ (as natural scalar multiplication).
Finset.card_univ- The cardinality of the universal finset `Finset.univ` of a finite type is the cardinality of the type.
nsmul_eq_mul- Scalar multiplication of a ring element by a natural number $n$ equals multiplication by $n$ cast into the ring: $n • a = ↑n * a$.
Finset.mul_sum- A common factor outside a finite sum distributes across each summand: $a \cdot \sum_{i \in s} f(i) = \sum_{i \in s} a \cdot f(i)$.
- Line 17 uses `nsmul_eq_mul` to convert the natural-number scalar multiplication produced by `Finset.sum_const` into integer multiplication, a formal type-casting detail with no counterpart on paper.
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 op1525_flip_mono_pair_sum {I : Type*} [Fintype I] (s : I → Bool) : let c : ℤ := ∑ i : I, if s i then 1 else 0 (∑ i : I, 2 * (if s i then c - 1 else c + 1)) = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ) := by classical let c : ℤ := ∑ i : I, if s i then 1 else 0 change (∑ i : I, 2 * (if s i then c - 1 else c + 1)) = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ) calc (∑ i : I, 2 * (if s i then c - 1 else c + 1)) = ∑ i : I, (2 * (c + 1) - 4 * (if s i then 1 else 0)) := by apply Finset.sum_congr rfl intro i _ cases h : s i <;> simp [h] <;> ring _ = (2 * (Fintype.card I : ℤ) - 4) * c + 2 * (Fintype.card I : ℤ) := by rw [Finset.sum_sub_distrib] simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, ← Finset.mul_sum] have hh : (∑ i : I, if s i then (1 : ℤ) else 0) = c := rfl rw [hh] ring