planar_necklace_cyclic_window_red_count
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.
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.
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⟩
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.
| 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⟩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.
uses
planar_necklace_cyclic_window_red_count_walk_auxlemma 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
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.
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
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.
uses
Finset.sum_range_add,Finset.sum_range_succhave 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
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.
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
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.
uses
Finset.card_filterhave 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
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.
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
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).
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⟩⟩
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.
uses
planar_necklace_cyclic_window_red_count_walk,Finset.card_filterobtain ⟨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.
- The file first establishes a discrete intermediate value theorem (the walk lemma) by induction on the interval length, before proving the main combinatorial result.
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.
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]