AFTD Auto-Formalizing Theoretical Domains

planar_necklace_cyclic_window_red_count

theoremverified

Let w : ℕ → Fin 2 be N-periodic (w (i + N) = w i) with N = 3k, k > 0, and suppose that among the N positions exactly 3a are red (w i = 0). Then some window of k consecutive positions contains exactly a red positions.

Statement

theorem planar_necklace_cyclic_window_red_count
    (k N a : ℕ) (hk : 0 < k) (hN : N = 3 * k) (w : ℕ → Fin 2)
    (hperiod : ∀ i, w (i + N) = w i)
    (hred : ((Finset.range N).filter (fun i => w i = 0)).card = 3 * a) :
    ∃ i : ℕ, ((Finset.range k).filter (fun j => w (i + j) = 0)).card = a
Source
step towards planar_necklace_three_agents_three_cuts
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that some window of length k in a 3k-periodic necklace contains exactly a red beads out of 3a total red beads, we partition the first 3k beads into three consecutive disjoint windows of length k. Since their red counts sum to 3a, by averaging one window has at most a red beads and another has at least a red beads. Because the window red count changes by at most 1 when shifting by one position, a discrete intermediate value theorem guarantees that some intermediate window contains exactly a red beads.

  1. Base case d = 0 for the discrete intermediate value theorem on ℕ.

    When v = u + 0, we have v = u. The condition that a is straddled by f(u) and f(v) forces f(u) = a, so u itself is the required intermediate point.

    lines 8–15

      intro d
      induction d with
      | zero =>
          intro u v a hv hstrad
          have hv' : v = u := by omega
          subst v
          simp only [Nat.add_zero] at hstrad
          exact ⟨u, le_rfl, le_rfl, by omega⟩
  2. Inductive step for the discrete intermediate value theorem on ℕ.

    Assuming the claim for intervals of length d, consider an interval [u, v] of length d + 1. If f(u) = a, u is the witness. Otherwise, if f(u) < a ≤ f(v), the bound f(u+1) ≤ f(u) + 1 implies f(u+1) ≤ a. If f(u+1) = a, u+1 is the witness; if f(u+1) < a, the induction hypothesis applies to [u+1, v] (which has length d). The symmetric case f(v) ≤ a < f(u) is identical using f(u) ≤ f(u+1) + 1.

    lines 16–40

      | succ d ih =>
          intro u v a hv hstrad
          rcases hstrad with ⟨hle, hge⟩ | ⟨hle, hge⟩
          · by_cases hfa : f u = a
            · exact ⟨u, le_rfl, by omega, hfa⟩
            · have hlt : f u < a := lt_of_le_of_ne hle hfa
              have hnext_le : f (u+1) ≤ a := by
                have := hup u
                omega
              by_cases hnext : f (u+1) = a
              · exact ⟨u+1, by omega, by omega, hnext⟩
              · have hnext_lt : f (u+1) < a := lt_of_le_of_ne hnext_le hnext
                obtain ⟨i, hi1, hi2, hia⟩ := ih (u+1) v a (by omega) (Or.inl ⟨le_of_lt hnext_lt, hge⟩)
                exact ⟨i, by omega, hi2, hia⟩
          · by_cases hfa : f u = a
            · exact ⟨u, le_rfl, by omega, hfa⟩
            · have hgt : a < f u := lt_of_le_of_ne hge (Ne.symm hfa)
              have hnext_ge : a ≤ f (u+1) := by
                have := hdown u
                omega
              by_cases hnext : f (u+1) = a
              · exact ⟨u+1, by omega, by omega, hnext⟩
              · have hnext_gt : a < f (u+1) := lt_of_le_of_ne hnext_ge (Ne.symm hnext)
                obtain ⟨i, hi1, hi2, hia⟩ := ih (u+1) v a (by omega) (Or.inr ⟨hle, le_of_lt hnext_gt⟩)
                exact ⟨i, by omega, hi2, hia⟩
  3. The discrete intermediate value theorem holds for any interval [u, v] with u ≤ v.

    Applying planar_necklace_cyclic_window_red_count_walk_aux with d = v - u gives the intermediate point i ∈ [u, v] where f(i) = a.

    lines 42–50

    uses planar_necklace_cyclic_window_red_count_walk_aux

    lemma planar_necklace_cyclic_window_red_count_walk
        (f : ℕ → ℕ)
        (hup : ∀ i, f (i+1) ≤ f i + 1)
        (hdown : ∀ i, f i ≤ f (i+1) + 1)
        (u v a : ℕ) (huv : u ≤ v)
        (hstrad : (f u ≤ a ∧ a ≤ f v) ∨ (f v ≤ a ∧ a ≤ f u)) :
        ∃ i, u ≤ i ∧ i ≤ v ∧ f i = a :=
      planar_necklace_cyclic_window_red_count_walk_aux f hup hdown (v-u) u v a (by omega) hstrad
    
  4. Define the red indicator function c, the window red count R, and the cumulative count f.

    We define c(j) to indicate whether bead j is red (w j = 0), R(i) as the number of red beads in the window of length k starting at i, and f(n) as the total red beads in the first n beads.

    lines 57–60

      let c : ℕ → ℕ := fun j => if w j = 0 then 1 else 0
      let R : ℕ → ℕ := fun i => ∑ j ∈ Finset.range k, c (i+j)
      let f : ℕ → ℕ := fun n => ∑ j ∈ Finset.range n, c j
      have hper : w (0 + N) = w 0 := hperiod 0
  5. Relate the cumulative count f to the window count R and successive counts.

    Splitting the sum over range (i + k) into range i and range k gives f(i + k) = f(i) + R(i). Similarly, f(n + 1) = f(n) + c(n). Furthermore, c(n) is always 0 or 1.

    lines 61–72

    uses Finset.sum_range_add, Finset.sum_range_succ

      have hf_add : ∀ i, f (i+k) = f i + R i := by
        intro i
        dsimp [f, R]
        rw [Finset.sum_range_add]
      have hf_succ : ∀ n, f (n+1) = f n + c n := by
        intro n
        dsimp [f]
        rw [Finset.sum_range_succ]
      have hc01 : ∀ n, c n = 0 ∨ c n = 1 := by
        intro n
        dsimp [c]
        split_ifs <;> simp
  6. The window red count R changes by at most 1 at each step. automation

    From f(i + 1 + k) = f(i + 1) + R(i + 1) and f(i + k) = f(i) + R(i), the change in window count is R(i+1) - R(i) = c(i+k) - c(i). Because c takes values in {0, 1}, the step size is at most 1 in either direction: R(i+1) ≤ R(i) + 1 and R(i) ≤ R(i+1) + 1. Linear arithmetic over ℕ verifies both bounds.

    lines 73–92

      have hRstep_up : ∀ i, R (i+1) ≤ R i + 1 := by
        intro i
        have h1 := hf_add (i+1)
        have h2 := hf_add i
        have h3 : f (i+1+k) = f (i+k+1) := congrArg f (by omega)
        have h4 := hf_succ (i+k)
        have h5 := hf_succ i
        have h6 : c (i+k) ≤ 1 := by rcases hc01 (i+k) with h | h <;> omega
        rw [h3] at h1
        omega
      have hRstep_down : ∀ i, R i ≤ R (i+1) + 1 := by
        intro i
        have h1 := hf_add (i+1)
        have h2 := hf_add i
        have h3 : f (i+1+k) = f (i+k+1) := congrArg f (by omega)
        have h4 := hf_succ (i+k)
        have h5 := hf_succ i
        have h6 : c i ≤ 1 := by rcases hc01 i with h | h <;> omega
        rw [h3] at h1
        omega
  7. The three non-overlapping windows of length k sum to 3a. automation

    The three consecutive windows starting at 0, k, and 2k cover the first 3k = N beads. Telescoping the relations f(k) = R(0), f(2k) = f(k) + R(k), and f(3k) = f(2k) + R(2k) shows that R(0) + R(k) + R(2k) = f(3k) = f(N) = 3a.

    lines 93–109

    uses Finset.card_filter

      have hsum : R 0 + R k + R (2*k) = 3*a := by
        have h0 : f k = R 0 := by
          simpa [f] using hf_add 0
        have hk2 : f (2*k) = f k + R k := by
          have h := hf_add k
          rw [show k+k = 2*k by omega] at h
          exact h
        have h2k3 : f (3*k) = f (2*k) + R (2*k) := by
          have h := hf_add (2*k)
          rw [show 2*k+k = 3*k by omega] at h
          exact h
        have hfN : f N = 3*a := by
          dsimp [f]
          rw [Finset.card_filter] at hred
          exact hred
        rw [hN] at hfN
        omega
  8. At least one of the three window counts is ≤ a and at least one is ≥ a. automation

    If all three window counts were strictly greater than a, their sum would exceed 3a; if all three were strictly less than a, their sum would be less than 3a. In either case, linear arithmetic derives a contradiction with the sum being 3a.

    lines 110–117

      have hlow : R 0 ≤ a ∨ R k ≤ a ∨ R (2*k) ≤ a := by
        by_contra h
        simp only [not_or, not_le] at h
        omega
      have hhigh : a ≤ R 0 ∨ a ≤ R k ∨ a ≤ R (2*k) := by
        by_contra h
        simp only [not_or, not_le] at h
        omega
  9. There exist indices u ≤ v among {0, k, 2k} that straddle a.

    By case analysis on which window count is ≤ a and which is ≥ a, we obtain two indices u ≤ v in {0, k, 2k} such that a lies between R(u) and R(v).

    lines 118–131

      have hstrad : ∃ u v, u ≤ v ∧ ((R u ≤ a ∧ a ≤ R v) ∨ (R v ≤ a ∧ a ≤ R u)) := by
        rcases hlow with h0 | hkR | h2
        · rcases hhigh with g0 | gk | g2
          · exact ⟨0, 0, le_rfl, Or.inl ⟨h0, g0⟩⟩
          · exact ⟨0, k, by omega, Or.inl ⟨h0, gk⟩⟩
          · exact ⟨0, 2*k, by omega, Or.inl ⟨h0, g2⟩⟩
        · rcases hhigh with g0 | gk | g2
          · exact ⟨0, k, by omega, Or.inr ⟨hkR, g0⟩⟩
          · exact ⟨k, k, le_rfl, Or.inl ⟨hkR, gk⟩⟩
          · exact ⟨k, 2*k, by omega, Or.inl ⟨hkR, g2⟩⟩
        · rcases hhigh with g0 | gk | g2
          · exact ⟨0, 2*k, by omega, Or.inr ⟨h2, g0⟩⟩
          · exact ⟨k, 2*k, by omega, Or.inr ⟨h2, gk⟩⟩
          · exact ⟨2*k, 2*k, le_rfl, Or.inl ⟨h2, g2⟩⟩
  10. Some window of length k contains exactly a red beads.

    Since R has step size at most 1 and straddles a between u and v, planar_necklace_cyclic_window_red_count_walk guarantees an index i between u and v where R(i) = a. Unfolding the definition of R and translating back to the filter cardinality completes the proof.

    lines 132–139

    uses planar_necklace_cyclic_window_red_count_walk, Finset.card_filter

      obtain ⟨u, v, huv, hstr⟩ := hstrad
      obtain ⟨i, hiu, hiv, hia⟩ :=
        planar_necklace_cyclic_window_red_count_walk R hRstep_up hRstep_down u v a huv hstr
      refine ⟨i, ?_⟩
      have hRfilter : ((Finset.range k).filter (fun j => w (i+j) = 0)).card = R i := by
        dsimp [R, c]
        rw [Finset.card_filter]
      rw [hRfilter, hia]
