spider_blocked_incoming_one_outward_options_eq
For r ≥ 2, the raw options list generated by [(1, outward), (r, φ)] at fuel r + 2 with centre status incoming unfolds to the explicit list of head options plus flatMap over range (r - 2) and the final cut, under the induction hypothesis.
Statement
theorem spider_blocked_incoming_one_outward_options_eq (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) (ih : ∀ r' < r, 1 ≤ r' → ∀ φ' ≠ SpiderLegEnd.free, spider_gamma (r' + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r', φ')] = r' ^^^ 1) : ([(1, SpiderLegEnd.outward), (r, φ)].zipIdx.flatMap (fun ⟨⟨h, phi⟩, idx⟩ => let rest := [(1, SpiderLegEnd.outward), (r, φ)].eraseIdx idx (List.range h).flatMap (fun j_zero => let j := j_zero + 1 [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta => if j == h ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then none else let d := spider_rho (h - j) delta phi if j ≥ 2 then let new_L := (j - 1, delta) :: rest some (d ^^^ spider_gamma (r + 1) CentreStatus.incoming new_L) else let new_s := spider_update_centre CentreStatus.incoming delta some (d ^^^ spider_gamma (r + 1) new_s rest) ) ) )) = ([r, spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ 1] ++ (List.range (r - 2)).flatMap (fun idx => let i := idx + 1 [spider_rho (r - 1 - i) SpiderLegEnd.inward φ ^^^ (i ^^^ 1), spider_rho (r - 1 - i) SpiderLegEnd.outward φ ^^^ (i ^^^ 1)]) ++ [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)])
- Source
- step towards spider_blocked_incoming_one_outward
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- spider_gamma_fuel_independentFor every fuel at least the total number of markable edges in L plus one, the value of spider_gamma does not depend on the fuel: it equals…
- spider_gamma_swap_twoThe Grundy value of a two-legged spider state is invariant under swapping the two legs in the list.
- spider_rhoThe function spider_rho takes h : ℕ and delta, phi : SpiderLegEnd, returning h if phi = free; if phi = inward, it returns h % 2 when delta…
- SpiderLegEndThe end condition of an attached leg in a spider state is either free (no arc on the leg), inward (pointing towards the centre), or…
- spider_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
- spider_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
- Used by 1
- spider_blocked_incoming_one_outwardFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(r) equals r xor 1 for every r ≥ 1 and both φ.
The proof, explained
To compute the game options for the two-leg position [(1, outward), (r, φ)] with incoming centre status, the proof decomposes the list of available moves into cuts on leg 0 and cuts on leg 1. Cutting leg 0 leaves only leg 1 with a free centre, evaluating to the singleton option [r]. The cuts on leg 1 are partitioned into the initial cut of length 1, intermediate cuts of length 2 ≤ j < r, and the final cut of length r. For each cut with j ≥ 2, the remaining spider has two legs and incoming centre, so swapping the legs and applying the induction hypothesis computes its nim-value as (j - 1) ^^^ 1. Concatenating these pieces yields the simplified explicit list of all option nim-values.
The raw options list for [(1, outward), (r, φ)] splits into moves on leg 0 and moves on leg 1.
The two-element list of legs has indices 0 and 1. Expanding List.zipIdx, unfolding the flatMap over this two-element list, and simplifying index erasure decomposes the options into cuts on the first leg (captured by spider_blocked_incoming_one_outward_options_eq_leg0) appended to cuts on the second leg (captured by spider_blocked_incoming_one_outward_options_eq_leg1 mapped over List.range r).
uses
List.zipIdx,List.flatMap_cons,List.flatMap_nil,List.append_nil,List.eraseIdx_cons_zero,List.eraseIdx_cons_succrw [show ([(1, SpiderLegEnd.outward), (r, φ)] : List (ℕ × SpiderLegEnd)).zipIdx = [((1, SpiderLegEnd.outward), 0), ((r, φ), 1)] from by simp [List.zipIdx]] simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil, List.eraseIdx_cons_zero, List.eraseIdx_cons_succ] rfl
For any n, List.range (n + 2) splits into 0, the range of n shifted by +1, and n + 1.
Proved by induction on n. The base case n = 0 holds definitionally. For the induction step, rewriting (k + 1) + 2 = (k + 2) + 1, applying List.range_succ and the induction hypothesis, and distributing List.map over list concatenation with List.map_append rearranges the list into head 0, shifted elements, and the last element k + 2.
uses
List.range_succ,List.map_append,List.cons_append,List.append_associnduction n with | zero => rfl | succ k ih => rw [show k + 1 + 2 = (k + 2) + 1 by ring, List.range_succ, ih] rw [show k + 1 + 1 = k + 2 by ring] rw [List.range_succ (n:=k), List.map_append] simp [List.cons_append, List.append_assoc]
For r ≥ 2, List.range r decomposes into 0, intermediate elements mapped from range (r - 2) by +1, and r - 1.
Rewriting r = (r - 2) + 2 via arithmetic, this follows directly from spider_blocked_incoming_one_outward_options_eq_range_succ_two with n = r - 2.
uses
spider_blocked_incoming_one_outward_options_eq_range_succ_twoconv => lhs; rw [show r = (r-2)+2 by omega] rw [spider_blocked_incoming_one_outward_options_eq_range_succ_two] rw [show r - 2 + 1 = r - 1 by omega]
The options generated by cutting leg 0 evaluate to the singleton list [r].
Leg 0 has length 1 with outward orientation, so the only cut length is j = 1. The rules filter out inward orientation, leaving only outward, which transitions the centre to free on the single remaining leg [(r, φ)]. For φ ≠ free, spider_gamma on [(r, φ)] with free centre evaluates to r. Since the cut piece has length 0, its nim-value is 0, yielding 0 ^^^ r = r.
uses
spider_blocked_incoming_one_outward_options_eq_leg0,List.range_one,List.flatMap_cons,List.flatMap_nil,List.append_nilhave hg : spider_gamma (r + 1) CentreStatus.free [(r, φ)] = r := by rcases φ with _ | _ | _ · exact absurd rfl hφ · simp only [spider_gamma]; simp [spider_rho_star] · simp only [spider_gamma]; simp [spider_rho_star] unfold spider_blocked_incoming_one_outward_options_eq_leg0 simp only [List.range_one, List.flatMap_cons, List.flatMap_nil, List.filterMap_cons, List.filterMap_nil, List.append_nil] simp only [spider_rho, spider_update_centre] rw [hg] simp
Cutting length 1 (j_zero = 0) on leg 1 produces two options, each XOR-summed with 1.
When j = 1, since r ≥ 2, j ≠ r and j < 2. The cut removes leg 1 completely, leaving only the first leg [(1, outward)]. For either choice of new orientation δ ∈ {inward, outward}, the centre updates to incoming or free, and spider_gamma on [(1, outward)] evaluates to 1. The cut piece of length r - 1 contributes ρ(r - 1, δ, φ), giving the two options ρ(r - 1, inward, φ) ^^^ 1 and ρ(r - 1, outward, φ) ^^^ 1.
uses
spider_blocked_incoming_one_outward_options_eq_leg1,Bool.eq_false_iff,beq_iff_eqhave h1r : (1 == r) = false := by rw [Bool.eq_false_iff]; simp [beq_iff_eq]; omega have h1g : ¬ (1 ≥ 2) := by omega unfold spider_blocked_incoming_one_outward_options_eq_leg1 simp only [Nat.zero_add, h1r, Bool.false_eq_true, false_and, if_false, h1g, if_false] simp only [List.filterMap_cons, List.filterMap_nil, spider_update_centre] rw [show spider_gamma (r+1) CentreStatus.incoming [(1, SpiderLegEnd.outward)] = 1 from by simp only [spider_gamma]; simp [spider_rho]] rw [show spider_gamma (r+1) CentreStatus.free [(1, SpiderLegEnd.outward)] = 1 from by simp only [spider_gamma]; simp [spider_rho_star]]
For any 2 ≤ j ≤ r and δ ≠ free, the two-leg spider [(j - 1, δ), (1, outward)] with incoming centre has nim-value (j - 1) ^^^ 1.
By spider_gamma_fuel_independent, the fuel r + 1 can be replaced by the minimal fuel j + 1. Swapping the two legs using spider_gamma_swap_two transforms the state to [(1, outward), (j - 1, δ)], to which the induction hypothesis ih applies at length j - 1 < r, yielding (j - 1) ^^^ 1.
uses
spider_gamma_fuel_independent,spider_gamma_swap_twohave hmid : ∀ (j : ℕ) (δ : SpiderLegEnd), δ ≠ SpiderLegEnd.free → 2 ≤ j → j ≤ r → spider_gamma (r+1) CentreStatus.incoming [(j-1, δ), (1, SpiderLegEnd.outward)] = (j-1) ^^^ 1 := by intro j δ hδ h2 hjr have hsum : ((([(j-1, δ), (1, SpiderLegEnd.outward)]).map Prod.fst).sum) + 1 = j + 1 := by simp; omega rw [spider_gamma_fuel_independent (r+1) CentreStatus.incoming _ (by omega)] rw [hsum] rw [spider_gamma_swap_two] have := ih (j-1) (by omega) (by omega) δ hδ rw [show (j-1)+2 = j+1 by omega] at this exact this
For each intermediate index idx < r - 2, the cut j = idx + 2 on leg 1 yields two options XOR-summed with (idx + 1) ^^^ 1.
With j = idx + 2, we have 2 ≤ j < r, so neither boundary filtering condition triggers. The cut piece has length r - j = r - 1 - (idx + 1). The remaining spider has legs [(idx + 1, δ), (1, outward)] and incoming centre, which evaluates to (idx + 1) ^^^ 1 by the previous step (hmid) for both δ = inward and δ = outward.
uses
spider_blocked_incoming_one_outward_options_eq_leg1,Bool.eq_false_iff,beq_iff_equnfold spider_blocked_incoming_one_outward_options_eq_leg1 rw [show idx + 1 + 1 = idx + 2 by omega] have hjr : (idx + 2 == r) = false := by rw [Bool.eq_false_iff]; simp [beq_iff_eq]; omega have hj2 : 2 ≤ idx + 2 := by omega simp only [hjr, Bool.false_eq_true, false_and, if_false, hj2, if_pos] simp only [List.filterMap_cons, List.filterMap_nil] rw [show r - (idx + 2) = r - 1 - (idx + 1) by omega] rw [hmid (idx+2) SpiderLegEnd.inward (by decide) hj2 (by omega)] rw [hmid (idx+2) SpiderLegEnd.outward (by decide) hj2 (by omega)] simp only [show idx + 2 - 1 = idx + 1 by omega]
After a cut of length r on leg 1, the remaining spider [(r - 1, φ), (1, outward)] with incoming centre has nim-value (r - 1) ^^^ 1.
Swapping the two legs via spider_gamma_swap_two and applying the induction hypothesis ih at length r - 1 < r yields (r - 1) ^^^ 1.
uses
spider_gamma_swap_twohave hg : spider_gamma (r+1) CentreStatus.incoming [(r-1,φ),(1, SpiderLegEnd.outward)] = (r-1)^^^1 := by rw [spider_gamma_swap_two] have := ih (r-1) (by omega) (by omega) φ hφ rw [show (r-1)+2 = r+1 by omega] at this exact this
The final cut j = r (j_zero = r - 1) on leg 1 yields the single option ρ(0, φ, φ) ^^^ ((r - 1) ^^^ 1).
Case analysis on φ ≠ free: when j = r, any orientation δ ≠ φ is filtered out, leaving only δ = φ. Since r ≥ 2, the remaining leg has length r - 1 with orientation φ. The cut piece has length r - r = 0, contributing ρ(0, φ, φ), while the remaining spider evaluates to (r - 1) ^^^ 1 by hg.
uses
spider_blocked_incoming_one_outward_options_eq_leg1rcases φ with _ | _ | _ · exact absurd rfl hφ · unfold spider_blocked_incoming_one_outward_options_eq_leg1 rw [show r - 1 + 1 = r by omega] simp only [beq_self_eq_true, true_and, List.filterMap_cons, List.filterMap_nil, show (SpiderLegEnd.inward ≠ SpiderLegEnd.free) = True from by decide, show (SpiderLegEnd.inward ≠ SpiderLegEnd.inward) = False from by decide, show (SpiderLegEnd.outward ≠ SpiderLegEnd.inward) = True from by decide, and_true, if_false, if_true, hr, spider_rho] rw [show r - r = 0 by omega, hg] · unfold spider_blocked_incoming_one_outward_options_eq_leg1 rw [show r - 1 + 1 = r by omega] simp only [beq_self_eq_true, true_and, List.filterMap_cons, List.filterMap_nil, show (SpiderLegEnd.outward ≠ SpiderLegEnd.free) = True from by decide, show (SpiderLegEnd.inward ≠ SpiderLegEnd.outward) = True from by decide, show (SpiderLegEnd.outward ≠ SpiderLegEnd.outward) = False from by decide, and_true, if_false, if_true, hr, spider_rho] rw [show r - r = 0 by omega, hg]
The flatMap of leg 1 over all shifted intermediate indices equals the flatMap over List.range (r - 2) using the intermediate cut formula.
Using List.flatMap_map, the map of +1 is composed into the flatMap. Applying List.flatMap_congr with List.mem_range allows rewriting each term pointwise using spider_blocked_incoming_one_outward_options_eq_leg1_mid.
uses
List.flatMap_map,List.flatMap_congr,List.mem_range,spider_blocked_incoming_one_outward_options_eq_leg1_midrw [List.flatMap_map] apply List.flatMap_congr intro idx hidx rw [List.mem_range] at hidx exact spider_blocked_incoming_one_outward_options_eq_leg1_mid r φ ih idx hidx
The options from leg 0 and all cuts on leg 1 concatenate to the explicit list of head options, intermediate cuts, and the final cut.
Rewriting leg 0 via spider_blocked_incoming_one_outward_options_eq_leg0_head yields [r]. Splitting List.range r via spider_blocked_incoming_one_outward_options_eq_range_split and distributing flatMap over list concatenation (List.flatMap_append, List.flatMap_cons, List.flatMap_nil) substitutes the evaluations for the initial cut (leg1_zero), intermediate cuts (mid_all), and the final cut (leg1_last).
uses
spider_blocked_incoming_one_outward_options_eq_leg0_head,spider_blocked_incoming_one_outward_options_eq_range_split,List.flatMap_cons,List.flatMap_append,List.flatMap_nil,spider_blocked_incoming_one_outward_options_eq_leg1_zero,spider_blocked_incoming_one_outward_options_eq_mid_all,spider_blocked_incoming_one_outward_options_eq_leg1_last,List.append_nilrw [spider_blocked_incoming_one_outward_options_eq_leg0_head r φ hφ, spider_blocked_incoming_one_outward_options_eq_range_split r hr, List.flatMap_cons, List.flatMap_append, List.flatMap_cons, List.flatMap_nil, spider_blocked_incoming_one_outward_options_eq_leg1_zero r hr φ, spider_blocked_incoming_one_outward_options_eq_mid_all r φ ih, spider_blocked_incoming_one_outward_options_eq_leg1_last r hr φ hφ ih] simp only [List.append_nil] rfl
The raw options list generated by [(1, outward), (r, φ)] unfolds to the explicit list of head options, intermediate cuts, and the final cut.
The proof rewrites the raw options list into leg 0 and leg 1 via spider_blocked_incoming_one_outward_options_eq_split, and concludes by applying spider_blocked_incoming_one_outward_options_eq_main.
uses
spider_blocked_incoming_one_outward_options_eq_split,spider_blocked_incoming_one_outward_options_eq_mainrw [spider_blocked_incoming_one_outward_options_eq_split r φ] exact spider_blocked_incoming_one_outward_options_eq_main r hr φ hφ ih
List.zipIdx- Pairs each element of a list with its zero-based index.
List.flatMap_cons- FlatMapping a function over a non-empty list x :: xs yields f(x) appended to the flatMap of xs.
List.flatMap_nil- FlatMapping a function over the empty list yields the empty list.
List.append_nil- Appending the empty list to any list yields the original list.
List.eraseIdx_cons_zero- Erasing index 0 of a :: as leaves as.
List.eraseIdx_cons_succ- Erasing index i + 1 of a :: as leaves a :: eraseIdx i as.
List.range_succ- The range of n + 1 equals the range of n followed by [n].
List.map_append- Mapping a function over the concatenation of two lists equals the concatenation of the mapped lists.
List.cons_append- Prepending an element to the concatenation of two lists equals prepending it to the first list.
List.append_assoc- Concatenation of lists is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
spider_blocked_incoming_one_outward_options_eq_range_succ_two- The range of n + 2 decomposes into 0, the range of n shifted by +1, and n + 1.
spider_blocked_incoming_one_outward_options_eq_leg0- The definition of the options list generated by cuts on the first leg [(1, outward)].
List.range_one- The range of 1 is the singleton list [0].
spider_blocked_incoming_one_outward_options_eq_leg1- The definition of the options list generated by cutting the second leg (r, φ) at cut length j_zero + 1.
Bool.eq_false_iff- A boolean value is false if and only if it is not true.
beq_iff_eq- Boolean equality a == b is true if and only if a = b.
spider_gamma_fuel_independent- The game value function γ is fuel-independent once fuel exceeds the sum of leg lengths plus 1.
spider_gamma_swap_two- The game value γ of a two-leg position is invariant under swapping the two legs.
List.flatMap_map- FlatMapping a function g over List.map f l equals flatMapping g ∘ f directly over l.
List.flatMap_congr- Two flatMaps over the same list are equal if the functions agree on every element of the list.
List.mem_range- A natural number m belongs to List.range n if and only if m < n.
spider_blocked_incoming_one_outward_options_eq_leg1_mid- For idx < r - 2, the cut of length idx + 2 on leg 1 produces two options XOR-summed with (idx + 1) ^^^ 1, under the induction hypothesis.
spider_blocked_incoming_one_outward_options_eq_leg0_head- The options generated by cutting leg 0 in state [(1, outward), (r, φ)] evaluate to [r] when φ ≠ free.
spider_blocked_incoming_one_outward_options_eq_range_split- For r ≥ 2, List.range r decomposes into 0, the shifted range of r - 2, and r - 1.
List.flatMap_append- FlatMapping a function over the concatenation of two lists equals the concatenation of the flatMaps.
spider_blocked_incoming_one_outward_options_eq_leg1_zero- Cutting length 1 from leg 1 produces the options ρ(r - 1, inward, φ) ^^^ 1 and ρ(r - 1, outward, φ) ^^^ 1.
spider_blocked_incoming_one_outward_options_eq_mid_all- The flatMap of leg 1 options over all shifted intermediate indices equals the flatMap over List.range (r - 2).
spider_blocked_incoming_one_outward_options_eq_leg1_last- The final cut of length r on leg 1 produces the single option ρ(0, φ, φ) ^^^ ((r - 1) ^^^ 1), under the induction hypothesis.
spider_blocked_incoming_one_outward_options_eq_split- The raw options generated across both legs decompose into leg 0 options appended to leg 1 options flatMapped over range r.
spider_blocked_incoming_one_outward_options_eq_main- The concatenated leg 0 and leg 1 options simplify under the induction hypothesis to the head options, intermediate cuts, and final cut.
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.
def spider_blocked_incoming_one_outward_options_eq_leg1 (r : ℕ) (φ : SpiderLegEnd) (j_zero : ℕ) : List ℕ := let j := j_zero + 1 [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta => if j == r ∧ φ ≠ SpiderLegEnd.free ∧ delta ≠ φ then none else let d := spider_rho (r - j) delta φ if j ≥ 2 then let new_L := (j - 1, delta) :: [(1, SpiderLegEnd.outward)] some (d ^^^ spider_gamma (r + 1) CentreStatus.incoming new_L) else let new_s := spider_update_centre CentreStatus.incoming delta some (d ^^^ spider_gamma (r + 1) new_s [(1, SpiderLegEnd.outward)]))def spider_blocked_incoming_one_outward_options_eq_leg0 (r : ℕ) (φ : SpiderLegEnd) : List ℕ := (List.range 1).flatMap (fun j_zero => let j := j_zero + 1 [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta => if j == 1 ∧ SpiderLegEnd.outward ≠ SpiderLegEnd.free ∧ delta ≠ SpiderLegEnd.outward then none else let d := spider_rho (1 - j) delta SpiderLegEnd.outward if j ≥ 2 then let new_L := (j - 1, delta) :: [(r, φ)] some (d ^^^ spider_gamma (r + 1) CentreStatus.incoming new_L) else let new_s := spider_update_centre CentreStatus.incoming delta some (d ^^^ spider_gamma (r + 1) new_s [(r, φ)])))lemma spider_blocked_incoming_one_outward_options_eq_split (r : ℕ) (φ : SpiderLegEnd) : ([(1, SpiderLegEnd.outward), (r, φ)].zipIdx.flatMap (fun ⟨⟨h, phi⟩, idx⟩ => let rest := [(1, SpiderLegEnd.outward), (r, φ)].eraseIdx idx (List.range h).flatMap (fun j_zero => let j := j_zero + 1 [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta => if j == h ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then none else let d := spider_rho (h - j) delta phi if j ≥ 2 then let new_L := (j - 1, delta) :: rest some (d ^^^ spider_gamma (r + 1) CentreStatus.incoming new_L) else let new_s := spider_update_centre CentreStatus.incoming delta some (d ^^^ spider_gamma (r + 1) new_s rest) ) ) )) = spider_blocked_incoming_one_outward_options_eq_leg0 r φ ++ (List.range r).flatMap (spider_blocked_incoming_one_outward_options_eq_leg1 r φ) := by rw [show ([(1, SpiderLegEnd.outward), (r, φ)] : List (ℕ × SpiderLegEnd)).zipIdx = [((1, SpiderLegEnd.outward), 0), ((r, φ), 1)] from by simp [List.zipIdx]] simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil, List.eraseIdx_cons_zero, List.eraseIdx_cons_succ] rfllemma spider_blocked_incoming_one_outward_options_eq_range_succ_two (n : ℕ) : List.range (n+2) = 0 :: (List.map (·+1) (List.range n) ++ [n+1]) := by induction n with | zero => rfl | succ k ih => rw [show k + 1 + 2 = (k + 2) + 1 by ring, List.range_succ, ih] rw [show k + 1 + 1 = k + 2 by ring] rw [List.range_succ (n:=k), List.map_append] simp [List.cons_append, List.append_assoc]lemma spider_blocked_incoming_one_outward_options_eq_range_split (r : ℕ) (hr : 2 ≤ r) : List.range r = 0 :: (List.map (·+1) (List.range (r-2)) ++ [r-1]) := by conv => lhs; rw [show r = (r-2)+2 by omega] rw [spider_blocked_incoming_one_outward_options_eq_range_succ_two] rw [show r - 2 + 1 = r - 1 by omega]lemma spider_blocked_incoming_one_outward_options_eq_leg0_head (r : ℕ) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : spider_blocked_incoming_one_outward_options_eq_leg0 r φ = [r] := by have hg : spider_gamma (r + 1) CentreStatus.free [(r, φ)] = r := by rcases φ with _ | _ | _ · exact absurd rfl hφ · simp only [spider_gamma]; simp [spider_rho_star] · simp only [spider_gamma]; simp [spider_rho_star] unfold spider_blocked_incoming_one_outward_options_eq_leg0 simp only [List.range_one, List.flatMap_cons, List.flatMap_nil, List.filterMap_cons, List.filterMap_nil, List.append_nil] simp only [spider_rho, spider_update_centre] rw [hg] simplemma spider_blocked_incoming_one_outward_options_eq_leg1_zero (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) : spider_blocked_incoming_one_outward_options_eq_leg1 r φ 0 = [spider_rho (r-1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r-1) SpiderLegEnd.outward φ ^^^ 1] := by have h1r : (1 == r) = false := by rw [Bool.eq_false_iff]; simp [beq_iff_eq]; omega have h1g : ¬ (1 ≥ 2) := by omega unfold spider_blocked_incoming_one_outward_options_eq_leg1 simp only [Nat.zero_add, h1r, Bool.false_eq_true, false_and, if_false, h1g, if_false] simp only [List.filterMap_cons, List.filterMap_nil, spider_update_centre] rw [show spider_gamma (r+1) CentreStatus.incoming [(1, SpiderLegEnd.outward)] = 1 from by simp only [spider_gamma]; simp [spider_rho]] rw [show spider_gamma (r+1) CentreStatus.free [(1, SpiderLegEnd.outward)] = 1 from by simp only [spider_gamma]; simp [spider_rho_star]]lemma spider_blocked_incoming_one_outward_options_eq_leg1_mid (r : ℕ) (φ : SpiderLegEnd) (ih : ∀ r' < r, 1 ≤ r' → ∀ φ' ≠ SpiderLegEnd.free, spider_gamma (r' + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r', φ')] = r' ^^^ 1) (idx : ℕ) (hidx : idx < r - 2) : spider_blocked_incoming_one_outward_options_eq_leg1 r φ (idx+1) = [spider_rho (r - 1 - (idx+1)) SpiderLegEnd.inward φ ^^^ ((idx+1) ^^^ 1), spider_rho (r - 1 - (idx+1)) SpiderLegEnd.outward φ ^^^ ((idx+1) ^^^ 1)] := by have hmid : ∀ (j : ℕ) (δ : SpiderLegEnd), δ ≠ SpiderLegEnd.free → 2 ≤ j → j ≤ r → spider_gamma (r+1) CentreStatus.incoming [(j-1, δ), (1, SpiderLegEnd.outward)] = (j-1) ^^^ 1 := by intro j δ hδ h2 hjr have hsum : ((([(j-1, δ), (1, SpiderLegEnd.outward)]).map Prod.fst).sum) + 1 = j + 1 := by simp; omega rw [spider_gamma_fuel_independent (r+1) CentreStatus.incoming _ (by omega)] rw [hsum] rw [spider_gamma_swap_two] have := ih (j-1) (by omega) (by omega) δ hδ rw [show (j-1)+2 = j+1 by omega] at this exact this unfold spider_blocked_incoming_one_outward_options_eq_leg1 rw [show idx + 1 + 1 = idx + 2 by omega] have hjr : (idx + 2 == r) = false := by rw [Bool.eq_false_iff]; simp [beq_iff_eq]; omega have hj2 : 2 ≤ idx + 2 := by omega simp only [hjr, Bool.false_eq_true, false_and, if_false, hj2, if_pos] simp only [List.filterMap_cons, List.filterMap_nil] rw [show r - (idx + 2) = r - 1 - (idx + 1) by omega] rw [hmid (idx+2) SpiderLegEnd.inward (by decide) hj2 (by omega)] rw [hmid (idx+2) SpiderLegEnd.outward (by decide) hj2 (by omega)] simp only [show idx + 2 - 1 = idx + 1 by omega]lemma spider_blocked_incoming_one_outward_options_eq_leg1_last (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) (ih : ∀ r' < r, 1 ≤ r' → ∀ φ' ≠ SpiderLegEnd.free, spider_gamma (r' + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r', φ')] = r' ^^^ 1) : spider_blocked_incoming_one_outward_options_eq_leg1 r φ (r-1) = [spider_rho 0 φ φ ^^^ ((r-1)^^^1)] := by have hg : spider_gamma (r+1) CentreStatus.incoming [(r-1,φ),(1, SpiderLegEnd.outward)] = (r-1)^^^1 := by rw [spider_gamma_swap_two] have := ih (r-1) (by omega) (by omega) φ hφ rw [show (r-1)+2 = r+1 by omega] at this exact this rcases φ with _ | _ | _ · exact absurd rfl hφ · unfold spider_blocked_incoming_one_outward_options_eq_leg1 rw [show r - 1 + 1 = r by omega] simp only [beq_self_eq_true, true_and, List.filterMap_cons, List.filterMap_nil, show (SpiderLegEnd.inward ≠ SpiderLegEnd.free) = True from by decide, show (SpiderLegEnd.inward ≠ SpiderLegEnd.inward) = False from by decide, show (SpiderLegEnd.outward ≠ SpiderLegEnd.inward) = True from by decide, and_true, if_false, if_true, hr, spider_rho] rw [show r - r = 0 by omega, hg] · unfold spider_blocked_incoming_one_outward_options_eq_leg1 rw [show r - 1 + 1 = r by omega] simp only [beq_self_eq_true, true_and, List.filterMap_cons, List.filterMap_nil, show (SpiderLegEnd.outward ≠ SpiderLegEnd.free) = True from by decide, show (SpiderLegEnd.inward ≠ SpiderLegEnd.outward) = True from by decide, show (SpiderLegEnd.outward ≠ SpiderLegEnd.outward) = False from by decide, and_true, if_false, if_true, hr, spider_rho] rw [show r - r = 0 by omega, hg]lemma spider_blocked_incoming_one_outward_options_eq_mid_all (r : ℕ) (φ : SpiderLegEnd) (ih : ∀ r' < r, 1 ≤ r' → ∀ φ' ≠ SpiderLegEnd.free, spider_gamma (r' + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r', φ')] = r' ^^^ 1) : (List.map (·+1) (List.range (r-2))).flatMap (spider_blocked_incoming_one_outward_options_eq_leg1 r φ) = (List.range (r - 2)).flatMap (fun idx => let i := idx + 1 [spider_rho (r - 1 - i) SpiderLegEnd.inward φ ^^^ (i ^^^ 1), spider_rho (r - 1 - i) SpiderLegEnd.outward φ ^^^ (i ^^^ 1)]) := by rw [List.flatMap_map] apply List.flatMap_congr intro idx hidx rw [List.mem_range] at hidx exact spider_blocked_incoming_one_outward_options_eq_leg1_mid r φ ih idx hidxlemma spider_blocked_incoming_one_outward_options_eq_main (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) (ih : ∀ r' < r, 1 ≤ r' → ∀ φ' ≠ SpiderLegEnd.free, spider_gamma (r' + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r', φ')] = r' ^^^ 1) : spider_blocked_incoming_one_outward_options_eq_leg0 r φ ++ (List.range r).flatMap (spider_blocked_incoming_one_outward_options_eq_leg1 r φ) = ([r, spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ 1] ++ (List.range (r - 2)).flatMap (fun idx => let i := idx + 1 [spider_rho (r - 1 - i) SpiderLegEnd.inward φ ^^^ (i ^^^ 1), spider_rho (r - 1 - i) SpiderLegEnd.outward φ ^^^ (i ^^^ 1)]) ++ [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)]) := by rw [spider_blocked_incoming_one_outward_options_eq_leg0_head r φ hφ, spider_blocked_incoming_one_outward_options_eq_range_split r hr, List.flatMap_cons, List.flatMap_append, List.flatMap_cons, List.flatMap_nil, spider_blocked_incoming_one_outward_options_eq_leg1_zero r hr φ, spider_blocked_incoming_one_outward_options_eq_mid_all r φ ih, spider_blocked_incoming_one_outward_options_eq_leg1_last r hr φ hφ ih] simp only [List.append_nil] rfl/-- For r ≥ 2, the options list generated by [(1, outward), (r, φ)] at fuel r + 2 with centre status incoming simplifies under the induction hypothesis to the explicit list of head options, intermediate cuts, and the final cut. -/theorem spider_blocked_incoming_one_outward_options_eq (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) (ih : ∀ r' < r, 1 ≤ r' → ∀ φ' ≠ SpiderLegEnd.free, spider_gamma (r' + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r', φ')] = r' ^^^ 1) : ([(1, SpiderLegEnd.outward), (r, φ)].zipIdx.flatMap (fun ⟨⟨h, phi⟩, idx⟩ => let rest := [(1, SpiderLegEnd.outward), (r, φ)].eraseIdx idx (List.range h).flatMap (fun j_zero => let j := j_zero + 1 [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta => if j == h ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then none else let d := spider_rho (h - j) delta phi if j ≥ 2 then let new_L := (j - 1, delta) :: rest some (d ^^^ spider_gamma (r + 1) CentreStatus.incoming new_L) else let new_s := spider_update_centre CentreStatus.incoming delta some (d ^^^ spider_gamma (r + 1) new_s rest) ) ) )) = ([r, spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ 1] ++ (List.range (r - 2)).flatMap (fun idx => let i := idx + 1 [spider_rho (r - 1 - i) SpiderLegEnd.inward φ ^^^ (i ^^^ 1), spider_rho (r - 1 - i) SpiderLegEnd.outward φ ^^^ (i ^^^ 1)]) ++ [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)]) := by rw [spider_blocked_incoming_one_outward_options_eq_split r φ] exact spider_blocked_incoming_one_outward_options_eq_main r hr φ hφ ih