AFTD Auto-Formalizing Theoretical Domains

good_slopes_grid_row_le_three

theoremverified

If a finite collection has at most seven cells and every nonempty column has at least two cells, every row has at most three cells.

Statement

theorem good_slopes_grid_row_le_three {R C : Type*} [DecidableEq R] [DecidableEq C]
    (B : Finset (R × C)) (hcard : B.card ≤ 7)
    (hcols : ∀ c : C, (B.filter fun p => p.2 = c).card = 0 ∨
      2 ≤ (B.filter fun p => p.2 = c).card) (r : R) :
    (B.filter fun p => p.1 = r).card ≤ 3
Source
Counting step in the 105-point good-slope fiber reduction for OP-1027.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Lean source view module on GitHub

theorem good_slopes_grid_row_le_three {R C : Type*} [DecidableEq R] [DecidableEq C]
    (B : Finset (R × C)) (hcard : B.card ≤ 7)
    (hcols : ∀ c : C, (B.filter fun p => p.2 = c).card = 0 ∨
      2 ≤ (B.filter fun p => p.2 = c).card) (r : R) :
    (B.filter fun p => p.1 = r).card ≤ 3 := by
  classical
  let row := B.filter fun p => p.1 = r
  let cols := row.image Prod.snd
  have hinj : Set.InjOn (fun p : R × C => p.2) row := by
    intro p hp q hq hpq
    apply Prod.ext ?_ hpq
    exact (Finset.mem_filter.mp hp).2.trans (Finset.mem_filter.mp hq).2.symm
  have hcols_card : cols.card = row.card := Finset.card_image_of_injOn hinj
  have hsubset : cols ⊆ B.image Prod.snd :=
    Finset.image_subset_image (Finset.filter_subset _ _)
  have hlower : ∀ c ∈ cols, 2 ≤ (B.filter fun p => p.2 = c).card := by
    intro c hc
    obtain ⟨p,hp,hpc⟩ := Finset.mem_image.mp hc
    have hpB : p ∈ B := (Finset.mem_filter.mp hp).1
    have hpos : 0 < (B.filter fun p => p.2 = c).card :=
      Finset.card_pos.mpr ⟨p,Finset.mem_filter.mpr ⟨hpB,hpc⟩⟩
    rcases hcols c with h | h
    · omega
    · exact h
  have htwice : 2 * row.card ≤ B.card := by
    rw [Finset.card_eq_sum_card_image Prod.snd B]
    calc
      2 * row.card = ∑ c ∈ cols, 2 := by simp [hcols_card, Nat.mul_comm]
      _ ≤ ∑ c ∈ cols, (B.filter fun p => p.2 = c).card := Finset.sum_le_sum hlower
      _ ≤ ∑ c ∈ B.image Prod.snd, (B.filter fun p => p.2 = c).card :=
        Finset.sum_le_sum_of_subset hsubset
  change row.card ≤ 3
  omega
See it in the graphDiscuss this resultChallenge it