planar_necklace_cyclic_window_red_count_walk_aux
A discrete intermediate value theorem parameterized by the interval length d = v - u: a function on ℕ with step size at most 1 takes all intermediate integer values between f(u) and f(v).
planar_necklace_cyclic_window_red_count_walk
Discrete intermediate value theorem: a function on ℕ whose consecutive values differ by at most 1 takes all intermediate values between f(u) and f(v) on any interval [u, v].
Finset.sum_range_add
The sum of a function over range (n + m) splits into the sum over range n plus the shifted sum over range m.
Finset.sum_range_succ
The sum of a function over range (n + 1) equals the sum over range n plus the term at n.
Finset.card_filter
The cardinality of the filter of a finite set is the sum of the indicator function of the predicate.

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

lemma planar_necklace_cyclic_window_red_count_walk_aux    (f : ℕ → ℕ)    (hup : ∀ i, f (i+1) ≤ f i + 1)    (hdown : ∀ i, f i ≤ f (i+1) + 1) :    ∀ d u v a, v = u + d →      ((f u ≤ a ∧ a ≤ f v) ∨ (f v ≤ a ∧ a ≤ f u)) →      ∃ i, u ≤ i ∧ i ≤ v ∧ f i = a := by  intro d  induction d with  | zero =>      intro u v a hv hstrad      have hv' : v = u := by omega      subst v      simp only [Nat.add_zero] at hstrad      exact ⟨u, le_rfl, le_rfl, by omega⟩  | succ d ih =>      intro u v a hv hstrad      rcases hstrad with ⟨hle, hge⟩ | ⟨hle, hge⟩      · by_cases hfa : f u = a        · exact ⟨u, le_rfl, by omega, hfa⟩        · have hlt : f u < a := lt_of_le_of_ne hle hfa          have hnext_le : f (u+1) ≤ a := by            have := hup u            omega          by_cases hnext : f (u+1) = a          · exact ⟨u+1, by omega, by omega, hnext⟩          · have hnext_lt : f (u+1) < a := lt_of_le_of_ne hnext_le hnext            obtain ⟨i, hi1, hi2, hia⟩ := ih (u+1) v a (by omega) (Or.inl ⟨le_of_lt hnext_lt, hge⟩)            exact ⟨i, by omega, hi2, hia⟩      · by_cases hfa : f u = a        · exact ⟨u, le_rfl, by omega, hfa⟩        · have hgt : a < f u := lt_of_le_of_ne hge (Ne.symm hfa)          have hnext_ge : a ≤ f (u+1) := by            have := hdown u            omega          by_cases hnext : f (u+1) = a          · exact ⟨u+1, by omega, by omega, hnext⟩          · have hnext_gt : a < f (u+1) := lt_of_le_of_ne hnext_ge (Ne.symm hnext)            obtain ⟨i, hi1, hi2, hia⟩ := ih (u+1) v a (by omega) (Or.inr ⟨hle, le_of_lt hnext_gt⟩)            exact ⟨i, by omega, hi2, hia⟩lemma planar_necklace_cyclic_window_red_count_walk    (f : ℕ → ℕ)    (hup : ∀ i, f (i+1) ≤ f i + 1)    (hdown : ∀ i, f i ≤ f (i+1) + 1)    (u v a : ℕ) (huv : u ≤ v)    (hstrad : (f u ≤ a ∧ a ≤ f v) ∨ (f v ≤ a ∧ a ≤ f u)) :    ∃ i, u ≤ i ∧ i ≤ v ∧ f i = a :=  planar_necklace_cyclic_window_red_count_walk_aux f hup hdown (v-u) u v a (by omega) hstrad/-- Discrete circular-window lemma: a cyclic 2-coloured necklace with 3a red of 3k beads has a window of k consecutive beads with exactly a red beads. -/theorem planar_necklace_cyclic_window_red_count    (k N a : ℕ) (hk : 0 < k) (hN : N = 3 * k) (w : ℕ → Fin 2)    (hperiod : ∀ i, w (i + N) = w i)    (hred : ((Finset.range N).filter (fun i => w i = 0)).card = 3 * a) :    ∃ i : ℕ, ((Finset.range k).filter (fun j => w (i + j) = 0)).card = a := by  let c : ℕ → ℕ := fun j => if w j = 0 then 1 else 0  let R : ℕ → ℕ := fun i => ∑ j ∈ Finset.range k, c (i+j)  let f : ℕ → ℕ := fun n => ∑ j ∈ Finset.range n, c j  have hper : w (0 + N) = w 0 := hperiod 0  have hf_add : ∀ i, f (i+k) = f i + R i := by    intro i    dsimp [f, R]    rw [Finset.sum_range_add]  have hf_succ : ∀ n, f (n+1) = f n + c n := by    intro n    dsimp [f]    rw [Finset.sum_range_succ]  have hc01 : ∀ n, c n = 0 ∨ c n = 1 := by    intro n    dsimp [c]    split_ifs <;> simp  have hRstep_up : ∀ i, R (i+1) ≤ R i + 1 := by    intro i    have h1 := hf_add (i+1)    have h2 := hf_add i    have h3 : f (i+1+k) = f (i+k+1) := congrArg f (by omega)    have h4 := hf_succ (i+k)    have h5 := hf_succ i    have h6 : c (i+k) ≤ 1 := by rcases hc01 (i+k) with h | h <;> omega    rw [h3] at h1    omega  have hRstep_down : ∀ i, R i ≤ R (i+1) + 1 := by    intro i    have h1 := hf_add (i+1)    have h2 := hf_add i    have h3 : f (i+1+k) = f (i+k+1) := congrArg f (by omega)    have h4 := hf_succ (i+k)    have h5 := hf_succ i    have h6 : c i ≤ 1 := by rcases hc01 i with h | h <;> omega    rw [h3] at h1    omega  have hsum : R 0 + R k + R (2*k) = 3*a := by    have h0 : f k = R 0 := by      simpa [f] using hf_add 0    have hk2 : f (2*k) = f k + R k := by      have h := hf_add k      rw [show k+k = 2*k by omega] at h      exact h    have h2k3 : f (3*k) = f (2*k) + R (2*k) := by      have h := hf_add (2*k)      rw [show 2*k+k = 3*k by omega] at h      exact h    have hfN : f N = 3*a := by      dsimp [f]      rw [Finset.card_filter] at hred      exact hred    rw [hN] at hfN    omega  have hlow : R 0 ≤ a ∨ R k ≤ a ∨ R (2*k) ≤ a := by    by_contra h    simp only [not_or, not_le] at h    omega  have hhigh : a ≤ R 0 ∨ a ≤ R k ∨ a ≤ R (2*k) := by    by_contra h    simp only [not_or, not_le] at h    omega  have hstrad : ∃ u v, u ≤ v ∧ ((R u ≤ a ∧ a ≤ R v) ∨ (R v ≤ a ∧ a ≤ R u)) := by    rcases hlow with h0 | hkR | h2    · rcases hhigh with g0 | gk | g2      · exact ⟨0, 0, le_rfl, Or.inl ⟨h0, g0⟩⟩      · exact ⟨0, k, by omega, Or.inl ⟨h0, gk⟩⟩      · exact ⟨0, 2*k, by omega, Or.inl ⟨h0, g2⟩⟩    · rcases hhigh with g0 | gk | g2      · exact ⟨0, k, by omega, Or.inr ⟨hkR, g0⟩⟩      · exact ⟨k, k, le_rfl, Or.inl ⟨hkR, gk⟩⟩      · exact ⟨k, 2*k, by omega, Or.inl ⟨hkR, g2⟩⟩    · rcases hhigh with g0 | gk | g2      · exact ⟨0, 2*k, by omega, Or.inr ⟨h2, g0⟩⟩      · exact ⟨k, 2*k, by omega, Or.inr ⟨h2, gk⟩⟩      · exact ⟨2*k, 2*k, le_rfl, Or.inl ⟨h2, g2⟩⟩  obtain ⟨u, v, huv, hstr⟩ := hstrad  obtain ⟨i, hiu, hiv, hia⟩ :=    planar_necklace_cyclic_window_red_count_walk R hRstep_up hRstep_down u v a huv hstr  refine ⟨i, ?_⟩  have hRfilter : ((Finset.range k).filter (fun j => w (i+j) = 0)).card = R i := by    dsimp [R, c]    rw [Finset.card_filter]  rw [hRfilter, hia]
See it in the graphDiscuss this resultChallenge it