AFTD Auto-Formalizing Theoretical Domains

spider_blocked_incoming_one_outward_options_eq

theoremverified

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

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.

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

    lines 50–54

    uses List.zipIdx, List.flatMap_cons, List.flatMap_nil, List.append_nil, List.eraseIdx_cons_zero, List.eraseIdx_cons_succ

      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]
      rfl
  2. 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.

    lines 58–64

    uses List.range_succ, List.map_append, List.cons_append, List.append_assoc

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

    lines 68–70

    uses spider_blocked_incoming_one_outward_options_eq_range_succ_two

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

    lines 75–85

    uses spider_blocked_incoming_one_outward_options_eq_leg0, List.range_one, List.flatMap_cons, List.flatMap_nil, List.append_nil

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

    lines 92–101

    uses spider_blocked_incoming_one_outward_options_eq_leg1, Bool.eq_false_iff, beq_iff_eq

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

    lines 110–120

    uses spider_gamma_fuel_independent, spider_gamma_swap_two

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

    lines 121–131

    uses spider_blocked_incoming_one_outward_options_eq_leg1, Bool.eq_false_iff, beq_iff_eq

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

    lines 139–144

    uses spider_gamma_swap_two

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

    lines 145–162

    uses spider_blocked_incoming_one_outward_options_eq_leg1

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

    lines 173–177

    uses List.flatMap_map, List.flatMap_congr, List.mem_range, spider_blocked_incoming_one_outward_options_eq_leg1_mid

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

    lines 192–199

    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_nil

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

    lines 228–229

    uses spider_blocked_incoming_one_outward_options_eq_split, spider_blocked_incoming_one_outward_options_eq_main

      rw [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

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