AFTD Auto-Formalizing Theoretical Domains

is_balanced_schedule

def

A picking sequence of m turns among n agents is balanced if each complete block of n turns contains each agent exactly once, and the remaining final block of m mod n turns contains no repeated agent.

Statement

def is_balanced_schedule (n m : ℕ) (s : Fin m → Fin n) : Prop
Defined in
arXiv:2611.09685
Verified
11 Nov 2026
Axioms
none listed
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2

Read back from the Lean

Given natural numbers $n$ and $m$ and a function $s : \text{Fin } m \to \text{Fin } n$, is_balanced_schedule n m s asserts the conjunction of two conditions: 1. For every natural number $b$ such that $(b + 1) \cdot n \le m$, the function mapping each $j \in \text{Fin } n$ to $s(b \cdot n + j)$ is injective (equivalently, a permutation of $\text{Fin } n$, meaning every value in $\text{Fin } n$ appears exactly once in the $b$-th full block of length $n$). 2. The function mapping each $j \in \text{Fin }(m \bmod n)$ to $s(n \cdot (m / n) + j)$ is injective (meaning all values in the final remainder block of length $m \bmod n$ are distinct).

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

/-- A picking sequence s : Fin m → Fin n is balanced if each complete block of n turns contains each agent once and the remaining final block has no repeats. -/
def is_balanced_schedule (n m : ℕ) (s : Fin m → Fin n) : Prop :=
  (∀ (b : ℕ) (hb : (b + 1) * n ≤ m),
    Function.Injective (fun (j : Fin n) =>
      have hj : b * n + j.val < m := by
        have : j.val < n := j.isLt
        nlinarith
      s ⟨b * n + j.val, hj⟩)) ∧
  (Function.Injective (fun (j : Fin (m % n)) =>
    have hj : n * (m / n) + j.val < m := by
      have : j.val < m % n := j.isLt
      have hdiv : n * (m / n) + m % n = m := Nat.div_add_mod m n
      omega
    s ⟨n * (m / n) + j.val, hj⟩))
See it in the graphDiscuss this resultChallenge it