AFTD Auto-Formalizing Theoretical Domains

finset_three_color_busiest_recolor

theoremverified

Given three colors and a finite set excluding a distinguished point, recolor only that point so that at least one third of the set has its new color.

Statement

theorem finset_three_color_busiest_recolor
    (α : Type) [Fintype α] [DecidableEq α] (col : α → Fin 3) (x : α) (M : Finset α)
    (hx : x ∉ M) :
    ∃ col' : α → Fin 3, (∀ v, v ≠ x → col' v = col v) ∧
      M.card ≤ 3 * (M.filter fun v => col' v = col' x).card
Source
Pigeonhole step in the exceptional-vertex reduction for OP-110.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof uses the pigeonhole principle: partitioning the set M into three color classes according to col, the sum of their sizes equals |M|, so at least one color class S(i) must satisfy |M| ≤ 3 * |S(i)|. Recoloring x with this majority color i while preserving all other colors ensures that the subset of M matching x's new color is precisely S(i) (since x ∉ M). Therefore, at least one third of M shares the new color assigned to x.

  1. Define S(i) for each color i ∈ {0, 1, 2} as the set of elements in M colored i.

    Working classically, we partition the finite set M by color, defining S(i) = {v ∈ M | col(v) = i} for each color i ∈ Fin 3.

    lines 6–7

      classical
      let S : Fin 3 → Finset α := fun i => M.filter fun v => col v = i
  2. The cardinality of M is the sum of the cardinalities of its three color classes: |M| = |S(0)| + |S(1)| + |S(2)|.

    By Finset.card_eq_sum_card_fiberwise, partitioning M along the fibers of the coloring col expresses |M| as the sum of fiber cardinalities over Finset.univ. Applying Fin.sum_univ_three expands this sum over Fin 3 into the three terms |S(0)| + |S(1)| + |S(2)|.

    lines 8–13

    uses Finset.card_eq_sum_card_fiberwise, Fin.sum_univ_three

      have hsum : M.card = (S 0).card+(S 1).card+(S 2).card := by
        have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := M)
          (t := (Finset.univ : Finset (Fin 3))) (by simp)
        simp only [Fin.sum_univ_three] at h
        change M.card = (S 0).card + (S 1).card + (S 2).card at h
        exact h
  3. There is at least one color i ∈ {0, 1, 2} such that |M| ≤ 3 * |S(i)|.

    By contradiction, suppose no such color exists. Then 3 * |S(i)| < |M| for each of i = 0, 1, 2. Summing these three strict inequalities gives 3 * (|S(0)| + |S(1)| + |S(2)|) < 3 * |M|, which contradicts |M| = |S(0)| + |S(1)| + |S(2)|; linear integer arithmetic (omega) derives False from this system.

    lines 14–22

      have hi : ∃ i : Fin 3, M.card ≤ 3 * (S i).card := by
        by_contra hn
        have h0 : 3*(S 0).card < M.card := by
          by_contra h; exact hn ⟨0, by omega⟩
        have h1 : 3*(S 1).card < M.card := by
          by_contra h; exact hn ⟨1, by omega⟩
        have h2 : 3*(S 2).card < M.card := by
          by_contra h; exact hn ⟨2, by omega⟩
        omega
  4. Choose such a majority color i and define a new coloring col' that changes only the color of x to i.

    We unpack the witness i satisfying |M| ≤ 3 * |S(i)| and define col' to map x to i and every other element v to col(v). The goal splits into showing that col' agrees with col away from x, and that |M| ≤ 3 * |{v ∈ M | col'(v) = col'(x)}|.

    lines 23–25

      obtain ⟨i,hi⟩ := hi
      let col' : α → Fin 3 := fun v => if v = x then i else col v
      refine ⟨col', ?_, ?_⟩
  5. For any vertex v ≠ x, the new coloring satisfies col'(v) = col(v).

    Since v ≠ x, the conditional definition of col'(v) immediately simplifies to col(v).

    lines 26–27

      · intro v hv
        simp [col',hv]
  6. The elements in M that share x's new color under col' are precisely the elements of S(i).

    We verify the set equality by extensionality. For any v ∈ M, the hypothesis x ∉ M ensures v ≠ x, so col'(v) = col(v); since col'(x) = i, the condition col'(v) = col'(x) is equivalent to col(v) = i, placing v in S(i). If v ∉ M, it belongs to neither set.

    lines 28–33

      · have heq : (M.filter fun v => col' v = col' x) = S i := by
          ext v
          by_cases hv : v ∈ M
          · have hvx : v ≠ x := by intro h; subst v; exact hx hv
            simp [S,col',hv,hvx]
          · simp [S,hv]
  7. At least one third of the elements in M have the color col'(x).

    Rewriting the filtered set {v ∈ M | col'(v) = col'(x)} as S(i) reduces the goal to |M| ≤ 3 * |S(i)|, which holds by our choice of i.

    lines 34–35

        rw [heq]
        exact hi
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set s mapped by f into t is the sum over all elements b of t of the cardinalities of the fibers {a ∈ s | f a = b}.
Fin.sum_univ_three
The sum of a function f over all elements of Fin 3 equals f(0) + f(1) + f(2).

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 finset_three_color_busiest_recolor    (α : Type) [Fintype α] [DecidableEq α] (col : α → Fin 3) (x : α) (M : Finset α)    (hx : x ∉ M) :    ∃ col' : α → Fin 3, (∀ v, v ≠ x → col' v = col v) ∧      M.card ≤ 3 * (M.filter fun v => col' v = col' x).card := by  classical  let S : Fin 3 → Finset α := fun i => M.filter fun v => col v = i  have hsum : M.card = (S 0).card+(S 1).card+(S 2).card := by    have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := M)      (t := (Finset.univ : Finset (Fin 3))) (by simp)    simp only [Fin.sum_univ_three] at h    change M.card = (S 0).card + (S 1).card + (S 2).card at h    exact h  have hi : ∃ i : Fin 3, M.card ≤ 3 * (S i).card := by    by_contra hn    have h0 : 3*(S 0).card < M.card := by      by_contra h; exact hn ⟨0, by omega⟩    have h1 : 3*(S 1).card < M.card := by      by_contra h; exact hn ⟨1, by omega⟩    have h2 : 3*(S 2).card < M.card := by      by_contra h; exact hn ⟨2, by omega⟩    omega  obtain ⟨i,hi⟩ := hi  let col' : α → Fin 3 := fun v => if v = x then i else col v  refine ⟨col', ?_, ?_⟩  · intro v hv    simp [col',hv]  · have heq : (M.filter fun v => col' v = col' x) = S i := by      ext v      by_cases hv : v ∈ M      · have hvx : v ≠ x := by intro h; subst v; exact hx hv        simp [S,col',hv,hvx]      · simp [S,hv]    rw [heq]    exact hi
See it in the graphDiscuss this resultChallenge it