run_C_D_pair_values
For every integer h ≥ 1, the pair consisting of h mod 2 and the indicator of (h ≥ 2 and h is even) is either (0, 1) or (1, 0).
Statement
theorem run_C_D_pair_values (h : ℕ) (hh : 1 ≤ h) : (h % 2 = 0 ∧ (if h ≥ 2 ∧ Even h then 1 else 0) = 1) ∨ (h % 2 = 1 ∧ (if h ≥ 2 ∧ Even h then 1 else 0) = 0)
- Source
- scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md:445
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For every natural number $h$ satisfying $1 \le h$, either: 1. $h \pmod 2 = 0$ and the expression $(\text{if } h \ge 2 \land \mathrm{Even}(h) \text{ then } 1 \text{ else } 0)$ equals $1$; or 2. $h \pmod 2 = 1$ and the expression $(\text{if } h \ge 2 \land \mathrm{Even}(h) \text{ then } 1 \text{ else } 0)$ equals $0$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by case analysis on the parity of $h$. If $h$ is even, then $h \bmod 2 = 0$, and since $h \ge 1$, $h$ must be at least 2, making the condition $h \ge 2 \land \operatorname{Even}(h)$ hold and setting the indicator to 1. If $h$ is odd, then $h \bmod 2 = 1$, and since $h$ is not even, the condition fails and the indicator evaluates to 0.
It suffices to consider the cases where $h$ is even and where $h$ is not even.
We perform a case distinction on whether $h$ is even (`Even h`).
by_cases he : Even hWhen $h$ is even, the first disjunct applies, and $h \bmod 2 = 0$.
We choose the left alternative of the disjunction. The first conjunct requires $h \bmod 2 = 0$, which follows from the evenness of $h$ via `Nat.even_iff.mp`.
uses
Nat.even_iff.mp· left constructor · exact Nat.even_iff.mp he
When $h$ is even, the indicator evaluates to 1.
Because $h$ is even, $h = 2k$ for some natural number $k$. Since $h \ge 1$, linear arithmetic (`omega`) determines that $h \ge 2$. Both conditions $h \ge 2$ and $\operatorname{Even}(h)$ are therefore satisfied, so simplifying the conditional expression yields 1.
· have h2 : 2 ≤ h := by rcases he with ⟨k, hk⟩ omega simp [h2, he]
When $h$ is odd, the second disjunct applies, and $h \bmod 2 = 1$.
We choose the right alternative of the disjunction. Because $h$ is not even, it is odd by `Nat.not_even_iff_odd.mp`, and therefore $h \bmod 2 = 1$ by `Nat.odd_iff.mp`.
uses
Nat.not_even_iff_odd.mp,Nat.odd_iff.mp· right constructor · exact Nat.odd_iff.mp (Nat.not_even_iff_odd.mp he)
When $h$ is odd, the indicator evaluates to 0.
Because $h$ is not even, the conjunct $\operatorname{Even}(h)$ in the condition is false, so simplifying the conditional expression yields 0.
· simp [he]
Nat.even_iff.mp- An even natural number has remainder 0 modulo 2.
Nat.not_even_iff_odd.mp- A natural number that is not even is odd.
Nat.odd_iff.mp- An odd natural number has remainder 1 modulo 2.
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.
/-- For all h ≥ 1, the Grundy values C_h and D_h form the set {0, 1}. -/theorem run_C_D_pair_values (h : ℕ) (hh : 1 ≤ h) : (h % 2 = 0 ∧ (if h ≥ 2 ∧ Even h then 1 else 0) = 1) ∨ (h % 2 = 1 ∧ (if h ≥ 2 ∧ Even h then 1 else 0) = 0) := by by_cases he : Even h · left constructor · exact Nat.even_iff.mp he · have h2 : 2 ≤ h := by rcases he with ⟨k, hk⟩ omega simp [h2, he] · right constructor · exact Nat.odd_iff.mp (Nat.not_even_iff_odd.mp he) · simp [he]