finite_rook_four_sparse_pattern
Let 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 row or column, then some column contains all four rows; outside that column there are either no cells, or exactly three cells sharing a row or sharing a column.
Statement
theorem finite_rook_four_sparse_pattern {C : Type*} [DecidableEq C] (B : Finset (Fin 4 × C)) (hrows : ∀ r : Fin 4, ∃ c : C, (r,c) ∈ B) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, (∀ r : Fin 4, (r,c) ∈ B) ∧ (let E := B.filter fun p => p.2 ≠ c; E.card = 0 ∨ (E.card = 3 ∧ ((∃ r : Fin 4, ∀ p ∈ E, p.1 = r) ∨ (∃ d : C, ∀ p ∈ E, p.2 = d))))
- Source
- Rook-graph reduction for the 55-point colored fiber case of OP-1027, supported by experiment 27569.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finite_rook_sparse_full_columnLet 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…
The proof, explained
By the companion theorem `finite_rook_sparse_full_column`, the conditions that |B| ≤ 7 < 2 · 4 and every cell has at least 3 rook-neighbors imply that some column c of B is entirely full (contains cells in all 4 rows). The set E of cells outside column c therefore has size at most 7 - 4 = 3. Each cell in E can have at most one rook-neighbor in column c (sharing its row), so it must have at least 3 - 1 = 2 rook-neighbors within E. If E is non-empty, this degree condition forces |E| ≥ 3, whence |E| = 3 and all three cells must be pairwise rook-aligned. Finally, an auxiliary lemma shows that any three pairwise rook-aligned cells in a grid must either all lie in the same row or all lie in the same column.
Any three pairwise distinct, pairwise rook-aligned cells in Fin 4 × C all share a common row or all share a common column.
We prove the auxiliary lemma `finite_rook_four_sparse_pattern_three_cells`. Let p, q, r be pairwise distinct cells such that each pair shares a row or a column. We case-split on whether p and q share a row (p.1 = q.1): if they do, and r also shares this row, all three share row p.1; if r does not share this row, then p and r must share a column (p.2 = r.2), and since q and r cannot share a row without contradicting p.1 ≠ r.1, q and r share a column (q.2 = r.2), so all three share column p.2. If instead p and q do not share a row, they must share a column (p.2 = q.2); then either r also shares this column, so all three share column p.2, or p and r share a row, in which case q and r can neither share a row nor a column, giving a contradiction in both branches. Hence, the three cells either all share a row or all share a column.
private lemma finite_rook_four_sparse_pattern_three_cells {C : Type*} [DecidableEq C] {p q r : Fin 4 × C} (hpq : p ≠ q) (hpr : p ≠ r) (hqr : q ≠ r) (h1 : p.1 = q.1 ∨ p.2 = q.2) (h2 : p.1 = r.1 ∨ p.2 = r.2) (h3 : q.1 = r.1 ∨ q.2 = r.2) : (∃ a, p.1 = a ∧ q.1 = a ∧ r.1 = a) ∨ (∃ b, p.2 = b ∧ q.2 = b ∧ r.2 = b) := by by_cases hp : p.1 = q.1 · by_cases hpr1 : p.1 = r.1 · left; exact ⟨p.1, rfl, hp.symm, hpr1.symm⟩ · have h2' : p.2 = r.2 := by rcases h2 with h | h; exact absurd h hpr1; exact h rcases h3 with h3 | h3 · exact absurd (hp.trans h3) hpr1 · right; exact ⟨p.2, rfl, h3.trans h2'.symm, h2'.symm⟩ · have h1' : p.2 = q.2 := by rcases h1 with h | h; exact absurd h hp; exact h by_cases hpr2 : p.2 = r.2 · right; exact ⟨p.2, rfl, h1'.symm, hpr2.symm⟩ · have h2' : p.1 = r.1 := by rcases h2 with h | h; exact h; exact absurd h hpr2 rcases h3 with h3 | h3 · exact absurd (h2'.trans h3.symm) hp · exact absurd (h1'.trans h3) hpr2
There exists a column c containing cells in all four rows of B.
We apply the theorem `finite_rook_sparse_full_column` with m = 4. Since every row is occupied, |B| ≤ 7 < 2 · 4 = 8, and every cell in B has at least 3 rook-neighbors in B, all conditions of the theorem hold. This produces a column c ∈ C such that (r, c) ∈ B for every row r ∈ Fin 4. We witness c and the fullness hypothesis hc for the main existential statement.
uses
finite_rook_sparse_full_columntheorem finite_rook_four_sparse_pattern {C : Type*} [DecidableEq C] (B : Finset (Fin 4 × C)) (hrows : ∀ r : Fin 4, ∃ c : C, (r,c) ∈ B) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, (∀ r : Fin 4, (r,c) ∈ B) ∧ (let E := B.filter fun p => p.2 ≠ c; E.card = 0 ∨ (E.card = 3 ∧ ((∃ r : Fin 4, ∀ p ∈ E, p.1 = r) ∨ (∃ d : C, ∀ p ∈ E, p.2 = d)))) := by obtain ⟨c, hc⟩ := finite_rook_sparse_full_column 4 B hrows (by omega) hneighbors refine ⟨c, hc, ?_⟩ dsimp only
The set E of cells in B outside column c has cardinality at most 3.
Let S = {(r, c) | r ∈ Fin 4} be the cells in column c. Because the row coordinate is injective, |S| = |Fin 4| = 4 by `Finset.card_image_of_injective` and `Finset.card_univ`. Since column c is full, S ⊆ B. The set E = {p ∈ B | p.2 ≠ c} consists of all cells of B outside column c, so E ⊆ B \ S. By `Finset.card_sdiff` and `Finset.inter_eq_left.mpr`, |B \ S| = |B| - |S| ≤ 7 - 4 = 3. Thus |E| ≤ 3 by `Finset.card_le_card`.
uses
Finset.card_image_of_injective,Finset.card_univ,Finset.card_le_card,Finset.card_sdiff,Finset.inter_eq_left.mprset E := B.filter (fun p => p.2 ≠ c) with hE set S : Finset (Fin 4 × C) := Finset.univ.image (fun r : Fin 4 => (r, c)) with hS have hScard : S.card = 4 := by rw [hS, Finset.card_image_of_injective _ (fun a b h => congrArg Prod.fst h), Finset.card_univ] simp have hSsub : S ⊆ B := by intro x hx rw [hS] at hx simp only [Finset.mem_image, Finset.mem_univ, true_and] at hx obtain ⟨r, rfl⟩ := hx exact hc r have hEsub : E ⊆ B \ S := by intro p hp rw [hE] at hp simp only [Finset.mem_filter] at hp refine Finset.mem_sdiff.mpr ⟨hp.1, ?_⟩ intro hpS rw [hS] at hpS simp only [Finset.mem_image, Finset.mem_univ, true_and] at hpS obtain ⟨r, hr⟩ := hpS have : p.2 = c := by rw [← hr] exact hp.2 this have hEcard : E.card ≤ 3 := by have h1 : E.card ≤ (B \ S).card := Finset.card_le_card hEsub rw [Finset.card_sdiff] at h1 have hinter : S ∩ B = S := Finset.inter_eq_left.mpr hSsub rw [hinter, hScard] at h1 omega
Every cell in E has at least 2 rook-neighbors in E.
Let p ∈ E. Any rook-neighbor q ∈ B of p either has column coordinate c or does not. If q.2 = c, then since p.2 ≠ c, q cannot share its column with p; hence q must share its row with p (q.1 = p.1), which uniquely determines q as (p.1, c). If q.2 ≠ c, then q ∈ E, so q is a rook-neighbor of p within E. Thus the rook-neighbors of p in B are contained in {(p.1, c)} ∪ {q ∈ E | q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)}. Since p has at least 3 rook-neighbors in B, and inserting (p.1, c) increases the set size by at most 1 (by `Finset.card_insert_le`), p must have at least 3 - 1 = 2 rook-neighbors in E.
uses
Finset.card_le_card,Finset.card_insert_lehave hsub : ∀ p ∈ E, (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) ⊆ insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) := by intro p hpE q hq rw [Finset.mem_filter] at hq obtain ⟨hqB, hqne, hqrc⟩ := hq obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE) by_cases hqc : q.2 = c · have hqeq : q = (p.1, c) := by refine Prod.ext ?_ hqc rcases hqrc with h | h · exact h · exact absurd (h.symm.trans hqc) hpc rw [Finset.mem_insert] exact Or.inl hqeq · rw [Finset.mem_insert] exact Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨hqB, hqc⟩, hqne, hqrc⟩) have hN : ∀ p ∈ E, 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := by intro p hpE obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE) have h1 : 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hneighbors p hpB have h2 : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2))).card := Finset.card_le_card (hsub p hpE) have h3 := Finset.card_insert_le (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) omega
Either |E| = 0, or |E| = 3.
The rook-neighbors of any cell a in E form a subset of E \ {a}. By `Nat.eq_zero_or_pos`, either |E| = 0, which immediately establishes the first disjunct of the theorem, or |E| > 0. If |E| > 0, by `Finset.card_pos.mp` there exists some cell p ∈ E. From the previous step, p has at least 2 rook-neighbors in E, all lying in E \ {p}. By `Finset.card_erase_of_mem`, |E \ {p}| = |E| - 1, so 2 ≤ |E| - 1 by `Finset.card_le_card`, which implies |E| ≥ 3. Together with |E| ≤ 3, this forces |E| = 3.
uses
Nat.eq_zero_or_pos,Finset.card_pos.mp,Finset.card_erase_of_mem,Finset.card_le_cardhave hsub2 : ∀ a, (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) ⊆ E.erase a := by intro a q hq rw [Finset.mem_filter] at hq rw [Finset.mem_erase] exact ⟨hq.2.1, hq.1⟩ rcases Nat.eq_zero_or_pos E.card with h0 | hpos · exact Or.inl h0 · obtain ⟨p, hpE⟩ := Finset.card_pos.mp hpos have hNp : 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hN p hpE have hle : (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (E.erase p).card := Finset.card_le_card (hsub2 p) have herase : (E.erase p).card = E.card - 1 := Finset.card_erase_of_mem hpE have hE3 : E.card = 3 := by omega refine Or.inr ⟨hE3, ?_⟩
When |E| = 3, write E = {x, y, z}; then x, y, z are pairwise distinct and pairwise rook-aligned.
Since |E| = 3, by `Finset.card_eq_three.mp` we can write E = {x, y, z} with x, y, z pairwise distinct. For each cell a ∈ E, its rook-neighbors in E are a subset of E \ {a}. Since a has at least 2 rook-neighbors in E and |E \ {a}| = 3 - 1 = 2 by `Finset.card_erase_of_mem`, the subset has the same cardinality as E \ {a}. By `Finset.eq_of_subset_of_card_le`, the rook-neighbors of a in E are all of E \ {a}. Thus every other cell b ∈ E (b ≠ a) is a rook-neighbor of a, meaning a and b share a row or share a column.
uses
Finset.card_eq_three.mp,Finset.card_erase_of_mem,Finset.eq_of_subset_of_card_leobtain ⟨x, y, z, hxy, hxz, hyz, hExyz⟩ := Finset.card_eq_three.mp hE3 have hxE : x ∈ E := by rw [hExyz]; simp have hyE : y ∈ E := by rw [hExyz]; simp have hzE : z ∈ E := by rw [hExyz]; simp have hpair : ∀ a ∈ E, ∀ b ∈ E, a ≠ b → (a.1 = b.1 ∨ a.2 = b.2) := by intro a haE b hbE hab have hNa : 2 ≤ (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)).card := hN a haE have heq : (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) = E.erase a := by apply Finset.eq_of_subset_of_card_le (hsub2 a) rw [Finset.card_erase_of_mem haE] omega have hb : b ∈ E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2) := by rw [heq] exact Finset.mem_erase.mpr ⟨Ne.symm hab, hbE⟩ rcases (Finset.mem_filter.mp hb).2.2 with h | h · exact Or.inl h.symm · exact Or.inr h.symm
The three cells in E all share a row or all share a column.
We invoke the helper lemma `finite_rook_four_sparse_pattern_three_cells` on the three pairwise distinct and pairwise rook-aligned cells x, y, z ∈ E. The lemma asserts that they either all share a common row coordinate a, or all share a common column coordinate b. Because E = {x, y, z}, every element of E is x, y, or z. In the first case, every cell in E has row coordinate a; in the second case, every cell in E has column coordinate b. This completes the second disjunct.
uses
finite_rook_four_sparse_pattern_three_cellshave hcomb := finite_rook_four_sparse_pattern_three_cells hxy hxz hyz (hpair x hxE y hyE hxy) (hpair x hxE z hzE hxz) (hpair y hyE z hzE hyz) rcases hcomb with ⟨a, hxa, hya, hza⟩ | ⟨b, hxb, hyb, hzb⟩ · left refine ⟨a, ?_⟩ intro q hqE rw [hExyz] at hqE simp only [Finset.mem_insert, Finset.mem_singleton] at hqE rcases hqE with rfl | rfl | rfl · exact hxa · exact hya · exact hza · right refine ⟨b, ?_⟩ intro q hqE rw [hExyz] at hqE simp only [Finset.mem_insert, Finset.mem_singleton] at hqE rcases hqE with rfl | rfl | rfl · exact hxb · exact hyb · exact hzb
finite_rook_sparse_full_column- In an m-row grid, if every row is occupied, |B| < 2m, and every cell has at least m - 1 rook-neighbors in B, then some column of B contains cells in all m rows.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the original set.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` of a finite type is the cardinality of that type.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_sdiff- The cardinality of the set difference t \ s equals |t| - |s ∩ t|.
Finset.inter_eq_left.mpr- If s ⊆ t, then s ∩ t = s.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1: |insert a s| ≤ |s| + 1.
Nat.eq_zero_or_pos- Every natural number is either 0 or strictly positive.
Finset.card_pos.mp- If a finite set has strictly positive cardinality, it is non-empty.
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases its cardinality by 1: |s \ {a}| = |s| - 1.
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements {x, y, z}.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s|, then s = t.
finite_rook_four_sparse_pattern_three_cells- If three pairwise distinct cells in a 4-row grid pairwise share a row or share a column, then all three share a row or all three share a column.
- The proof takes the existence of the full column from `finite_rook_sparse_full_column`, a companion theorem in the same development.
- Linear arithmetic bounds on set cardinalities are discharged by the `omega` tactic once the set-theoretic inclusions are established.
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.
private lemma finite_rook_four_sparse_pattern_three_cells {C : Type*} [DecidableEq C] {p q r : Fin 4 × C} (hpq : p ≠ q) (hpr : p ≠ r) (hqr : q ≠ r) (h1 : p.1 = q.1 ∨ p.2 = q.2) (h2 : p.1 = r.1 ∨ p.2 = r.2) (h3 : q.1 = r.1 ∨ q.2 = r.2) : (∃ a, p.1 = a ∧ q.1 = a ∧ r.1 = a) ∨ (∃ b, p.2 = b ∧ q.2 = b ∧ r.2 = b) := by by_cases hp : p.1 = q.1 · by_cases hpr1 : p.1 = r.1 · left; exact ⟨p.1, rfl, hp.symm, hpr1.symm⟩ · have h2' : p.2 = r.2 := by rcases h2 with h | h; exact absurd h hpr1; exact h rcases h3 with h3 | h3 · exact absurd (hp.trans h3) hpr1 · right; exact ⟨p.2, rfl, h3.trans h2'.symm, h2'.symm⟩ · have h1' : p.2 = q.2 := by rcases h1 with h | h; exact absurd h hp; exact h by_cases hpr2 : p.2 = r.2 · right; exact ⟨p.2, rfl, h1'.symm, hpr2.symm⟩ · have h2' : p.1 = r.1 := by rcases h2 with h | h; exact h; exact absurd h hpr2 rcases h3 with h3 | h3 · exact absurd (h2'.trans h3.symm) hp · exact absurd (h1'.trans h3) hpr2theorem finite_rook_four_sparse_pattern {C : Type*} [DecidableEq C] (B : Finset (Fin 4 × C)) (hrows : ∀ r : Fin 4, ∃ c : C, (r,c) ∈ B) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card) : ∃ c : C, (∀ r : Fin 4, (r,c) ∈ B) ∧ (let E := B.filter fun p => p.2 ≠ c; E.card = 0 ∨ (E.card = 3 ∧ ((∃ r : Fin 4, ∀ p ∈ E, p.1 = r) ∨ (∃ d : C, ∀ p ∈ E, p.2 = d)))) := by obtain ⟨c, hc⟩ := finite_rook_sparse_full_column 4 B hrows (by omega) hneighbors refine ⟨c, hc, ?_⟩ dsimp only set E := B.filter (fun p => p.2 ≠ c) with hE set S : Finset (Fin 4 × C) := Finset.univ.image (fun r : Fin 4 => (r, c)) with hS have hScard : S.card = 4 := by rw [hS, Finset.card_image_of_injective _ (fun a b h => congrArg Prod.fst h), Finset.card_univ] simp have hSsub : S ⊆ B := by intro x hx rw [hS] at hx simp only [Finset.mem_image, Finset.mem_univ, true_and] at hx obtain ⟨r, rfl⟩ := hx exact hc r have hEsub : E ⊆ B \ S := by intro p hp rw [hE] at hp simp only [Finset.mem_filter] at hp refine Finset.mem_sdiff.mpr ⟨hp.1, ?_⟩ intro hpS rw [hS] at hpS simp only [Finset.mem_image, Finset.mem_univ, true_and] at hpS obtain ⟨r, hr⟩ := hpS have : p.2 = c := by rw [← hr] exact hp.2 this have hEcard : E.card ≤ 3 := by have h1 : E.card ≤ (B \ S).card := Finset.card_le_card hEsub rw [Finset.card_sdiff] at h1 have hinter : S ∩ B = S := Finset.inter_eq_left.mpr hSsub rw [hinter, hScard] at h1 omega have hsub : ∀ p ∈ E, (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) ⊆ insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) := by intro p hpE q hq rw [Finset.mem_filter] at hq obtain ⟨hqB, hqne, hqrc⟩ := hq obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE) by_cases hqc : q.2 = c · have hqeq : q = (p.1, c) := by refine Prod.ext ?_ hqc rcases hqrc with h | h · exact h · exact absurd (h.symm.trans hqc) hpc rw [Finset.mem_insert] exact Or.inl hqeq · rw [Finset.mem_insert] exact Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨hqB, hqc⟩, hqne, hqrc⟩) have hN : ∀ p ∈ E, 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := by intro p hpE obtain ⟨hpB, hpc⟩ := Finset.mem_filter.mp (hE ▸ hpE) have h1 : 3 ≤ (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hneighbors p hpB have h2 : (B.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (insert (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2))).card := Finset.card_le_card (hsub p hpE) have h3 := Finset.card_insert_le (p.1, c) (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)) omega have hsub2 : ∀ a, (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) ⊆ E.erase a := by intro a q hq rw [Finset.mem_filter] at hq rw [Finset.mem_erase] exact ⟨hq.2.1, hq.1⟩ rcases Nat.eq_zero_or_pos E.card with h0 | hpos · exact Or.inl h0 · obtain ⟨p, hpE⟩ := Finset.card_pos.mp hpos have hNp : 2 ≤ (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card := hN p hpE have hle : (E.filter fun q => q ≠ p ∧ (q.1 = p.1 ∨ q.2 = p.2)).card ≤ (E.erase p).card := Finset.card_le_card (hsub2 p) have herase : (E.erase p).card = E.card - 1 := Finset.card_erase_of_mem hpE have hE3 : E.card = 3 := by omega refine Or.inr ⟨hE3, ?_⟩ obtain ⟨x, y, z, hxy, hxz, hyz, hExyz⟩ := Finset.card_eq_three.mp hE3 have hxE : x ∈ E := by rw [hExyz]; simp have hyE : y ∈ E := by rw [hExyz]; simp have hzE : z ∈ E := by rw [hExyz]; simp have hpair : ∀ a ∈ E, ∀ b ∈ E, a ≠ b → (a.1 = b.1 ∨ a.2 = b.2) := by intro a haE b hbE hab have hNa : 2 ≤ (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)).card := hN a haE have heq : (E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2)) = E.erase a := by apply Finset.eq_of_subset_of_card_le (hsub2 a) rw [Finset.card_erase_of_mem haE] omega have hb : b ∈ E.filter fun q => q ≠ a ∧ (q.1 = a.1 ∨ q.2 = a.2) := by rw [heq] exact Finset.mem_erase.mpr ⟨Ne.symm hab, hbE⟩ rcases (Finset.mem_filter.mp hb).2.2 with h | h · exact Or.inl h.symm · exact Or.inr h.symm have hcomb := finite_rook_four_sparse_pattern_three_cells hxy hxz hyz (hpair x hxE y hyE hxy) (hpair x hxE z hzE hxz) (hpair y hyE z hzE hyz) rcases hcomb with ⟨a, hxa, hya, hza⟩ | ⟨b, hxb, hyb, hzb⟩ · left refine ⟨a, ?_⟩ intro q hqE rw [hExyz] at hqE simp only [Finset.mem_insert, Finset.mem_singleton] at hqE rcases hqE with rfl | rfl | rfl · exact hxa · exact hya · exact hza · right refine ⟨b, ?_⟩ intro q hqE rw [hExyz] at hqE simp only [Finset.mem_insert, Finset.mem_singleton] at hqE rcases hqE with rfl | rfl | rfl · exact hxb · exact hyb · exact hzb