RowProblemSolvable
The anonymous-slip puzzle for S sages in a row with n symbols and unlabeled seats (with 2 ≤ S) is solvable if there exists a protocol p : RowLocalView (Fin S) → Fin n satisfying RowProtocolSolves S hS p.
Statement
def RowProblemSolvable (S n : ℕ) (hS : 2 ≤ S) : Prop
- Defined in
- arXiv:2610.33032:168
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 2
- RowLocalViewFor sages of type α, a local view in an unlabeled row consists of the sage's own identity together with an optional left neighbor and an…
- RowProtocolSolvesA protocol p : RowLocalView (Fin S) → α solves the anonymous-slip puzzle for S sages in a row with 2 ≤ S without seat labels if for every…
- Used by 3
- row_sages_5R3E_implies_5R4EIf five sages in a row with unlabeled seats can solve the anonymous-slip puzzle using three symbols (RowProblemSolvable 5 3 (by decide)),…
- row_solvable_monoIf the anonymous-slip puzzle for S sages in a row with unlabeled seats is solvable with n symbols (RowProblemSolvable S n hS), then it is…
- sages_row_upper_bound_binomialFor every integer S ≥ 3, the anonymous-slip puzzle for S sages in a row with unlabeled seats can be solved using Nat.choose S 2 symbols.
Read back from the Lean
Given natural numbers S and n, and a proof hS : 2 ≤ S, RowProblemSolvable S n hS asserts that there exists a function (protocol) p : RowLocalView (Fin S) → Fin n such that p solves the row problem in the following sense:
For every element (sage) x : Fin S and every pair of permutations π₁, π₂ : Equiv.Perm (Fin S):
1. If the local view of sage x under permutation π₁ equals the local view of sage x under permutation π₂ (where the local view of x under a permutation π consists of x itself, x's left neighbor in the line if not at position 0, and x's right neighbor in the line if not at position S - 1), and
2. If the multiset of protocol messages p produced across all positions i : Fin S under π₁ equals the multiset of protocol messages produced across all positions under π₂,
then π₁ = π₂.
In words: there exists an assignment of messages from Fin n to local views such that every sage, knowing their own identity and immediate neighbors, and observing the multiset of all announced messages, can uniquely determine the underlying permutation of the sages.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The anonymous-slip puzzle for `S` sages in a row with `n` symbols and unlabeled seats is solvable. -/ def RowProblemSolvable (S n : ℕ) (hS : 2 ≤ S) : Prop := ∃ p : RowLocalView (Fin S) → Fin n, RowProtocolSolves S hS p