AFTD Auto-Formalizing Theoretical Domains

run_C_D_pair_values

theoremverified

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.

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

    line 5

      by_cases he : Even h
  2. When $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`.

    lines 6–8

    uses Nat.even_iff.mp

      · left
        constructor
        · exact Nat.even_iff.mp he
  3. 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.

    lines 9–12

        · have h2 : 2 ≤ h := by
            rcases he with ⟨k, hk⟩
            omega
          simp [h2, he]
  4. 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`.

    lines 13–15

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

    line 16

        · 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

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