spider_mex_one_two
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.
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.
uses
Nat.xor_mod_two_eq,Nat.zero_ne_oneintro h0 have hx := Nat.xor_mod_two_eq (m := a) (n := b) rw [h0, h] at hx exact Nat.zero_ne_one hx
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.
uses
Nat.xor_mod_two_eqintro h1 have hx := Nat.xor_mod_two_eq (m := a) (n := b) rw [h1, h] at hx exact absurd hx (by decide)
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.
uses
Nat.mod_two_eq_zero_or_onercases Nat.mod_two_eq_zero_or_one z with h | h
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.
· 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]
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.
uses
spider_mex_one_two_xor_ne_one_of_sum_even,Nat.xor_mod_two_eqhave 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
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.
uses
nat_mex_list_eq_onerw [nat_mex_list_eq_one _ h0 h1] omega
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.
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
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.
uses
nat_mex_list_eq_zerorw [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
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 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