AFTD Auto-Formalizing Theoretical Domains

four_type_simultaneous_balance_counts

theoremverified

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

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.

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

    lines 8–11

    uses Nat.mod_lt

      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)
  2. 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).

    lines 12–13

      interval_cases hma : a % 2 <;> interval_cases hmb : b % 2 <;>
        interval_cases hmc : c % 2 <;> interval_cases hmd : d % 2 <;>
  3. 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.

    lines 14–30

        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.

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