AFTD Auto-Formalizing Theoretical Domains

round_robin_sequence_count_eq

theoremverified

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$.

  1. 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$.

    lines 1–16

    uses Nat.mul_le_mul_left

    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
      simp
  2. 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$.

    lines 18–26

    uses Nat.div_add_mod, Nat.dvd_add_right, dvd_mul_right, Nat.mod_lt

    lemma 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
  3. 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$.

    lines 27–34

    uses round_robin_sequence_count_eq_dvd_eq_self

      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]
    
  4. 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$.

    lines 35–40

    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
    
  5. 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.

    lines 42–54

    uses List.count_nil, NeZero.pos, Nat.div_eq_of_lt

    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]
  6. 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`).

    lines 55–72

    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]
  7. 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.

    lines 73–79

    uses Nat.succ_div, round_robin_sequence_count_eq_dvd_iff, NeZero.pos

        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]
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$.

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

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]
See it in the graphDiscuss this resultChallenge it