finite_rook_sparse_full_column
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.
The number of rows $m$ is strictly positive.
If $m = 0$, the hypothesis $|B| < 2m = 0$ is impossible since a cardinality cannot be negative.
uses
Nat.eq_zero_or_posrcases Nat.eq_zero_or_pos m with hm | hm · exfalso; omega
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$.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,Finset.mem_filter,Finset.card_pos.mprlet 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
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$.
uses
Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mulhave 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
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$.
uses
Finset.mem_filter,Finset.card_le_one.mp,le_of_eqobtain ⟨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
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\}$.
uses
Finset.mem_filter,Finset.mem_eraselet 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⟩
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$.
uses
Nat.sub_le_iff_le_add,Finset.card_le_card,Finset.card_erase_add_onehave 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
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$.
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_antisymmhave 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
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$.
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.extrefine ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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