Assignment moves, pass moves, and deviations
Lax689614.RegularPlay · concepts/Lax689614/RegularPlay.lean · lax-689614
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An assignment move is or with . A pass move is with , or . A regular position is reachable from the initial graph by such moves. Write and for the numbers of surviving and , respectively.
Claim 7: when is odd, , and , any other move loses unless it is and all literal vertices of clause are gone. Claim 8: at a regular position with , such an exceptional move wins exactly when is even.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax689614.Construction |
| 2 | import Lax689614.Grundy |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Assignment moves, pass moves, and deviations |
| 7 | type: theorem |
| 8 | --- |
| 9 | An assignment move is or with . A pass move is |
| 10 | with , or . A regular position is reachable |
| 11 | from the initial graph by such moves. Write and for the numbers |
| 12 | of surviving and , respectively. |
| 13 | |
| 14 | Claim 7: when is odd, , and , any other move |
| 15 | loses unless it is and all literal vertices of clause are gone. |
| 16 | Claim 8: at a regular position with , such an exceptional move |
| 17 | wins exactly when is even. |
| 18 | -/ |
| 19 | |
| 20 | namespace Lax689614.RegularPlay |
| 21 | |
| 22 | open PositiveCNF Construction ArcKayles |
| 23 | |
| 24 | def SameEdge (u w x z : ℕ) : Prop := (u = x ∧ w = z) ∨ (u = z ∧ w = x) |
| 25 | |
| 26 | def RegularMove (φ : Formula) (u w : ℕ) : Prop := |
| 27 | (∃ i < R φ, SameEdge u w (v φ i) (vt φ i)) ∨ |
| 28 | (∃ i < φ.nvars, SameEdge u w (v φ i) (f φ i)) ∨ |
| 29 | (∃ i < K φ, SameEdge u w (y φ i) (z φ i)) |
| 30 | |
| 31 | inductive Reachable (φ : Formula) : Finset ℕ → Prop |
| 32 | | initial : Reachable φ (board φ) |
| 33 | | step {S : Finset ℕ} {u w : ℕ} : Reachable φ S → |
| 34 | u ∈ S → w ∈ S → (graph φ).Adj u w → RegularMove φ u w → |
| 35 | Reachable φ (remove S u w) |
| 36 | |
| 37 | def remainingV (φ : Formula) (S : Finset ℕ) : ℕ := |
| 38 | ((Finset.range (R φ)).filter fun i => v φ i ∈ S).card |
| 39 | |
| 40 | def remainingY (φ : Formula) (S : Finset ℕ) : ℕ := |
| 41 | ((Finset.range (K φ)).filter fun i => y φ i ∈ S).card |
| 42 | |
| 43 | def Exhausted (φ : Formula) (S : Finset ℕ) (j : Fin φ.clauses.length) : Prop := |
| 44 | ∀ i ∈ φ.clauses[j], f φ i ∉ S |
| 45 | |
| 46 | def Exceptional (φ : Formula) (S : Finset ℕ) (u w : ℕ) : Prop := |
| 47 | ∃ j : Fin φ.clauses.length, SameEdge u w s (a φ j) ∧ Exhausted φ S j |
| 48 | |
| 49 | axiom deviation_loses (φ : Formula) (hm : φ.clauses.length % 2 = 1) |
| 50 | (S : Finset ℕ) (hS : Reachable φ S) |
| 51 | (hr : φ.clauses.length ≤ remainingV φ S) (hk : 1 ≤ remainingY φ S) |
| 52 | (u w : ℕ) (hu : u ∈ S) (hw : w ∈ S) (he : (graph φ).Adj u w) |
| 53 | (hn : ¬ RegularMove φ u w) (hx : ¬ Exceptional φ S u w) : |
| 54 | Winning (graph φ) (remove S u w) |
| 55 | |
| 56 | axiom exceptional_parity (φ : Formula) (hm : φ.clauses.length % 2 = 1) |
| 57 | (S : Finset ℕ) (hS : Reachable φ S) |
| 58 | (hr : φ.clauses.length ≤ remainingV φ S) |
| 59 | (j : Fin φ.clauses.length) (hj : Exhausted φ S j) : |
| 60 | ¬ Winning (graph φ) (remove S s (a φ j)) ↔ |
| 61 | (remainingV φ S + remainingY φ S) % 2 = 0 |
| 62 | |
| 63 | end Lax689614.RegularPlay |
| 64 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments