round_robin_sequence_count_eq
The number of times agent a appears in the Round-Robin sequence of n agents and m goods is (m + (n - 1 - a)) / n.
Statement
theorem round_robin_sequence_count_eq (n m : ℕ) [NeZero n] (a : Fin n) :
(round_robin_sequence n m).count a = (m + (n - 1 - a.val)) / n- Source
- step towards round_robin_alpha_three_eq_two_thirds
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
The proof, explained
The theorem is proved by induction on the number of goods $m$. The base case $m = 0$ is immediate since the sequence is empty and the integer division $(n - 1 - a) / n$ yields $0$. For the induction step from $m$ to $m + 1$, the sequence appends agent $m % n$, increasing agent $a$'s count by $1$ precisely when $m % n = a$. Correspondingly, by `Nat.succ_div`, the division formula increases by $1$ if and only if $n ∣ (m + (n - 1 - a) + 1)$; this divisibility is shown to be equivalent to $m % n = a$ because the remainder modulo $n$ lies strictly between $0$ and $2n$, where $n$ is the only multiple of $n$.
If $Y$ is a positive multiple of $n$ strictly less than $2n$, then $Y = n$.
Write $Y = n * k$ using the divisibility hypothesis. If $k ≥ 2$, then $2 * n ≤ n * k = Y$ by `Nat.mul_le_mul_left`, which contradicts $Y < 2 * n$. If $k ≤ 0$, then $k = 0$, giving $Y = 0$, contradicting $0 < Y$. Thus $0 < k < 2$, which forces $k = 1$ in $\mathbb{N}$, so $Y = n * 1 = n$.
uses
Nat.mul_le_mul_leftlemma round_robin_sequence_count_eq_dvd_eq_self {n Y : ℕ} (h1 : 0 < Y) (h2 : Y < 2 * n) (hdiv : n ∣ Y) : Y = n := by rcases hdiv with ⟨k, rfl⟩ have hk_lt : k < 2 := by by_contra! h have : 2 * n ≤ n * k := by calc 2 * n = n * 2 := by ring _ ≤ n * k := Nat.mul_le_mul_left n h omega have hk_pos : 0 < k := by by_contra! h have : k = 0 := by omega subst this simp at h1 have : k = 1 := by omega subst this simp
The quantity $m + (n - 1 - a) + 1$ decomposes into a multiple of $n$ plus a remainder term $Y$ that lies strictly between $0$ and $2n$.
Using the division theorem $m = n * (m / n) + m % n$ (`Nat.div_add_mod`), we rewrite $m + (n - 1 - a) + 1 = n * (m / n) + Y$, where $Y = m % n + (n - 1 - a) + 1$. Since $n ∣ n * (m / n)$ (`dvd_mul_right`), divisibility of the whole sum by $n$ reduces to $n ∣ Y$ (`Nat.dvd_add_right`). Since $m % n < n$ (`Nat.mod_lt`) and $a < n$, linear arithmetic establishes $0 < Y < 2 * n$.
uses
Nat.div_add_mod,Nat.dvd_add_right,dvd_mul_right,Nat.mod_ltlemma round_robin_sequence_count_eq_dvd_iff (n m a : ℕ) (hn : 0 < n) (ha : a < n) : (n ∣ (m + (n - 1 - a) + 1)) ↔ m % n = a := by have H : m + (n - 1 - a) + 1 = n * (m / n) + (m % n + (n - 1 - a) + 1) := by have := Nat.div_add_mod m n omega rw [H, Nat.dvd_add_right (dvd_mul_right n (m / n))] have hr : m % n < n := Nat.mod_lt m hn have h1 : 0 < m % n + (n - 1 - a) + 1 := by omega have h2 : m % n + (n - 1 - a) + 1 < 2 * n := by omega
The divisibility condition $n ∣ (m + (n - 1 - a) + 1)$ is equivalent to $m % n = a$.
For the forward direction, assuming $n ∣ Y$, since $0 < Y < 2 * n$, the previous lemma (`round_robin_sequence_count_eq_dvd_eq_self`) implies $Y = n$. Expanding $Y = m % n + (n - 1 - a) + 1 = n$ gives $m % n = a$. Conversely, if $m % n = a$, substituting this into $Y$ gives $a + (n - 1 - a) + 1 = n$, which is clearly divisible by $n$.
uses
round_robin_sequence_count_eq_dvd_eq_selfconstructor · intro hdvd have := round_robin_sequence_count_eq_dvd_eq_self h1 h2 hdvd omega · rintro rfl have : m % n + (n - 1 - m % n) + 1 = n := by omega rw [this]
The Round-Robin sequence for $m + 1$ goods appends agent $m % n$ to the sequence for $m$ goods.
Unfolding the definition of `round_robin_sequence`, which generates the list of turns via `List.ofFn` of $t \mapsto t % n$, and rewriting with `List.ofFn_succ'`, the sequence on $m + 1$ goods decomposes into the prefix of length $m$ followed by the final element $m % n$.
uses
List.ofFn_succ'lemma round_robin_sequence_count_eq_succ (n m : ℕ) [NeZero n] : round_robin_sequence n (m + 1) = (round_robin_sequence n m).concat ⟨m % n, Nat.mod_lt _ (NeZero.pos n)⟩ := by unfold round_robin_sequence rw [List.ofFn_succ'] congr 1
Base case $m = 0$: agent $a$ appears $0$ times in the empty sequence, matching $(0 + (n - 1 - a)) / n = 0$.
We proceed by induction on $m$. For $m = 0$, the sequence is empty, so `List.count_nil` gives $0$. Since $a < n$ and $0 < n$ (`NeZero.pos`), the numerator $0 + (n - 1 - a)$ is strictly less than $n$. By `Nat.div_eq_of_lt`, integer division by $n$ produces $0$, completing the base case.
uses
List.count_nil,NeZero.pos,Nat.div_eq_of_lttheorem round_robin_sequence_count_eq (n m : ℕ) [NeZero n] (a : Fin n) : (round_robin_sequence n m).count a = (m + (n - 1 - a.val)) / n := by induction m with | zero => have : (round_robin_sequence n 0) = [] := by unfold round_robin_sequence rfl rw [this] simp only [List.count_nil] have ha : a.val < n := a.isLt have hn : 0 < n := NeZero.pos n have : 0 + (n - 1 - a.val) < n := by omega rw [Nat.div_eq_of_lt this]
In the induction step, the count in the sequence of length $m + 1$ equals $(m + (n - 1 - a)) / n$ plus $1$ if $m % n = a$ and $0$ otherwise.
By `round_robin_sequence_count_eq_succ`, the sequence of length $m + 1$ is the concatenation of the sequence of length $m$ with the singleton $[m % n]$. Converting concatenation to append (`List.concat_eq_append`), `List.count_append` splits the count into the count over the first $m$ turns plus the count in the singleton (`List.count_singleton`). By the induction hypothesis, the first part is $(m + (n - 1 - a)) / n$. The singleton count tests boolean equality with $a$, which is equivalent to propositional equality $m % n = a$ (`beq_iff_eq`, `Fin.ext_iff`).
uses
round_robin_sequence_count_eq_succ,List.concat_eq_append,List.count_append,List.count_singleton,beq_iff_eq,Fin.ext_iff| succ m ih => rw [round_robin_sequence_count_eq_succ] rw [List.concat_eq_append, List.count_append, ih] rw [List.count_singleton] have h_count_sing : (if (⟨m % n, Nat.mod_lt _ (NeZero.pos n)⟩ : Fin n) == a then 1 else 0) = (if m % n = a.val then 1 else 0) := by split_ifs with h1 h2 h3 · rfl · exfalso apply h2 rw [beq_iff_eq, Fin.ext_iff] at h1 exact h1 · exfalso apply h1 rw [beq_iff_eq, Fin.ext_iff] exact h3 · rfl rw [h_count_sing]The updated count matches the formula $(m + 1 + (n - 1 - a)) / n$, concluding the induction.
By `Nat.succ_div`, the formula $(m + 1 + (n - 1 - a)) / n$ equals $(m + (n - 1 - a)) / n + 1$ if $n ∣ (m + (n - 1 - a) + 1)$ and $(m + (n - 1 - a)) / n$ otherwise. By the equivalence lemma (`round_robin_sequence_count_eq_dvd_iff`, using `NeZero.pos`), this divisibility holds if and only if $m % n = a$. Simplifying with this equivalence shows the formula matches the count from the previous step.
uses
Nat.succ_div,round_robin_sequence_count_eq_dvd_iff,NeZero.poshave h_succ_div : (m + 1 + (n - 1 - a.val)) / n = (m + (n - 1 - a.val)) / n + if n ∣ (m + (n - 1 - a.val) + 1) then 1 else 0 := by have : m + 1 + (n - 1 - a.val) = (m + (n - 1 - a.val)) + 1 := by omega rw [this, Nat.succ_div] rw [h_succ_div] have h_dvd := round_robin_sequence_count_eq_dvd_iff n m a.val (NeZero.pos n) a.isLt simp only [h_dvd]
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers on the left by $k$ preserves the inequality ($n ≤ m → k * n ≤ k * m$).
Nat.div_add_mod- For any natural numbers $m$ and $n$, $n * (m / n) + m % n = m$.
Nat.dvd_add_right- If $a$ divides $b$, then $a$ divides $b + c$ if and only if $a$ divides $c$.
dvd_mul_right- An element $a$ divides any product $a * b$.
Nat.mod_lt- The remainder $x % y$ is strictly less than $y$ whenever $0 < y$.
round_robin_sequence_count_eq_dvd_eq_self- A positive multiple of $n$ strictly less than $2 * n$ must equal $n$.
List.ofFn_succ'- A list generated by `List.ofFn` on $n + 1$ elements equals the list on the first $n$ elements concatenated with the $(n+1)$-th element at the end.
List.count_nil- The count of any element in the empty list is zero.
NeZero.pos- A nonzero natural number is strictly positive ($0 < a$).
Nat.div_eq_of_lt- If $a < b$, then integer division $a / b$ equals $0$.
round_robin_sequence_count_eq_succ- The Round-Robin sequence of $m + 1$ goods is obtained by appending agent $m % n$ to the sequence of $m$ goods.
List.concat_eq_append- Concatenating an element to a list is equivalent to appending the singleton list containing that element.
List.count_append- The count of an element in the append of two lists is the sum of its counts in each list.
List.count_singleton- The count of $a$ in a singleton list $[b]$ is $1$ if $b == a$ and $0$ otherwise.
beq_iff_eq- Boolean equality $a == b$ evaluates to true if and only if $a = b$.
Fin.ext_iff- Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Nat.succ_div- Division of $a + 1$ by $b$ equals $a / b + 1$ if $b$ divides $a + 1$, and $a / b$ otherwise.
round_robin_sequence_count_eq_dvd_iff- For $a < n$, $n$ divides $m + (n - 1 - a) + 1$ if and only if $m % n = a$.
- The agents are indexed by `Fin n`, requiring explicit conversion between boolean equality (`==`), equality of `Fin n` terms, and equality of their underlying natural numbers (`Fin.ext_iff`).
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.
lemma round_robin_sequence_count_eq_dvd_eq_self {n Y : ℕ} (h1 : 0 < Y) (h2 : Y < 2 * n) (hdiv : n ∣ Y) : Y = n := by rcases hdiv with ⟨k, rfl⟩ have hk_lt : k < 2 := by by_contra! h have : 2 * n ≤ n * k := by calc 2 * n = n * 2 := by ring _ ≤ n * k := Nat.mul_le_mul_left n h omega have hk_pos : 0 < k := by by_contra! h have : k = 0 := by omega subst this simp at h1 have : k = 1 := by omega subst this simplemma round_robin_sequence_count_eq_dvd_iff (n m a : ℕ) (hn : 0 < n) (ha : a < n) : (n ∣ (m + (n - 1 - a) + 1)) ↔ m % n = a := by have H : m + (n - 1 - a) + 1 = n * (m / n) + (m % n + (n - 1 - a) + 1) := by have := Nat.div_add_mod m n omega rw [H, Nat.dvd_add_right (dvd_mul_right n (m / n))] have hr : m % n < n := Nat.mod_lt m hn have h1 : 0 < m % n + (n - 1 - a) + 1 := by omega have h2 : m % n + (n - 1 - a) + 1 < 2 * n := by omega constructor · intro hdvd have := round_robin_sequence_count_eq_dvd_eq_self h1 h2 hdvd omega · rintro rfl have : m % n + (n - 1 - m % n) + 1 = n := by omega rw [this]lemma round_robin_sequence_count_eq_succ (n m : ℕ) [NeZero n] : round_robin_sequence n (m + 1) = (round_robin_sequence n m).concat ⟨m % n, Nat.mod_lt _ (NeZero.pos n)⟩ := by unfold round_robin_sequence rw [List.ofFn_succ'] congr 1/-- Exact pick count of an agent in the Round-Robin sequence: agent a picks (m + n - 1 - a)/n times. -/theorem round_robin_sequence_count_eq (n m : ℕ) [NeZero n] (a : Fin n) : (round_robin_sequence n m).count a = (m + (n - 1 - a.val)) / n := by induction m with | zero => have : (round_robin_sequence n 0) = [] := by unfold round_robin_sequence rfl rw [this] simp only [List.count_nil] have ha : a.val < n := a.isLt have hn : 0 < n := NeZero.pos n have : 0 + (n - 1 - a.val) < n := by omega rw [Nat.div_eq_of_lt this] | succ m ih => rw [round_robin_sequence_count_eq_succ] rw [List.concat_eq_append, List.count_append, ih] rw [List.count_singleton] have h_count_sing : (if (⟨m % n, Nat.mod_lt _ (NeZero.pos n)⟩ : Fin n) == a then 1 else 0) = (if m % n = a.val then 1 else 0) := by split_ifs with h1 h2 h3 · rfl · exfalso apply h2 rw [beq_iff_eq, Fin.ext_iff] at h1 exact h1 · exfalso apply h1 rw [beq_iff_eq, Fin.ext_iff] exact h3 · rfl rw [h_count_sing] have h_succ_div : (m + 1 + (n - 1 - a.val)) / n = (m + (n - 1 - a.val)) / n + if n ∣ (m + (n - 1 - a.val) + 1) then 1 else 0 := by have : m + 1 + (n - 1 - a.val) = (m + (n - 1 - a.val)) + 1 := by omega rw [this, Nat.succ_div] rw [h_succ_div] have h_dvd := round_robin_sequence_count_eq_dvd_iff n m a.val (NeZero.pos n) a.isLt simp only [h_dvd]