cyclic_necklace_transitions_ge_two_mul_sub_one
On a cyclic necklace of r red beads followed by b blue beads with r, b ≥ k ≥ 2, any allocation to k agents in which every agent receives at least one red bead and at least one blue bead has at least 2(k - 1) index transitions where adjacent beads are assigned to different agents.
Statement
theorem cyclic_necklace_transitions_ge_two_mul_sub_one (m k r b : ℕ) [NeZero m] (hm : m = r + b) (hk : 2 ≤ k) (hr : k ≤ r) (hb : k ≤ b) (α : ZMod m → Fin k) (hred : ∀ j : Fin k, ∃ (i : ℕ) (hi : i < r), α i = j) (hblue : ∀ j : Fin k, ∃ (i : ℕ) (hi : r ≤ i ∧ i < m), α i = j) : 2 * (k - 1) ≤ (Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1))).card
- Source
- arXiv:2610.27956 Proposition 1
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For all natural numbers $m, k, r, b$ with $m \ne 0$, such that $m = r + b$, $2 \le k$, $k \le r$, and $k \le b$: Given any function $\alpha : \mathbb{Z}/m\mathbb{Z} \to \operatorname{Fin} k$, if: 1. for every color $j \in \operatorname{Fin} k$, there exists a natural number $i < r$ such that $\alpha(i \pmod m) = j$, and 2. for every color $j \in \operatorname{Fin} k$, there exists a natural number $i$ with $r \le i < m$ such that $\alpha(i \pmod m) = j$, then the number of indices $i \in \mathbb{Z}/m\mathbb{Z}$ such that $\alpha(i) \ne \alpha(i + 1)$ is at least $2(k - 1)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that any allocation of r red and b blue beads to k agents where each agent receives at least one bead of each color has at least 2(k - 1) adjacent assignment changes. First, an auxiliary induction proves that any sequence on n beads taking distinct values has at most one more distinct value than adjacent transitions. Applying this to the red and blue blocks yields at least k - 1 transitions strictly within the red beads and at least k - 1 strictly within the blue beads. Because the indices of these transitions are strictly less than m = r + b, their projections into ZMod m are injective and disjoint, giving at least 2(k - 1) total transitions on the cyclic necklace.
Base case: for n = 0, the image of {0} has cardinality at most 0 + 1 = 1.
By induction on n. In the base case n = 0, Finset.range 1 is {0}. The image of a singleton has cardinality at most 1, while the filter on the empty range Finset.range 0 has cardinality 0. Linear arithmetic and rewriting with Finset.range_one close the goal.
uses
Finset.range_oneinduction n with | zero => rw [Finset.range_one]; simp
Inductive decomposition: express the image and transition set for n + 1 by adjoining index n + 1 and transition n.
The range of n + 2 is obtained by adjoining n + 1 to the range of n + 1, so its image adjoins f(n + 1). Similarly, the transition filter on the range of n + 1 decomposes into the transition filter on the range of n plus the index n if f(n) ≠ f(n + 1). Rewriting with these identities sets up the inductive step.
uses
Finset.range_add_one,Finset.image_insert,Finset.filter_insert| succ n ih => have himg : (Finset.range (n + 1 + 1)).image f = insert (f (n+1)) ((Finset.range (n+1)).image f) := by nth_rewrite 1 [Finset.range_add_one (n := n+1)] rw [Finset.image_insert] have hfilt : (Finset.range (n + 1)).filter (fun i => f i ≠ f (i + 1)) = if f n ≠ f (n+1) then insert n ((Finset.range n).filter (fun i => f i ≠ f (i + 1))) else (Finset.range n).filter (fun i => f i ≠ f (i + 1)) := by rw [Finset.range_add_one, Finset.filter_insert] rw [himg, hfilt]Inductive step when a transition occurs: if f(n) ≠ f(n + 1), the induction hypothesis is preserved.
Since n does not belong to the range of n, inserting n increases the transition count by 1. Since adjoining f(n + 1) increases the image size by at most 1 (by Finset.card_insert_le), the induction hypothesis guarantees that the bound holds.
uses
Finset.card_insert_of_notMem,Finset.card_insert_lesplit_ifs with h · have hnot : n ∉ (Finset.range n).filter (fun i => f i ≠ f (i + 1)) := by simp rw [Finset.card_insert_of_notMem hnot] have := Finset.card_insert_le (f (n+1)) ((Finset.range (n + 1)).image f) omega
Inductive step when no transition occurs: if f(n) = f(n + 1), the bound holds directly.
When f(n) = f(n + 1), the element f(n + 1) is already in the image of {0, ..., n}, so inserting it does not increase the image cardinality (by Finset.card_insert_of_mem). The transition count also remains unchanged, so the induction hypothesis directly concludes the step.
uses
Finset.mem_image.mpr,Finset.card_insert_of_mem· have heq : f n = f (n+1) := by tauto have hmem : f (n+1) ∈ (Finset.range (n + 1)).image f := Finset.mem_image.mpr ⟨n, by simp, heq⟩ rw [Finset.card_insert_of_mem hmem] exact ih
For any sequence f on a range of length n, the number of distinct values taken is at most 1 plus the transition count.
Case split on n. If n = 0, both sides evaluate to 0 ≤ 0 + 1. If n is a successor, the claim follows immediately by applying cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succ.
uses
cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succcases n with | zero => simp | succ n => have := cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succ f n simpa using this
The canonical projection from ℕ to ZMod m is injective for indices strictly less than m.
For any natural numbers a, c < m with (a : ZMod m) = (c : ZMod m), taking the canonical representative in {0, ..., m - 1} via ZMod.val recovers a and c directly (by ZMod.val_cast_of_lt), so a = c.
uses
congrArg,ZMod.val,ZMod.val_cast_of_lthave hcast_inj : ∀ a c : ℕ, a < m → c < m → ((a : ZMod m) = (c : ZMod m)) → a = c := by intro a c ha hc h have hh := congrArg ZMod.val h rwa [ZMod.val_cast_of_lt ha, ZMod.val_cast_of_lt hc] at hh
There are at least k - 1 adjacent transitions among the r red beads.
Define A(i) = α(i : ZMod m). Because each of the k agents receives at least one red bead, the image of {0, ..., r - 1} under A is all of Fin k, having cardinality k. Applying the helper lemma cyclic_necklace_transitions_ge_two_mul_sub_one_changes gives k ≤ |{i < r - 1 : A(i) ≠ A(i + 1)}| + 1, so there are at least k - 1 internal transitions among red beads.
uses
Finset.eq_univ_of_forall,Finset.mem_image.mpr,Finset.mem_range.mpr,Finset.card_univ,Fintype.card_fin,cyclic_necklace_transitions_ge_two_mul_sub_one_changeslet A : ℕ → Fin k := fun i => α (i : ZMod m) have hRimage : (Finset.range r).image A = Finset.univ := by apply Finset.eq_univ_of_forall intro j obtain ⟨i, hii, h⟩ := hred j exact Finset.mem_image.mpr ⟨i, Finset.mem_range.mpr hii, h⟩ have hRcard : ((Finset.range r).image A).card = k := by rw [hRimage, Finset.card_univ, Fintype.card_fin] have hred_changes : k - 1 ≤ ((Finset.range (r - 1)).filter (fun i => A i ≠ A (i + 1))).card := by have := cyclic_necklace_transitions_ge_two_mul_sub_one_changes A r rw [hRcard] at this omega
There are at least k - 1 adjacent transitions among the b blue beads.
Define B(j) = α((r + j : ℕ) : ZMod m). Because each agent receives at least one blue bead, the image of {0, ..., b - 1} under B is all of Fin k, which has cardinality k. The same helper lemma implies k ≤ |{j < b - 1 : B(j) ≠ B(j + 1)}| + 1, yielding at least k - 1 internal transitions among blue beads.
uses
Finset.eq_univ_of_forall,Finset.mem_image.mpr,Finset.mem_range,Nat.add_sub_cancel',Finset.card_univ,Fintype.card_fin,cyclic_necklace_transitions_ge_two_mul_sub_one_changeslet B : ℕ → Fin k := fun j => α (((r + j : ℕ)) : ZMod m) have hBimage : (Finset.range b).image B = Finset.univ := by apply Finset.eq_univ_of_forall intro j obtain ⟨i, ⟨hri, him⟩, h⟩ := hblue j refine Finset.mem_image.mpr ⟨i - r, ?_, ?_⟩ · rw [Finset.mem_range]; omega · show α (((r + (i - r) : ℕ)) : ZMod m) = j rw [Nat.add_sub_cancel' hri] exact h have hBcard : ((Finset.range b).image B).card = k := by rw [hBimage, Finset.card_univ, Fintype.card_fin] have hblue_changes : k - 1 ≤ ((Finset.range (b - 1)).filter (fun j => B j ≠ B (j + 1))).card := by have := cyclic_necklace_transitions_ge_two_mul_sub_one_changes B b rw [hBcard] at this omega
The internal red transitions R1 and internal blue transitions B1 in ZMod m are both subsets of the necklace transitions T.
Let T be the set of all transitions i in ZMod m where α(i) ≠ α(i + 1). An internal red transition at index i < r - 1 satisfies (i : ZMod m) + 1 = (i + 1 : ZMod m), so α(i) ≠ α(i + 1) in ZMod m. Similarly, an internal blue transition at offset j < b - 1 satisfies (r + j : ZMod m) + 1 = (r + j + 1 : ZMod m), giving α(r + j) ≠ α(r + j + 1) in ZMod m.
uses
Finset.mem_image.mp,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_filter.mpset T := Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1)) with hT set R1 := ((Finset.range (r - 1)).filter (fun i => A i ≠ A (i + 1))).image (fun i : ℕ => (i : ZMod m)) with hR1 set B1 := ((Finset.range (b - 1)).filter (fun j => B j ≠ B (j + 1))).image (fun j : ℕ => ((r + j : ℕ) : ZMod m)) with hB1 have hR1T : R1 ⊆ T := by intro x hx rw [hR1] at hx obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx rw [hT] simp only [Finset.mem_filter, Finset.mem_univ, true_and] have hcast : ((i : ZMod m) + 1) = ((i + 1 : ℕ) : ZMod m) := by push_cast; ring rw [hcast] exact (Finset.mem_filter.mp hi).2 have hB1T : B1 ⊆ T := by intro x hx rw [hB1] at hx obtain ⟨j, hj, rfl⟩ := Finset.mem_image.mp hx rw [hT] simp only [Finset.mem_filter, Finset.mem_univ, true_and] have hcast : ((r + j : ℕ) : ZMod m) + 1 = ((r + j + 1 : ℕ) : ZMod m) := by push_cast; ring rw [hcast] have hjne : α ((r + j : ℕ) : ZMod m) ≠ α ((r + (j + 1) : ℕ) : ZMod m) := (Finset.mem_filter.mp hj).2 have heq : r + (j + 1) = r + j + 1 := by ring rw [heq] at hjne exact hjne
The set R1 has cardinality equal to the number of internal red transitions, which is at least k - 1.
Because all transition indices i satisfy i < r - 1 < m, the projection from ℕ to ZMod m is injective on this index set. Hence the image R1 has the same cardinality as the set of internal red transitions.
uses
Finset.card_image_of_injOn,Finset.mem_range.mp,Finset.mem_filter.mphave hR1card : R1.card = ((Finset.range (r - 1)).filter (fun i => A i ≠ A (i + 1))).card := by rw [hR1] apply Finset.card_image_of_injOn intro a ha c hc h have ha' : a < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp ha).1; omega have hc' : c < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp hc).1; omega exact hcast_inj a c ha' hc' h
The set B1 has cardinality equal to the number of internal blue transitions, which is at least k - 1.
Because all blue transition indices r + j satisfy r + j < r + b - 1 = m - 1 < m, the projection j ↦ (r + j : ZMod m) is injective. Hence B1 has the same cardinality as the set of internal blue transitions.
uses
Finset.card_image_of_injOn,Finset.mem_range.mp,Finset.mem_filter.mphave hB1card : B1.card = ((Finset.range (b - 1)).filter (fun j => B j ≠ B (j + 1))).card := by rw [hB1] apply Finset.card_image_of_injOn intro a ha c hc h have ha' : r + a < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp ha).1; omega have hc' : r + c < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp hc).1; omega have := hcast_inj (r + a) (r + c) ha' hc' h omega
The transition sets R1 and B1 are disjoint.
Any common element in ZMod m would mean (i : ZMod m) = (r + j : ZMod m) with i < r - 1 and j < b - 1. Since both i and r + j are strictly less than m, injectivity implies i = r + j ≥ r, contradicting i < r - 1. Thus R1 and B1 are disjoint.
uses
Finset.disjoint_left,Finset.mem_image.mp,Finset.mem_range.mp,Finset.mem_filter.mphave hdisj : Disjoint R1 B1 := by rw [Finset.disjoint_left] intro x hxR hxB rw [hR1] at hxR rw [hB1] at hxB obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hxR obtain ⟨j, hj, hxj⟩ := Finset.mem_image.mp hxB have hi' : i < r - 1 := Finset.mem_range.mp (Finset.mem_filter.mp hi).1 have hj' : j < b - 1 := Finset.mem_range.mp (Finset.mem_filter.mp hj).1 have him : i < m := by omega have hjm : r + j < m := by omega have := hcast_inj (r + j) i hjm him hxj omega
The necklace has at least 2(k - 1) index transitions where adjacent beads are assigned to different agents.
Since R1 and B1 are disjoint subsets of T, the cardinality of T is at least |R1 ∪ B1| = |R1| + |B1| ≥ (k - 1) + (k - 1) = 2(k - 1).
uses
Finset.card_union_of_disjoint,Finset.card_le_card,Finset.union_subsetcalc 2 * (k - 1) = (k - 1) + (k - 1) := by ring _ ≤ R1.card + B1.card := by rw [hR1card, hB1card]; omega _ = (R1 ∪ B1).card := (Finset.card_union_of_disjoint hdisj).symm _ ≤ T.card := Finset.card_le_card (Finset.union_subset hR1T hB1T)
Finset.range_one- The range of 1 is the singleton set {0}.
Finset.range_add_one- The range of n + 1 is obtained by inserting n into the range of n.
Finset.image_insert- The image of insert a s under f is obtained by inserting f(a) into the image of s under f.
Finset.filter_insert- Filtering insert a s by a predicate p inserts a into the filtered set if p(a) holds, and leaves the filtered set unchanged otherwise.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Finset.card_insert_of_mem- Inserting an element that already belongs to a finite set leaves its cardinality unchanged.
cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succ- For any sequence f, the number of distinct values taken on {0, ..., n} is at most 1 plus the number of adjacent transitions on {0, ..., n - 1}.
congrArg- If two elements are equal, applying any function to both yields equal results.
ZMod.val- The canonical representative in {0, ..., n - 1} of an element of ZMod n as a natural number.
ZMod.val_cast_of_lt- For a natural number a < n, the canonical representative (a : ZMod n).val is a itself.
Finset.eq_univ_of_forall- A finite set containing every element of a finite type is equal to the universal set Finset.univ.
Finset.mem_image.mpr- An element b belongs to the image of a set s under f if there exists some a in s such that f(a) = b.
Finset.mem_image.mp- If an element b belongs to the image of a set s under f, then there exists some a in s such that f(a) = b.
Finset.mem_range- A natural number m belongs to Finset.range n if and only if m < n.
Finset.mem_range.mpr- If a natural number m satisfies m < n, then m belongs to Finset.range n.
Finset.mem_range.mp- If a natural number m belongs to Finset.range n, then m < n.
Finset.card_univ- The cardinality of Finset.univ for a finite type is the cardinality of that type.
Fintype.card_fin- The finite type Fin n has cardinality n.
cyclic_necklace_transitions_ge_two_mul_sub_one_changes- For any sequence f on natural numbers, the number of distinct values taken on {0, ..., n - 1} is at most 1 plus the number of adjacent index transitions where f(i) ≠ f(i + 1) for i < n - 1.
Nat.add_sub_cancel'- For natural numbers with m ≤ n, m + (n - m) = n.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p(a) holds.
Finset.mem_filter.mp- If an element a belongs to Finset.filter p s, then a ∈ s and p(a) holds.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
true_and- The conjunction True ∧ p is equivalent to p.
Finset.card_image_of_injOn- If a function is injective on a finite set s, then the image of s has the same cardinality as s.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.union_subset- If both s and t are subsets of u, then their union s ∪ t is a subset of u.
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.
open Finset inlemma cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succ {β : Type*} [DecidableEq β] (f : ℕ → β) (n : ℕ) : ((Finset.range (n + 1)).image f).card ≤ ((Finset.range n).filter (fun i => f i ≠ f (i + 1))).card + 1 := by induction n with | zero => rw [Finset.range_one]; simp | succ n ih => have himg : (Finset.range (n + 1 + 1)).image f = insert (f (n+1)) ((Finset.range (n+1)).image f) := by nth_rewrite 1 [Finset.range_add_one (n := n+1)] rw [Finset.image_insert] have hfilt : (Finset.range (n + 1)).filter (fun i => f i ≠ f (i + 1)) = if f n ≠ f (n+1) then insert n ((Finset.range n).filter (fun i => f i ≠ f (i + 1))) else (Finset.range n).filter (fun i => f i ≠ f (i + 1)) := by rw [Finset.range_add_one, Finset.filter_insert] rw [himg, hfilt] split_ifs with h · have hnot : n ∉ (Finset.range n).filter (fun i => f i ≠ f (i + 1)) := by simp rw [Finset.card_insert_of_notMem hnot] have := Finset.card_insert_le (f (n+1)) ((Finset.range (n + 1)).image f) omega · have heq : f n = f (n+1) := by tauto have hmem : f (n+1) ∈ (Finset.range (n + 1)).image f := Finset.mem_image.mpr ⟨n, by simp, heq⟩ rw [Finset.card_insert_of_mem hmem] exact ihopen Finset inlemma cyclic_necklace_transitions_ge_two_mul_sub_one_changes {β : Type*} [DecidableEq β] (f : ℕ → β) (n : ℕ) : ((Finset.range n).image f).card ≤ ((Finset.range (n - 1)).filter (fun i => f i ≠ f (i + 1))).card + 1 := by cases n with | zero => simp | succ n => have := cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succ f n simpa using this/-- On a cyclic necklace with r contiguous red beads and b blue beads, any allocation giving each agent at least one bead of each color has at least 2(k - 1) color transitions. -/theorem cyclic_necklace_transitions_ge_two_mul_sub_one (m k r b : ℕ) [NeZero m] (hm : m = r + b) (hk : 2 ≤ k) (hr : k ≤ r) (hb : k ≤ b) (α : ZMod m → Fin k) (hred : ∀ j : Fin k, ∃ (i : ℕ) (hi : i < r), α i = j) (hblue : ∀ j : Fin k, ∃ (i : ℕ) (hi : r ≤ i ∧ i < m), α i = j) : 2 * (k - 1) ≤ (Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1))).card := by have hcast_inj : ∀ a c : ℕ, a < m → c < m → ((a : ZMod m) = (c : ZMod m)) → a = c := by intro a c ha hc h have hh := congrArg ZMod.val h rwa [ZMod.val_cast_of_lt ha, ZMod.val_cast_of_lt hc] at hh let A : ℕ → Fin k := fun i => α (i : ZMod m) have hRimage : (Finset.range r).image A = Finset.univ := by apply Finset.eq_univ_of_forall intro j obtain ⟨i, hii, h⟩ := hred j exact Finset.mem_image.mpr ⟨i, Finset.mem_range.mpr hii, h⟩ have hRcard : ((Finset.range r).image A).card = k := by rw [hRimage, Finset.card_univ, Fintype.card_fin] have hred_changes : k - 1 ≤ ((Finset.range (r - 1)).filter (fun i => A i ≠ A (i + 1))).card := by have := cyclic_necklace_transitions_ge_two_mul_sub_one_changes A r rw [hRcard] at this omega let B : ℕ → Fin k := fun j => α (((r + j : ℕ)) : ZMod m) have hBimage : (Finset.range b).image B = Finset.univ := by apply Finset.eq_univ_of_forall intro j obtain ⟨i, ⟨hri, him⟩, h⟩ := hblue j refine Finset.mem_image.mpr ⟨i - r, ?_, ?_⟩ · rw [Finset.mem_range]; omega · show α (((r + (i - r) : ℕ)) : ZMod m) = j rw [Nat.add_sub_cancel' hri] exact h have hBcard : ((Finset.range b).image B).card = k := by rw [hBimage, Finset.card_univ, Fintype.card_fin] have hblue_changes : k - 1 ≤ ((Finset.range (b - 1)).filter (fun j => B j ≠ B (j + 1))).card := by have := cyclic_necklace_transitions_ge_two_mul_sub_one_changes B b rw [hBcard] at this omega set T := Finset.univ.filter (fun i : ZMod m => α i ≠ α (i + 1)) with hT set R1 := ((Finset.range (r - 1)).filter (fun i => A i ≠ A (i + 1))).image (fun i : ℕ => (i : ZMod m)) with hR1 set B1 := ((Finset.range (b - 1)).filter (fun j => B j ≠ B (j + 1))).image (fun j : ℕ => ((r + j : ℕ) : ZMod m)) with hB1 have hR1T : R1 ⊆ T := by intro x hx rw [hR1] at hx obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx rw [hT] simp only [Finset.mem_filter, Finset.mem_univ, true_and] have hcast : ((i : ZMod m) + 1) = ((i + 1 : ℕ) : ZMod m) := by push_cast; ring rw [hcast] exact (Finset.mem_filter.mp hi).2 have hB1T : B1 ⊆ T := by intro x hx rw [hB1] at hx obtain ⟨j, hj, rfl⟩ := Finset.mem_image.mp hx rw [hT] simp only [Finset.mem_filter, Finset.mem_univ, true_and] have hcast : ((r + j : ℕ) : ZMod m) + 1 = ((r + j + 1 : ℕ) : ZMod m) := by push_cast; ring rw [hcast] have hjne : α ((r + j : ℕ) : ZMod m) ≠ α ((r + (j + 1) : ℕ) : ZMod m) := (Finset.mem_filter.mp hj).2 have heq : r + (j + 1) = r + j + 1 := by ring rw [heq] at hjne exact hjne have hR1card : R1.card = ((Finset.range (r - 1)).filter (fun i => A i ≠ A (i + 1))).card := by rw [hR1] apply Finset.card_image_of_injOn intro a ha c hc h have ha' : a < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp ha).1; omega have hc' : c < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp hc).1; omega exact hcast_inj a c ha' hc' h have hB1card : B1.card = ((Finset.range (b - 1)).filter (fun j => B j ≠ B (j + 1))).card := by rw [hB1] apply Finset.card_image_of_injOn intro a ha c hc h have ha' : r + a < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp ha).1; omega have hc' : r + c < m := by have := Finset.mem_range.mp (Finset.mem_filter.mp hc).1; omega have := hcast_inj (r + a) (r + c) ha' hc' h omega have hdisj : Disjoint R1 B1 := by rw [Finset.disjoint_left] intro x hxR hxB rw [hR1] at hxR rw [hB1] at hxB obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hxR obtain ⟨j, hj, hxj⟩ := Finset.mem_image.mp hxB have hi' : i < r - 1 := Finset.mem_range.mp (Finset.mem_filter.mp hi).1 have hj' : j < b - 1 := Finset.mem_range.mp (Finset.mem_filter.mp hj).1 have him : i < m := by omega have hjm : r + j < m := by omega have := hcast_inj (r + j) i hjm him hxj omega calc 2 * (k - 1) = (k - 1) + (k - 1) := by ring _ ≤ R1.card + B1.card := by rw [hR1card, hB1card]; omega _ = (R1 ∪ B1).card := (Finset.card_union_of_disjoint hdisj).symm _ ≤ T.card := Finset.card_le_card (Finset.union_subset hR1T hB1T)