AFTD Auto-Formalizing Theoretical Domains

spr_opt_two_two

theoremverifiedoriginal

opt(2, 2) = 1: on two cells with two rounds, the labeler can keep at most one sign on the board.

Statement

theorem spr_opt_two_two : spr_opt 2 2 = 1
Related work
smallest nontrivial case of opt(n, n) for the sign-preservation-with-reuse game of arXiv:2610.07623 (Sec. 2.2); computed exhaustively
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • spr_optopt(n, t): the number of signs remaining at the end of the sign-preservation-with-reuse game with n cells and at most t rounds, under…
Used by 1
  • spr_opt_three_oneOn three cells with at most one round, the sign-preservation-with-reuse minimax value is one: spr_opt 3 1 = 1.

The proof, explained

The theorem asserts that on a board of two cells over two rounds, the optimal number of signs the labeler can secure is 1. Because the board size and round count are small and finite, Lean computes the minimax value directly through definitional reduction. The equality holds by reflexivity (`rfl`).

  1. spr_opt 2 2 = 1 automation

    The game is played on n = 2 cells over t = 2 rounds. In round 1, placing a sign on either cell leaves the other empty. In round 2, playing the remaining empty cell allows the adversary to erase the previously placed sign, so no strategy can achieve more than 1 sign on the board. Because the game tree is finite, Lean evaluates the recursive definition spr_value definitionally on all branches to 1, and the proof finishes by reflexivity (rfl).

    line 1

    theorem spr_opt_two_two : spr_opt 2 2 = 1 := rfl

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem spr_opt_two_two : spr_opt 2 2 = 1 := rfl
See it in the graphDiscuss this resultChallenge it