AFTD Auto-Formalizing Theoretical Domains

spider_mex_one_two

theoremverified

The mex of the explicit closed-form option list of S(1,2,z) (8 head values plus the long block, after substituting all closed forms) equals (z+1) % 2, for z ≥ 1.

Statement

theorem spider_mex_one_two (z : ℕ) (hz : 1 ≤ z) :
    nat_mex_list
      ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),
        z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++
       (List.range (z-1)).flatMap (fun i =>
          [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]))
      = (z+1) % 2
Source
step towards spider_grundy_val_one_two
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • nat_mex_list_eq_zeroIf a list of naturals does not contain 0, then its mex (minimum excluded value) is 0.
  • nat_mex_list_eq_oneIf a list of naturals contains 0 but not 1, then its mex is 1.
  • nat_mex_list_not_mem_and_ltFor a list l of naturals, nat_mex_list l is not a member of l, and every natural number below nat_mex_list l is a member of l.
  • nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.

The proof, explained

The theorem is proved by case analysis on the parity of z. Since the minimum excluded value (mex) of a list of natural numbers is 1 if 0 is present and 1 is absent, and 0 if 0 is absent, it suffices to test membership of 0 and 1. When z is even, 1 ^^^ 1 = 0 appears in the list while every XOR term combines numbers of the same parity and thus cannot equal 1, making the mex 1. When z is odd, all head terms are nonzero and every XOR term combines numbers of opposite parity and thus cannot equal 0, making the mex 0.

  1. If the sum a + b is odd, then the bitwise XOR a ^^^ b is nonzero.

    Assume for contradiction that a ^^^ b = 0. By Nat.xor_mod_two_eq, the parity of a ^^^ b matches the parity of a + b. Rewriting with the assumption that a + b is odd and a ^^^ b = 0 yields 0 % 2 = 1 (i.e., 0 = 1), contradicting Nat.zero_ne_one.

    lines 3–6

    uses Nat.xor_mod_two_eq, Nat.zero_ne_one

      intro h0
      have hx := Nat.xor_mod_two_eq (m := a) (n := b)
      rw [h0, h] at hx
      exact Nat.zero_ne_one hx
  2. If the sum a + b is even, then the bitwise XOR a ^^^ b cannot equal 1.

    Assume for contradiction that a ^^^ b = 1. By Nat.xor_mod_two_eq, the parity of a ^^^ b equals the parity of a + b. Rewriting with a ^^^ b = 1 and (a + b) % 2 = 0 yields 1 % 2 = 0, which is an immediate arithmetic contradiction.

    lines 10–13

    uses Nat.xor_mod_two_eq

      intro h1
      have hx := Nat.xor_mod_two_eq (m := a) (n := b)
      rw [h1, h] at hx
      exact absurd hx (by decide)
  3. The proof reduces to two cases based on whether z is even or odd.

    We split into the cases z % 2 = 0 and z % 2 = 1 using Nat.mod_two_eq_zero_or_one.

    line 23

    uses Nat.mod_two_eq_zero_or_one

      rcases Nat.mod_two_eq_zero_or_one z with h | h
  4. When z is even, 0 is an element of the option list.

    When z % 2 = 0, the head entry 1 ^^^ (1 - z % 2) simplifies to 1 ^^^ 1 = 0, so 0 is present in the list.

    lines 24–28

      · have h0 : 0 ∈ ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),
            z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++
           (List.range (z-1)).flatMap (fun i =>
              [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]) : List ℕ) := by
          simp [h]
  5. When z is even, 1 is not an element of the option list.

    Simplifying with z % 2 = 0 reduces non-membership of 1 to three conditions: (1) z - 2 ≠ 1, which holds because z ≥ 1 and z is even implies z ≥ 2 and z ≠ 3; (2) (z - 1) ^^^ 1 ≠ 1, which follows from spider_mex_one_two_xor_ne_one_of_sum_even because the operands sum to z, which is even; and (3) (z - (x + 2)) ^^^ ((x + 1) ^^^ 1) ≠ 1 for all x < z - 1, which also follows from spider_mex_one_two_xor_ne_one_of_sum_even because ((x + 1) ^^^ 1) % 2 = (x + 2) % 2 by Nat.xor_mod_two_eq, making the sum of the two operands congruent modulo 2 to (z - (x + 2)) + (x + 2) = z, which is even.

    lines 29–40

    uses spider_mex_one_two_xor_ne_one_of_sum_even, Nat.xor_mod_two_eq

        have h1 : 1 ∉ ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),
            z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++
           (List.range (z-1)).flatMap (fun i =>
              [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]) : List ℕ) := by
          simp [h]
          refine ⟨?_, ?_, ?_⟩
          · omega
          · intro hh
            exact spider_mex_one_two_xor_ne_one_of_sum_even _ _ (by omega) hh.symm
          · intro x hx hh
            have hpar : ((x+1) ^^^ 1) % 2 = (x+2) % 2 := by rw [Nat.xor_mod_two_eq]
            exact spider_mex_one_two_xor_ne_one_of_sum_even _ _ (by omega) hh.symm
  6. When z is even, the mex of the option list is (z + 1) % 2.

    Since 0 is in the list and 1 is not, nat_mex_list_eq_one establishes that the mex is 1. Because z is even, (z + 1) % 2 = 1 as well.

    lines 41–42

    uses nat_mex_list_eq_one

        rw [nat_mex_list_eq_one _ h0 h1]
        omega
  7. When z is odd, 0 is not an element of the option list.

    Simplifying with z % 2 = 1 reduces non-membership of 0 to three conditions: (1) z ≠ 0, which holds because z ≥ 1; (2) (z - 1) ^^^ 1 ≠ 0, which holds by spider_mex_one_two_xor_ne_zero_of_sum_odd because the sum of the operands is z, which is odd; and (3) (z - (x + 2)) ^^^ ((x + 1) ^^^ 1) ≠ 0 for all x < z - 1, which holds by spider_mex_one_two_xor_ne_zero_of_sum_odd because ((x + 1) ^^^ 1) % 2 = (x + 2) % 2 by Nat.xor_mod_two_eq, so the sum of the operands has the same parity as z, which is odd.

    lines 43–54

    uses spider_mex_one_two_xor_ne_zero_of_sum_odd, Nat.xor_mod_two_eq

      · have h0 : 0 ∉ ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),
            z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++
           (List.range (z-1)).flatMap (fun i =>
              [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]) : List ℕ) := by
          simp [h]
          refine ⟨?_, ?_, ?_⟩
          · omega
          · intro hh
            exact spider_mex_one_two_xor_ne_zero_of_sum_odd _ _ (by omega) hh.symm
          · intro x hx hh
            have hpar : ((x+1) ^^^ 1) % 2 = (x+2) % 2 := by rw [Nat.xor_mod_two_eq]
            exact spider_mex_one_two_xor_ne_zero_of_sum_odd _ _ (by omega) hh.symm
  8. When z is odd, the mex of the option list is (z + 1) % 2.

    Since 0 is not in the list, nat_mex_list_eq_zero establishes that the mex is 0. Because z is odd, (z + 1) % 2 = 0 as well.

    lines 55–56

    uses nat_mex_list_eq_zero

        rw [nat_mex_list_eq_zero _ h0]
        omega
