AFTD Auto-Formalizing Theoretical Domains

cyclic_necklace_transitions_ge_two_mul_sub_one

theoremverified

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.

  1. 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.

    lines 6–7

    uses Finset.range_one

      induction n with
      | zero => rw [Finset.range_one]; simp
  2. 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.

    lines 8–16

    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]
  3. 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.

    lines 17–21

    uses Finset.card_insert_of_notMem, Finset.card_insert_le

        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
  4. 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.

    lines 22–26

    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
  5. 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.

    lines 33–37

    uses cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succ

      cases n with
      | zero => simp
      | succ n =>
        have := cyclic_necklace_transitions_ge_two_mul_sub_one_changes_succ f n
        simpa using this
  6. 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.

    lines 46–49

    uses congrArg, ZMod.val, ZMod.val_cast_of_lt

      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
  7. 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.

    lines 50–61

    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_changes

      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
  8. 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.

    lines 62–77

    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_changes

      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
  9. 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.

    lines 78–103

    uses Finset.mem_image.mp, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_filter.mp

      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
  10. 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.

    lines 104–112

    uses Finset.card_image_of_injOn, Finset.mem_range.mp, Finset.mem_filter.mp

      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
  11. 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.

    lines 113–122

    uses Finset.card_image_of_injOn, Finset.mem_range.mp, Finset.mem_filter.mp

      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
  12. 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.

    lines 123–135

    uses Finset.disjoint_left, Finset.mem_image.mp, Finset.mem_range.mp, Finset.mem_filter.mp

      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
  13. 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).

    lines 136–139

    uses Finset.card_union_of_disjoint, Finset.card_le_card, Finset.union_subset

      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)
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

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)
See it in the graphDiscuss this resultChallenge it