AFTD Auto-Formalizing Theoretical Domains

two_finite_subsets_simultaneously_balanced

theoremverified

Given 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 from each subset differ by at most one.

Statement

theorem two_finite_subsets_simultaneously_balanced
    (m : ℕ) (A B : Finset (Fin m)) :
    ∃ S : Finset (Fin m),
      S.card ≤ (m + 1) / 2 ∧
      (Finset.univ \ S).card ≤ (m + 1) / 2 ∧
      (S ∩ A).card ≤ (A.card + 1) / 2 ∧
      (A \ S).card ≤ (A.card + 1) / 2 ∧
      (S ∩ B).card ≤ (B.card + 1) / 2 ∧
      (B \ S).card ≤ (B.card + 1) / 2
Source
Finite balancing lemma for the two-agent bivalued rounding argument in IN-570.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The ambient set Fin m is partitioned into four pairwise disjoint regions corresponding to the Venn diagram of A and B: Aᶜ \ B, Aᶜ ∩ B, A \ B, and A ∩ B. By applying a combinatorial lemma (four_type_simultaneous_balance_counts), we obtain integer sizes (w, x, y, z) bounded by the region sizes that simultaneously balance the total universe, the subset A, and the subset B. We then select disjoint subsets of the four regions having these exact cardinalities and form their union S, which is verified to satisfy all six desired balancing inequalities.

  1. The ambient universe is partitioned into four pairwise disjoint regions R₀, R₁, R₂, R₃ according to membership in A and B.

    We define R₀ = Aᶜ \ B, R₁ = Aᶜ ∩ B, R₂ = A \ B, and R₃ = A ∩ B. For each of the six pairs of regions, any element belonging to both would have contradictory membership properties in A and B, which Finset.disjoint_left.mpr establishes by propositional simplification.

    lines 10–49

    uses Finset.disjoint_left.mpr

      classical
      let R0 : Finset (Fin m) := (Finset.univ \ A) \ B
      let R1 : Finset (Fin m) := (Finset.univ \ A) ∩ B
      let R2 : Finset (Fin m) := A \ B
      let R3 : Finset (Fin m) := A ∩ B
      have d01 : Disjoint R0 R1 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R1, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d02 : Disjoint R0 R2 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R2, Finset.mem_sdiff,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d03 : Disjoint R0 R3 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d12 : Disjoint R1 R2 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R1, R2, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d13 : Disjoint R1 R3 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d23 : Disjoint R2 R3 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter] at hi hj
        tauto
  2. There exist non-negative integer counts w ≤ |R₀|, x ≤ |R₁|, y ≤ |R₂|, and z ≤ |R₃| that simultaneously balance the total size and the sizes of A and B.

    Applying the combinatorial lemma four_type_simultaneous_balance_counts to the sizes of the four regions produces integer counts (w, x, y, z) bounded by (|R₀|, |R₁|, |R₂|, |R₃|) such that the total sum w + x + y + z, the sum y + z (for A), and the sum x + z (for B), along with their complement sums, do not exceed ⌊(N + 1)/2⌋ for their respective total sizes.

    lines 50–51

    uses four_type_simultaneous_balance_counts

      obtain ⟨w, x, y, z, hw, hx, hy, hz, htot, htotc, hB, hBc, hA, hAc⟩ :=
        four_type_simultaneous_balance_counts R0.card R1.card R2.card R3.card
  3. There exist pairwise disjoint subsets W ⊆ R₀, X ⊆ R₁, Y ⊆ R₂, and Z ⊆ R₃ with cardinalities w, x, y, z respectively.

    By Finset.exists_subset_card_eq, each region contains a subset of the specified size because the target counts are bounded by the region sizes. Since the four regions are pairwise disjoint, any subsets chosen from them are automatically pairwise disjoint.

    lines 52–61

    uses Finset.exists_subset_card_eq

      obtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hw
      obtain ⟨X, hX, hXc⟩ := Finset.exists_subset_card_eq hx
      obtain ⟨Y, hY, hYc⟩ := Finset.exists_subset_card_eq hy
      obtain ⟨Z, hZ, hZc⟩ := Finset.exists_subset_card_eq hz
      have dWX : Disjoint W X := d01.mono hW hX
      have dWY : Disjoint W Y := d02.mono hW hY
      have dWZ : Disjoint W Z := d03.mono hW hZ
      have dXY : Disjoint X Y := d12.mono hX hY
      have dXZ : Disjoint X Z := d13.mono hX hZ
      have dYZ : Disjoint Y Z := d23.mono hY hZ
  4. The candidate subset S = W ∪ X ∪ Y ∪ Z has cardinality w + x + y + z.

    We define S as the union of W, X, Y, and Z. Because these four sets are pairwise disjoint, the cardinality of their union is the sum of their individual cardinalities by Finset.card_union_of_disjoint and associativity of addition (Nat.add_assoc).

    lines 62–65

    uses Finset.card_union_of_disjoint, Nat.add_assoc

      let S := W ∪ X ∪ Y ∪ Z
      have hSc : S.card = w + x + y + z := by
        simp [S, Finset.card_union_of_disjoint,
          dWX, dWY, dWZ, dXY, dXZ, dYZ, hWc, hXc, hYc, hZc, Nat.add_assoc]
  5. The union of the four regions is the entire universe, and the sum of their cardinalities equals m.

    Every element of the universe belongs to exactly one combination of memberships in A and B, so R₀ ∪ R₁ ∪ R₂ ∪ R₃ = univ. Applying congrArg with Finset.card and expanding the disjoint unions via Finset.card_union_of_disjoint shows that |R₀| + |R₁| + |R₂| + |R₃| = m.

    lines 66–75

    uses congrArg, Finset.card_union_of_disjoint, Nat.add_assoc

      have hR : R0 ∪ R1 ∪ R2 ∪ R3 = Finset.univ := by
        ext t
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_union, Finset.mem_univ, true_and, iff_true]
        tauto
      have hRc : R0.card + R1.card + R2.card + R3.card = m := by
        have hc := congrArg Finset.card hR
        simp [Finset.card_union_of_disjoint,
          d01, d02, d03, d12, d13, d23] at hc
        simpa [Nat.add_assoc] using hc
  6. A = R₂ ∪ R₃ and B = R₁ ∪ R₃, so |A| = |R₂| + |R₃| and |B| = |R₁| + |R₃|.

    By definition of the regions, A decomposes into the disjoint union of A \ B (R₂) and A ∩ B (R₃), while B decomposes into Aᶜ ∩ B (R₁) and A ∩ B (R₃). Their cardinalities are therefore the sums of the respective region sizes by Finset.card_union_of_disjoint.

    lines 76–86

    uses Finset.card_union_of_disjoint

      have hAR : A = R2 ∪ R3 := by
        ext t
        simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union]
        tauto
      have hBR : B = R1 ∪ R3 := by
        ext t
        simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ,
          Finset.mem_union, true_and]
        tauto
      have hAc' : A.card = R2.card + R3.card := by rw [hAR, Finset.card_union_of_disjoint d23]
      have hBc' : B.card = R1.card + R3.card := by rw [hBR, Finset.card_union_of_disjoint d13]
  7. S ∩ A = Y ∪ Z with cardinality y + z, and S ∩ B = X ∪ Z with cardinality x + z.

    Since W ⊆ R₀ and X ⊆ R₁ are disjoint from A, intersecting S = W ∪ X ∪ Y ∪ Z with A leaves only Y ∪ Z. Disjointness of Y and Z gives |S ∩ A| = y + z. Symmetrically, intersecting S with B leaves X ∪ Z, which has cardinality x + z.

    lines 87–110

    uses Finset.card_union_of_disjoint

      have hSA : S ∩ A = Y ∪ Z := by
        ext t
        have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht
        have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht
        have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht
        have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hw' hx' hy' hz'
        simp only [S, Finset.mem_inter, Finset.mem_union]
        tauto
      have hSB : S ∩ B = X ∪ Z := by
        ext t
        have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht
        have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht
        have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht
        have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hw' hx' hy' hz'
        simp only [S, Finset.mem_inter, Finset.mem_union]
        tauto
      have hSAc : (S ∩ A).card = y + z := by
        rw [hSA, Finset.card_union_of_disjoint dYZ, hYc, hZc]
      have hSBc : (S ∩ B).card = x + z := by
        rw [hSB, Finset.card_union_of_disjoint dXZ, hXc, hZc]
  8. The subset S witnesses the theorem, satisfying all six required balance inequalities.

    We provide S as the witness and verify each of the six goals. The bounds for |S|, |S ∩ A|, and |S ∩ B| match the inequalities htot, hA, and hB directly. For the complement sets, the cardinalities are rewritten using Finset.card_sdiff, Finset.card_univ, Finset.inter_univ, and Fintype.card_fin, and the bounds follow from the complement bounds of the four-type balance lemma via linear arithmetic.

    lines 111–120

    uses Finset.card_sdiff, Finset.card_univ, Finset.inter_univ, Fintype.card_fin

      refine ⟨S, ?_, ?_, ?_, ?_, ?_, ?_⟩
      · rw [hSc, ← hRc]; exact htot
      · rw [Finset.card_sdiff, Finset.card_univ, Finset.inter_univ, Fintype.card_fin, hSc, ← hRc]
        omega
      · rw [hSAc, hAc']; exact hA
      · rw [Finset.card_sdiff, hSAc, hAc']
        omega
      · rw [hSBc, hBc']; exact hB
      · rw [Finset.card_sdiff, hSBc, hBc']
        omega
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element belonging to the first belongs to the second.
four_type_simultaneous_balance_counts
Given four natural numbers a, b, c, d, there exist natural numbers w ≤ a, x ≤ b, y ≤ c, z ≤ d such that the total sum w + x + y + z and the partial sums y + z and x + z, as well as their complements, are each bounded above by ⌊(N + 1)/2⌋ for their respective totals N.
Finset.exists_subset_card_eq
If n is at most the cardinality of a finite set s, then s contains a subset of cardinality n.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.add_assoc
Addition of natural numbers is associative.
congrArg
Applying a function to equal arguments yields equal results.
Finset.card_sdiff
The cardinality of the set difference t \ s equals the cardinality of t minus the cardinality of s ∩ t.
Finset.card_univ
The cardinality of the universal finset equals the cardinality of the underlying finite type.
Finset.inter_univ
Intersecting a set with the universal set gives the set itself.
Fintype.card_fin
The standard finite type Fin n has cardinality n.

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 two_finite_subsets_simultaneously_balanced    (m : ℕ) (A B : Finset (Fin m)) :    ∃ S : Finset (Fin m),      S.card ≤ (m + 1) / 2 ∧      (Finset.univ \ S).card ≤ (m + 1) / 2 ∧      (S ∩ A).card ≤ (A.card + 1) / 2 ∧      (A \ S).card ≤ (A.card + 1) / 2 ∧      (S ∩ B).card ≤ (B.card + 1) / 2 ∧      (B \ S).card ≤ (B.card + 1) / 2 := by  classical  let R0 : Finset (Fin m) := (Finset.univ \ A) \ B  let R1 : Finset (Fin m) := (Finset.univ \ A) ∩ B  let R2 : Finset (Fin m) := A \ B  let R3 : Finset (Fin m) := A ∩ B  have d01 : Disjoint R0 R1 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R1, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d02 : Disjoint R0 R2 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R2, Finset.mem_sdiff,      Finset.mem_univ, true_and] at hi hj    tauto  have d03 : Disjoint R0 R3 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d12 : Disjoint R1 R2 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R1, R2, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d13 : Disjoint R1 R3 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d23 : Disjoint R2 R3 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter] at hi hj    tauto  obtain ⟨w, x, y, z, hw, hx, hy, hz, htot, htotc, hB, hBc, hA, hAc⟩ :=    four_type_simultaneous_balance_counts R0.card R1.card R2.card R3.card  obtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hw  obtain ⟨X, hX, hXc⟩ := Finset.exists_subset_card_eq hx  obtain ⟨Y, hY, hYc⟩ := Finset.exists_subset_card_eq hy  obtain ⟨Z, hZ, hZc⟩ := Finset.exists_subset_card_eq hz  have dWX : Disjoint W X := d01.mono hW hX  have dWY : Disjoint W Y := d02.mono hW hY  have dWZ : Disjoint W Z := d03.mono hW hZ  have dXY : Disjoint X Y := d12.mono hX hY  have dXZ : Disjoint X Z := d13.mono hX hZ  have dYZ : Disjoint Y Z := d23.mono hY hZ  let S := W ∪ X ∪ Y ∪ Z  have hSc : S.card = w + x + y + z := by    simp [S, Finset.card_union_of_disjoint,      dWX, dWY, dWZ, dXY, dXZ, dYZ, hWc, hXc, hYc, hZc, Nat.add_assoc]  have hR : R0 ∪ R1 ∪ R2 ∪ R3 = Finset.univ := by    ext t    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_union, Finset.mem_univ, true_and, iff_true]    tauto  have hRc : R0.card + R1.card + R2.card + R3.card = m := by    have hc := congrArg Finset.card hR    simp [Finset.card_union_of_disjoint,      d01, d02, d03, d12, d13, d23] at hc    simpa [Nat.add_assoc] using hc  have hAR : A = R2 ∪ R3 := by    ext t    simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union]    tauto  have hBR : B = R1 ∪ R3 := by    ext t    simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ,      Finset.mem_union, true_and]    tauto  have hAc' : A.card = R2.card + R3.card := by rw [hAR, Finset.card_union_of_disjoint d23]  have hBc' : B.card = R1.card + R3.card := by rw [hBR, Finset.card_union_of_disjoint d13]  have hSA : S ∩ A = Y ∪ Z := by    ext t    have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht    have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht    have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht    have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hw' hx' hy' hz'    simp only [S, Finset.mem_inter, Finset.mem_union]    tauto  have hSB : S ∩ B = X ∪ Z := by    ext t    have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht    have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht    have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht    have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hw' hx' hy' hz'    simp only [S, Finset.mem_inter, Finset.mem_union]    tauto  have hSAc : (S ∩ A).card = y + z := by    rw [hSA, Finset.card_union_of_disjoint dYZ, hYc, hZc]  have hSBc : (S ∩ B).card = x + z := by    rw [hSB, Finset.card_union_of_disjoint dXZ, hXc, hZc]  refine ⟨S, ?_, ?_, ?_, ?_, ?_, ?_⟩  · rw [hSc, ← hRc]; exact htot  · rw [Finset.card_sdiff, Finset.card_univ, Finset.inter_univ, Fintype.card_fin, hSc, ← hRc]    omega  · rw [hSAc, hAc']; exact hA  · rw [Finset.card_sdiff, hSAc, hAc']    omega  · rw [hSBc, hBc']; exact hB  · rw [Finset.card_sdiff, hSBc, hBc']    omega
See it in the graphDiscuss this resultChallenge it