two_agent_alternating_schedule_is_balanced
For every number of goods m : ℕ, the alternating drafting schedule two_agent_alternating_schedule m of length m is a balanced schedule for two agents.
Statement
theorem two_agent_alternating_schedule_is_balanced (m : ℕ) :
is_balanced_schedule 2 m (two_agent_alternating_schedule m)- Source
- arXiv:2611.09685
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- two_agent_alternating_scheduleGiven the number of goods m : ℕ, the alternating drafting schedule of length m is the function from Fin m to Fin 2 sending each turn t :…
- is_balanced_scheduleA picking sequence of m turns among n agents is balanced if each complete block of n turns contains each agent exactly once, and the…
Read back from the Lean
For every natural number $m$, the two-agent alternating schedule of length $m$ (which assigns round $t$ to agent $t \bmod 2$) is a balanced schedule for 2 agents and $m$ rounds.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
A drafting schedule for two agents is balanced if each full round of two items gives every agent one item, and the final partial round does not assign any agent more than one item. Unfolding the definitions reduces the theorem to showing that the assignment $t \mapsto t \bmod 2$ is injective on every block of size 2 and on the final block of size $m \bmod 2$. In both cases, the items within a block have distinct remainders modulo 2, so injectivity follows immediately by modular arithmetic.
To show the schedule is balanced, it suffices to prove that the agent assignment is injective on each full round of two items and on the final partial round.
Unfolding the definitions of a balanced schedule and the two-agent alternating schedule reveals two requirements: for each complete round $b$ satisfying $(b + 1) \cdot 2 \le m$, the assignment $j \mapsto (2b + j) \bmod 2$ must be injective on $\text{Fin } 2$; and on the remaining partial round of length $m \bmod 2$, the map $j \mapsto (2\lfloor m/2 \rfloor + j) \bmod 2$ must be injective on $\text{Fin }(m \bmod 2)$. The goal splits into these two independent subgoals.
dsimp [is_balanced_schedule, two_agent_alternating_schedule] constructor
The schedule is injective on every complete round of two items.
Consider an arbitrary round $b$ and two round positions $j_1, j_2 \in \text{Fin } 2$ assigned to the same agent. Applying `Fin.val` to both sides via `congr_arg` gives the equality of underlying values: $(2b + j_1) \bmod 2 = (2b + j_2) \bmod 2$. By extensionality (`ext`), equality in $\text{Fin } 2$ reduces to equality of natural numbers $j_1 = j_2$. Since both $j_1, j_2 < 2$, adding a multiple of $2$ does not change the remainder modulo $2$, so $(2b + j) \bmod 2 = j$; linear integer arithmetic (`omega`) finishes the step.
uses
congr_arg,Fin.val· intro b hb j1 j2 h have hval := congr_arg Fin.val h dsimp at hval ext omega
The schedule is injective on the remaining partial round.
Suppose two positions $j_1, j_2 \in \text{Fin }(m \bmod 2)$ in the leftover partial round are assigned to the same agent. Applying `Fin.val` using `congr_arg` yields $(2\lfloor m/2 \rfloor + j_1) \bmod 2 = (2\lfloor m/2 \rfloor + j_2) \bmod 2$. Extensionality (`ext`) reduces the equality in $\text{Fin }(m \bmod 2)$ to $j_1 = j_2$ in $\mathbb{N}$. Since $j_1, j_2 < m \bmod 2 \le 1$, the offset $2\lfloor m/2 \rfloor$ cancels modulo $2$, and linear integer arithmetic (`omega`) closes the goal.
uses
congr_arg,Fin.val· intro j1 j2 h have hval := congr_arg Fin.val h dsimp at hval ext omega
congr_arg- If two arguments are equal, applying any function to both preserves equality ($a_1 = a_2 \implies f(a_1) = f(a_2)$).
Fin.val- The projection mapping an element of $\text{Fin } n$ to its underlying natural number in $\mathbb{N}$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The canonical two-agent alternating schedule of length m is a balanced schedule. -/theorem two_agent_alternating_schedule_is_balanced (m : ℕ) : is_balanced_schedule 2 m (two_agent_alternating_schedule m) := by dsimp [is_balanced_schedule, two_agent_alternating_schedule] constructor · intro b hb j1 j2 h have hval := congr_arg Fin.val h dsimp at hval ext omega · intro j1 j2 h have hval := congr_arg Fin.val h dsimp at hval ext omega