Nat.xor_mod_two_eq
The bitwise XOR of two natural numbers has the same parity (remainder modulo 2) as their sum.
Nat.zero_ne_one
0 is not equal to 1.
Nat.mod_two_eq_zero_or_one
Every natural number modulo 2 is equal to either 0 or 1.
spider_mex_one_two_xor_ne_one_of_sum_even
If the sum of two natural numbers is even, their bitwise XOR is not equal to 1.
spider_mex_one_two_xor_ne_zero_of_sum_odd
If the sum of two natural numbers is odd, their bitwise XOR is not equal to 0.
nat_mex_list_eq_one
If a list of natural numbers contains 0 and does not contain 1, its minimum excluded value is 1.
nat_mex_list_eq_zero
If a list of natural numbers does not contain 0, its minimum excluded value is 0.

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 spider_mex_one_two_xor_ne_zero_of_sum_odd (a b : ℕ) (h : (a + b) % 2 = 1) :    a ^^^ b ≠ 0 := by  intro h0  have hx := Nat.xor_mod_two_eq (m := a) (n := b)  rw [h0, h] at hx  exact Nat.zero_ne_one hxlemma spider_mex_one_two_xor_ne_one_of_sum_even (a b : ℕ) (h : (a + b) % 2 = 0) :    a ^^^ b ≠ 1 := by  intro h1  have hx := Nat.xor_mod_two_eq (m := a) (n := b)  rw [h1, h] at hx  exact absurd hx (by decide)/-- Mex of the substituted root option list equals (z+1)%2. -/theorem spider_mex_one_two (z : ℕ) (hz : 1 ≤ z) :    nat_mex_list      ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),        z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++       (List.range (z-1)).flatMap (fun i =>          [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]))      = (z+1) % 2 := by  rcases Nat.mod_two_eq_zero_or_one z with h | h  · have h0 : 0 ∈ ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),        z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++       (List.range (z-1)).flatMap (fun i =>          [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]) : List ℕ) := by      simp [h]    have h1 : 1 ∉ ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),        z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++       (List.range (z-1)).flatMap (fun i =>          [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]) : List ℕ) := by      simp [h]      refine ⟨?_, ?_, ?_⟩      · omega      · intro hh        exact spider_mex_one_two_xor_ne_one_of_sum_even _ _ (by omega) hh.symm      · intro x hx hh        have hpar : ((x+1) ^^^ 1) % 2 = (x+2) % 2 := by rw [Nat.xor_mod_two_eq]        exact spider_mex_one_two_xor_ne_one_of_sum_even _ _ (by omega) hh.symm    rw [nat_mex_list_eq_one _ h0 h1]    omega  · have h0 : 0 ∉ ([z - 2*(1 - z%2), z - 2*(1 - z%2), 1 ^^^ (1 - z%2), 1 ^^^ (1 - z%2),        z - 2*(1 - z%2), z - 2*(1 - z%2), (z-1) ^^^ 1, (z-1) ^^^ 1] ++       (List.range (z-1)).flatMap (fun i =>          [(z - (i+2)) ^^^ ((i+1) ^^^ 1), (z - (i+2)) ^^^ ((i+1) ^^^ 1)]) : List ℕ) := by      simp [h]      refine ⟨?_, ?_, ?_⟩      · omega      · intro hh        exact spider_mex_one_two_xor_ne_zero_of_sum_odd _ _ (by omega) hh.symm      · intro x hx hh        have hpar : ((x+1) ^^^ 1) % 2 = (x+2) % 2 := by rw [Nat.xor_mod_two_eq]        exact spider_mex_one_two_xor_ne_zero_of_sum_odd _ _ (by omega) hh.symm    rw [nat_mex_list_eq_zero _ h0]    omega
See it in the graphDiscuss this resultChallenge it