four_type_simultaneous_balance_counts
Four type counts can be halved so that the total and each of the two high-type marginals are balanced to within one.
Statement
theorem four_type_simultaneous_balance_counts(a b c d : ℕ) :
∃ w x y z : ℕ,
w ≤ a ∧ x ≤ b ∧ y ≤ c ∧ z ≤ d ∧
w+x+y+z ≤ (a+b+c+d+1)/2 ∧
(a-w)+(b-x)+(c-y)+(d-z) ≤ (a+b+c+d+1)/2 ∧
x+z ≤ (b+d+1)/2 ∧ (b-x)+(d-z) ≤ (b+d+1)/2 ∧
y+z ≤ (c+d+1)/2 ∧ (c-y)+(d-z) ≤ (c+d+1)/2- Source
- Elementary arithmetic for the bivalued two-agent rounding route in IN-570.
- Verified
- 06 Nov 2026
- Axioms
Quot.soundpropext- Used by 1
- two_finite_subsets_simultaneously_balancedGiven two subsets of a finite set, one can split the underlying set into two parts so that the two part sizes and the counts of elements…
The proof, explained
The proof proceeds by finite parity case analysis. Because balance conditions when dividing counts by 2 depend only on the parities of a, b, c, and d, the problem reduces to 16 parity configurations. In each configuration, the proof searches through all 16 candidate tuples obtained by rounding each variable either down (n / 2) or up ((n + 1) / 2), with the Presburger arithmetic tactic `omega` verifying that the matching candidate satisfies all bounds and balance inequalities.
The remainder modulo 2 of each count a, b, c, and d is strictly less than 2.
Applying `Nat.mod_lt` with 0 < 2 (verified by linear arithmetic) establishes that a % 2, b % 2, c % 2, and d % 2 are all strictly less than 2, so each is either 0 or 1.
uses
Nat.mod_lthave ha : a % 2 < 2 := Nat.mod_lt _ (by omega) have hb : b % 2 < 2 := Nat.mod_lt _ (by omega) have hc : c % 2 < 2 := Nat.mod_lt _ (by omega) have hd : d % 2 < 2 := Nat.mod_lt _ (by omega)
The problem is reduced to 16 cases according to the parities of a, b, c, and d.
Using `interval_cases` on each remainder modulo 2 exhaustively breaks the goal into 2⁴ = 16 cases, one for each parity combination of (a, b, c, d).
interval_cases hma : a % 2 <;> interval_cases hmb : b % 2 <;> interval_cases hmc : c % 2 <;> interval_cases hmd : d % 2 <;>In each parity configuration, at least one combination of floor and ceiling halvings satisfies all ten bounds and balance conditions. automation
For each count n, halving can be rounded down as n / 2 or rounded up as (n + 1) / 2. The `first` tactic sequentially tests all 16 candidate tuples (w, x, y, z) formed by choosing floor or ceiling for each component. In each of the 16 parity cases, the matching candidate provides the existential witness via `refine`, and Presburger arithmetic (`omega`) automatically proves the ten inequalities: the four individual bounds (w ≤ a, x ≤ b, y ≤ c, z ≤ d), the two bounds for the total sum, and the two bounds for each of the two marginal sums.
first | refine ⟨a / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
Nat.mod_lt- For any natural numbers x and y, if 0 < y, then x % y < y.
- The proof delegates all arithmetic verification across the 16 parity cases to automation: for each parity combination, it tests candidates among all combinations of floor and ceiling halvings, relying entirely on the `omega` decision procedure to check the 10 resulting linear inequalities.
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 four_type_simultaneous_balance_counts(a b c d : ℕ) : ∃ w x y z : ℕ, w ≤ a ∧ x ≤ b ∧ y ≤ c ∧ z ≤ d ∧ w+x+y+z ≤ (a+b+c+d+1)/2 ∧ (a-w)+(b-x)+(c-y)+(d-z) ≤ (a+b+c+d+1)/2 ∧ x+z ≤ (b+d+1)/2 ∧ (b-x)+(d-z) ≤ (b+d+1)/2 ∧ y+z ≤ (c+d+1)/2 ∧ (c-y)+(d-z) ≤ (c+d+1)/2 := by have ha : a % 2 < 2 := Nat.mod_lt _ (by omega) have hb : b % 2 < 2 := Nat.mod_lt _ (by omega) have hc : c % 2 < 2 := Nat.mod_lt _ (by omega) have hd : d % 2 < 2 := Nat.mod_lt _ (by omega) interval_cases hma : a % 2 <;> interval_cases hmb : b % 2 <;> interval_cases hmc : c % 2 <;> interval_cases hmd : d % 2 <;> first | refine ⟨a / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega