AFTD Auto-Formalizing Theoretical Domains

sages_row_pair_protocol

def

Every sage in a row announces the unordered pair consisting of themselves together with their right neighbour; the rightmost sage, who has no right neighbour, announces the pair with their left neighbour.

Statement

def sages_row_pair_protocol {S : ℕ} (hS : 2 ≤ S) (v : RowLocalView (Fin S)) : {s : Finset (Fin S) // s.card = 2}
Source
step towards sages_row_upper_bound_binomial
Verified
29 Oct 2026
Axioms
none listed
Built on 2
  • sages_row_other_thanFor S ≥ 2 sages, a canonical sage other than a given sage x: seat 1 if x occupies seat 0, and seat 0 otherwise.
  • 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…
Used by 1
  • 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.

Lean source view module on GitHub

/-- Every sage announces the pair consisting of themselves and their right neighbour, or their left neighbour if they have no right neighbour (the rightmost sage), falling back to a canonical partner on neighbourless views. -/
def sages_row_pair_protocol {S : ℕ} (hS : 2 ≤ S) (v : RowLocalView (Fin S)) : {s : Finset (Fin S) // s.card = 2} := let x := v.1
   let y := match v.2.2, v.2.1 with
     | some y, _ => y
     | none, some y => y
     | none, none => sages_row_other_than hS x
   if hy : y = x then
     ⟨{x, sages_row_other_than hS x}, by
       apply Finset.card_pair
       intro h
       have hv : (sages_row_other_than hS x).val = x.val := congrArg Fin.val h.symm
       simp only [sages_row_other_than] at hv
       split_ifs at hv with h0 <;> omega⟩
   else
     ⟨{x, y}, Finset.card_pair (Ne.symm hy)⟩
See it in the graphDiscuss this resultChallenge it