AFTD Auto-Formalizing Theoretical Domains

finite_rook_sparse_full_column

theoremverified

Let B be a finite set of cells with m possible rows. Suppose every row is occupied, B has fewer than 2m cells, and every selected cell has at least m−1 other selected cells in its row or column. Then some column contains a selected cell in every row.

Statement

theorem finite_rook_sparse_full_column (m : ℕ) {C : Type*} [DecidableEq C] (B : Finset (Fin m × C)) (hrows : ∀ r : Fin m, ∃ c : C, (r,c) ∈ B) (hsize : B.card < 2*m) (hneighbors : ∀ p ∈ B, m-1 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, ∀ r : Fin m, (r,c) ∈ B
Source
Elementary rook-graph pigeonhole reduction for OP-1027; experiment 27569 checks the four-by-ten case.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • finite_rook_four_sparse_patternLet B be a set of at most seven cells in four rows, with every row occupied. If every cell of B has at least three other cells of B in its…

The proof, explained

By partitioning the cells of $B$ across the $m$ rows and using the fact that every row has at least one cell while the total number of cells is strictly less than $2m$, the pigeonhole principle implies that at least one row contains exactly one cell $p$. Because $p$ is the only cell in its row, all of its at least $m - 1$ neighbors must lie in its column, meaning this column contains at least $m$ cells. Since the cells in a single column must all lie in distinct rows, the column can have at most $m$ cells and thus has size exactly $m$. Therefore, this column contains a selected cell in every row.

  1. The number of rows $m$ is strictly positive.

    If $m = 0$, the hypothesis $|B| < 2m = 0$ is impossible since a cardinality cannot be negative.

    lines 2–3

    uses Nat.eq_zero_or_pos

      rcases Nat.eq_zero_or_pos m with hm | hm
      · exfalso; omega
  2. The total size $|B|$ is the sum of row occupancies, and every row contains at least one cell.

    We define the row count of row $r$ as the number of cells in $B$ in row $r$. Partitioning $B$ by row projection shows $|B| = \sum_{r} \mathrm{rowCount}(r)$, and the hypothesis that every row is occupied implies $\mathrm{rowCount}(r) ≥ 1$ for all $r$.

    lines 4–12

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ, Finset.mem_filter, Finset.card_pos.mpr

      let rowCount : Fin m → ℕ := fun r => (B.filter (fun q => q.1 = r)).card
      have hsum : B.card = ∑ r : Fin m, rowCount r := by
        rw [Finset.card_eq_sum_card_fiberwise (f := fun q : Fin m × C => q.1) (t := Finset.univ) (fun q _ => Finset.mem_univ q.1)]
      have hrow_ge : ∀ r : Fin m, 1 ≤ rowCount r := by
        intro r
        obtain ⟨c, hc⟩ := hrows r
        have hmem : (r, c) ∈ B.filter (fun q => q.1 = r) := by simp [Finset.mem_filter, hc]
        have hpos := Finset.card_pos.mpr ⟨(r, c), hmem⟩
        simpa [rowCount] using hpos
  3. There is some row that contains exactly one cell.

    By contradiction: if no row had count 1, then every row would have at least 2 cells because every row has at least 1. Summing 2 over all $m$ rows gives $2m ≤ \sum_{r} \mathrm{rowCount}(r) = |B|$, which contradicts the hypothesis $|B| < 2m$.

    lines 13–23

    uses Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul

      have hsome : ∃ r : Fin m, rowCount r = 1 := by
        by_contra h
        have h2 : ∀ r : Fin m, 2 ≤ rowCount r := by
          intro r
          have h1 := hrow_ge r
          have hne : rowCount r ≠ 1 := fun hh => h ⟨r, hh⟩
          omega
        have hle : ∑ r : Fin m, 2 ≤ ∑ r : Fin m, rowCount r := Finset.sum_le_sum (fun r _ => h2 r)
        rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hle
        rw [← hsum] at hle
        omega
  4. Let $p = (r_0, c_0) \in B$ be the unique cell in this singleton row; no other cell in $B$ shares row $r_0$.

    We choose a row $r_0$ with row count 1 and a cell $c_0$ such that $p = (r_0, c_0) \in B$. Since row $r_0$ has cardinality 1, any cell $q \in B$ with row coordinate $r_0$ must equal $p$.

    lines 24–36

    uses Finset.mem_filter, Finset.card_le_one.mp, le_of_eq

      obtain ⟨r0, hr0⟩ := hsome
      obtain ⟨c0, hc0⟩ := hrows r0
      set p : Fin m × C := (r0, c0) with hp_def
      have hpB : p ∈ B := hc0
      have huniq : ∀ q ∈ B, q.1 = p.1 → q = p := by
        intro q hqB hqrow
        have hq : q ∈ B.filter (fun q => q.1 = r0) := by
          simp only [Finset.mem_filter]
          exact ⟨hqB, hqrow⟩
        have hp : p ∈ B.filter (fun q => q.1 = r0) := by
          simp only [Finset.mem_filter]
          exact ⟨hpB, rfl⟩
        exact Finset.card_le_one.mp (le_of_eq hr0) q hq p hp
  5. Every neighbor of $p$ in $B$ lies in $p$'s column.

    Let $\mathrm{col}$ be the set of cells in $B$ in column $p.2$. By definition, a neighbor of $p$ is a cell $q \in B \setminus \{p\}$ that shares a row or column with $p$. Since no other cell shares $p$'s row, every neighbor must share $p$'s column, so the neighborhood of $p$ is contained in $\mathrm{col} \setminus \{p\}$.

    lines 37–49

    uses Finset.mem_filter, Finset.mem_erase

      let col := B.filter (fun q => q.2 = p.2)
      have hpcol : p ∈ col := by
        simp [col, Finset.mem_filter, hpB]
      have hN_sub : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) ⊆ col.erase p := by
        intro q hq
        simp only [Finset.mem_filter] at hq
        obtain ⟨hqB, hqp, hrowcol⟩ := hq
        rw [Finset.mem_erase]
        refine ⟨hqp, ?_⟩
        simp only [col, Finset.mem_filter]
        exact ⟨hqB, by rcases hrowcol with h | h
                       · exact absurd (huniq q hqB h) hqp
                       · exact h⟩
  6. The column containing $p$ has cardinality at least $m$.

    By hypothesis, $p$ has at least $m - 1$ neighbors in $B$. Since all of these neighbors belong to $\mathrm{col} \setminus \{p\}$, we have $|\mathrm{col} \setminus \{p\}| ≥ m - 1$. Adding $p \in \mathrm{col}$ back shows $|\mathrm{col}| ≥ m$.

    lines 50–56

    uses Nat.sub_le_iff_le_add, Finset.card_le_card, Finset.card_erase_add_one

      have hcol_lower : m ≤ col.card := by
        have hNcard := hneighbors p hpB
        rw [Nat.sub_le_iff_le_add] at hNcard
        have h1 : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (col.erase p).card :=
          Finset.card_le_card hN_sub
        have h2 : (col.erase p).card + 1 = col.card := Finset.card_erase_add_one hpcol
        omega
  7. The column containing $p$ has cardinality exactly $m$.

    Cells in the same column have identical column coordinates, so the projection to the row coordinate is injective on $\mathrm{col}$. Since there are $m$ possible rows in $\mathrm{Fin}\; m$, $|\mathrm{col}| ≤ m$. Combined with $|\mathrm{col}| ≥ m$, this yields $|\mathrm{col}| = m$.

    lines 57–68

    uses Finset.mem_coe, Finset.mem_filter, Prod.ext, Finset.mem_univ, Finset.card_le_card_of_injOn, Finset.card_univ, Fintype.card_fin, le_antisymm

      have hinj : Set.InjOn (fun q : Fin m × C => q.1) ↑col := by
        intro a ha b hb hab
        rw [Finset.mem_coe] at ha hb
        have ha' : a ∈ B ∧ a.2 = p.2 := by simpa only [col, Finset.mem_filter] using ha
        have hb' : b ∈ B ∧ b.2 = p.2 := by simpa only [col, Finset.mem_filter] using hb
        exact Prod.ext hab (ha'.2.trans hb'.2.symm)
      have hcol_upper : col.card ≤ m := by
        have hmaps : Set.MapsTo (fun q : Fin m × C => q.1) ↑col ↑(Finset.univ : Finset (Fin m)) :=
          fun q _ => Finset.mem_univ q.1
        have hle := Finset.card_le_card_of_injOn (fun q : Fin m × C => q.1) hmaps hinj
        rwa [Finset.card_univ, Fintype.card_fin] at hle
      have hcolcard : col.card = m := le_antisymm hcol_upper hcol_lower
  8. Column $p.2$ contains a cell in every row, completing the proof.

    Because the row projection is injective on $\mathrm{col}$ and $|\mathrm{col}| = m = |\mathrm{Fin}\; m|$, the image of $\mathrm{col}$ under row projection is the entire set of rows. Thus for every row $r$, there exists a cell in $\mathrm{col}$ (hence in $B$ and column $p.2$) with row coordinate $r$.

    lines 69–78

    uses Finset.eq_univ_of_card, Finset.card_image_of_injOn, Fintype.card_fin, Finset.mem_univ, Finset.mem_image.mp, Finset.mem_filter, Prod.ext

      refine ⟨p.2, fun r => ?_⟩
      have himg : col.image (fun q => q.1) = Finset.univ := by
        apply Finset.eq_univ_of_card
        rw [Finset.card_image_of_injOn hinj, hcolcard, Fintype.card_fin]
      have hr : r ∈ col.image (fun q => q.1) := by rw [himg]; exact Finset.mem_univ r
      obtain ⟨q, hqcol, hqrow⟩ := Finset.mem_image.mp hr
      have hqcol' : q ∈ B ∧ q.2 = p.2 := by
        simpa only [col, Finset.mem_filter] using hqcol
      rw [show (r, p.2) = q from Prod.ext hqrow.symm hqcol'.2.symm]
      exact hqcol'.1
Finset.card_image_of_injOn
The image of a finite set under an injective map has the same cardinality as the set.
Finset.card_le_card
If $s ⊆ t$ for finite sets, then $|s| ≤ |t|$.
Finset.card_le_card_of_injOn
If a function maps a finite set injectively into another, the size of the domain is at most the size of the codomain.
Finset.card_le_one.mp
If a finite set has at most one element, any two elements in it are equal.
Finset.card_pos.mpr
A finite set with at least one element has strictly positive cardinality.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of that type.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set equals the sum of the cardinalities of its fibers under a map.
Finset.card_erase_add_one
Removing an element from a finite set decreases its cardinality by 1.
Finset.eq_univ_of_card
A subset of a finite type with the same cardinality as the type is the universal set.
Finset.mem_coe
An element belongs to a finset coerced to a set if and only if it belongs to the finset.
Finset.mem_erase
An element is in $s \setminus \{a\}$ if and only if it is not equal to $a$ and is in $s$.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_image.mp
If an element is in the image of a set under $f$, it equals $f(x)$ for some element $x$ in the set.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.sum_const
Summing a constant over a finite set equals the cardinality of the set times the constant.
Finset.sum_le_sum
If $f(i) ≤ g(i)$ for all $i$ in a finite set, then $\sum_i f(i) ≤ \sum_i g(i)$.
Fintype.card_fin
The finite type $\mathrm{Fin}\; n$ has cardinality $n$.
le_antisymm
If $a ≤ b$ and $b ≤ a$, then $a = b$.
le_of_eq
If $a = b$, then $a ≤ b$.
Nat.eq_zero_or_pos
A natural number is either zero or strictly positive.
Nat.sub_le_iff_le_add
For natural numbers, $a - b ≤ c$ if and only if $a ≤ c + b$.
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.
smul_eq_mul
Scalar multiplication of natural numbers coincides with standard multiplication.

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 finite_rook_sparse_full_column (m : ℕ) {C : Type*} [DecidableEq C] (B : Finset (Fin m × C)) (hrows : ∀ r : Fin m, ∃ c : C, (r,c) ∈ B) (hsize : B.card < 2*m) (hneighbors : ∀ p ∈ B, m-1 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, ∀ r : Fin m, (r,c) ∈ B := by  rcases Nat.eq_zero_or_pos m with hm | hm  · exfalso; omega  let rowCount : Fin m → ℕ := fun r => (B.filter (fun q => q.1 = r)).card  have hsum : B.card = ∑ r : Fin m, rowCount r := by    rw [Finset.card_eq_sum_card_fiberwise (f := fun q : Fin m × C => q.1) (t := Finset.univ) (fun q _ => Finset.mem_univ q.1)]  have hrow_ge : ∀ r : Fin m, 1 ≤ rowCount r := by    intro r    obtain ⟨c, hc⟩ := hrows r    have hmem : (r, c) ∈ B.filter (fun q => q.1 = r) := by simp [Finset.mem_filter, hc]    have hpos := Finset.card_pos.mpr ⟨(r, c), hmem⟩    simpa [rowCount] using hpos  have hsome : ∃ r : Fin m, rowCount r = 1 := by    by_contra h    have h2 : ∀ r : Fin m, 2 ≤ rowCount r := by      intro r      have h1 := hrow_ge r      have hne : rowCount r ≠ 1 := fun hh => h ⟨r, hh⟩      omega    have hle : ∑ r : Fin m, 2 ≤ ∑ r : Fin m, rowCount r := Finset.sum_le_sum (fun r _ => h2 r)    rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hle    rw [← hsum] at hle    omega  obtain ⟨r0, hr0⟩ := hsome  obtain ⟨c0, hc0⟩ := hrows r0  set p : Fin m × C := (r0, c0) with hp_def  have hpB : p ∈ B := hc0  have huniq : ∀ q ∈ B, q.1 = p.1 → q = p := by    intro q hqB hqrow    have hq : q ∈ B.filter (fun q => q.1 = r0) := by      simp only [Finset.mem_filter]      exact ⟨hqB, hqrow⟩    have hp : p ∈ B.filter (fun q => q.1 = r0) := by      simp only [Finset.mem_filter]      exact ⟨hpB, rfl⟩    exact Finset.card_le_one.mp (le_of_eq hr0) q hq p hp  let col := B.filter (fun q => q.2 = p.2)  have hpcol : p ∈ col := by    simp [col, Finset.mem_filter, hpB]  have hN_sub : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) ⊆ col.erase p := by    intro q hq    simp only [Finset.mem_filter] at hq    obtain ⟨hqB, hqp, hrowcol⟩ := hq    rw [Finset.mem_erase]    refine ⟨hqp, ?_⟩    simp only [col, Finset.mem_filter]    exact ⟨hqB, by rcases hrowcol with h | h                   · exact absurd (huniq q hqB h) hqp                   · exact h⟩  have hcol_lower : m ≤ col.card := by    have hNcard := hneighbors p hpB    rw [Nat.sub_le_iff_le_add] at hNcard    have h1 : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (col.erase p).card :=      Finset.card_le_card hN_sub    have h2 : (col.erase p).card + 1 = col.card := Finset.card_erase_add_one hpcol    omega  have hinj : Set.InjOn (fun q : Fin m × C => q.1) ↑col := by    intro a ha b hb hab    rw [Finset.mem_coe] at ha hb    have ha' : a ∈ B ∧ a.2 = p.2 := by simpa only [col, Finset.mem_filter] using ha    have hb' : b ∈ B ∧ b.2 = p.2 := by simpa only [col, Finset.mem_filter] using hb    exact Prod.ext hab (ha'.2.trans hb'.2.symm)  have hcol_upper : col.card ≤ m := by    have hmaps : Set.MapsTo (fun q : Fin m × C => q.1) ↑col ↑(Finset.univ : Finset (Fin m)) :=      fun q _ => Finset.mem_univ q.1    have hle := Finset.card_le_card_of_injOn (fun q : Fin m × C => q.1) hmaps hinj    rwa [Finset.card_univ, Fintype.card_fin] at hle  have hcolcard : col.card = m := le_antisymm hcol_upper hcol_lower  refine ⟨p.2, fun r => ?_⟩  have himg : col.image (fun q => q.1) = Finset.univ := by    apply Finset.eq_univ_of_card    rw [Finset.card_image_of_injOn hinj, hcolcard, Fintype.card_fin]  have hr : r ∈ col.image (fun q => q.1) := by rw [himg]; exact Finset.mem_univ r  obtain ⟨q, hqcol, hqrow⟩ := Finset.mem_image.mp hr  have hqcol' : q ∈ B ∧ q.2 = p.2 := by    simpa only [col, Finset.mem_filter] using hqcol  rw [show (r, p.2) = q from Prod.ext hqrow.symm hqcol'.2.symm]  exact hqcol'.1
See it in the graphDiscuss this resultChallenge it