AFTD Auto-Formalizing Theoretical Domains

round_robin_sequence_count_le_two_of_ne_zero

theoremverified

In the Round-Robin sequence of n agents and 2n + 1 goods, every agent other than agent 0 picks at most twice.

Statement

theorem round_robin_sequence_count_le_two_of_ne_zero (n : ℕ) [NeZero n] (j : Fin n) (hj : j ≠ 0) :
    (round_robin_sequence n (2 * n + 1)).count j ≤ 2
Source
Step for round_robin_pne_ef1_of_card_le_two_mul_add_one (thread RT-3).
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
  • round_robin_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
Used by 1

The proof, explained

We partition the length-(2n + 1) Round-Robin sequence into three segments: the first n elements, the next n elements, and the single remaining element. The first two segments each consist of n distinct agents, so agent j can appear at most once in each. The last item is allocated to agent (2n) % n = 0, which cannot be j since j ≠ 0, so j appears 0 times in the tail, yielding at most 1 + 1 + 0 = 2 picks in total.

  1. Define the sequence `seq` and record its length and indexing formula.

    We let `seq` denote `round_robin_sequence n (2 * n + 1)`. By `rr_l1_seq_length`, its total length is 2n + 1, and by `rr_l1_seq_getElem`, the agent at index t has numerical value t % n.

    lines 3–6

    uses rr_l1_seq_length, rr_l1_seq_getElem

      set seq := round_robin_sequence n (2 * n + 1) with hseq
      have hlen : seq.length = 2 * n + 1 := rr_l1_seq_length n _
      have ex : ∀ (t : ℕ) (ht : t < seq.length), (seq[t]).val = t % n :=
        fun t ht => rr_l1_seq_getElem n _ t ht
  2. Decompose the count of j in `seq` into the sum of its counts in three subsegments.

    Using `List.take_append_drop` twice, `seq` is decomposed into the prefix of length n (`seq.take n`), the next n elements (`(seq.drop n).take n`), and the remaining tail (`seq.drop (n + n)`). By `List.count_append`, the count of j in `seq` equals the sum of its counts in these three disjoint sublists.

    lines 7–8

    uses List.take_append_drop, List.count_append, List.drop_drop

      rw [← List.take_append_drop n seq, List.count_append, ← List.take_append_drop n (seq.drop n),
        List.count_append, List.drop_drop]
  3. Agent j appears at most once in the first segment: `(seq.take n).count j ≤ 1`.

    By `rr_l1_count_take_le_one`, any prefix of length at most n in a round-robin sequence contains each agent at most once. Applying this with k = n (using `le_rfl`) yields the bound for the first n items.

    lines 9–10

    uses rr_l1_count_take_le_one, le_rfl

      have h1 := rr_l1_count_take_le_one n (2 * n + 1) n le_rfl j
      rw [← hseq] at h1
  4. Agent j appears at most once in the second segment: `((seq.drop n).take n).count j ≤ 1`.

    By `List.nodup_iff_count_le_one.mp`, it suffices to show that this segment contains no duplicate elements (`Nodup`), which by `List.nodup_iff_injective_getElem` is equivalent to the injectivity of its indexing function. For any indices x, y < n where the elements agree, their values are (n + x) % n and (n + y) % n. Because x, y < n, these reduce by `Nat.add_mod_left` and `Nat.mod_eq_of_lt` to x and y, proving x = y and hence injectivity.

    lines 11–21

    uses List.nodup_iff_count_le_one.mp, List.nodup_iff_injective_getElem, List.length_take, List.length_drop, congrArg, List.getElem_take, List.getElem_drop, Nat.add_mod_left, Nat.mod_eq_of_lt, Fin.ext

      have h2 : ((seq.drop n).take n).count j ≤ 1 := by
        apply List.nodup_iff_count_le_one.mp
        rw [List.nodup_iff_injective_getElem]
        intro ⟨x, hx⟩ ⟨y, hy⟩ hxy
        simp only [List.length_take, List.length_drop, hlen] at hx hy
        have h1 := congrArg Fin.val hxy
        simp only [List.getElem_take, List.getElem_drop, ex] at h1
        have e1 : (n + x) % n = x := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)]
        have e2 : (n + y) % n = y := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)]
        rw [e1, e2] at h1
        exact Fin.ext h1
  5. Agent j does not appear in the final tail: `(seq.drop (n + n)).count j = 0`.

    By `List.count_eq_zero.mpr`, it suffices to show that j does not belong to `seq.drop (n + n)`. The tail has length (2n + 1) - 2n = 1, so any index t within it must be 0. The element at index 0 has value (2n + 0) % n = 0, which would imply j = 0, contradicting the hypothesis that j ≠ 0.

    lines 22–33

    uses List.count_eq_zero.mpr, List.mem_iff_getElem.mp, List.length_drop, congrArg, List.getElem_drop, Fin.ext

      have h3 : (seq.drop (n + n)).count j = 0 := by
        apply List.count_eq_zero.mpr
        intro hmem
        obtain ⟨t, ht, hte⟩ := List.mem_iff_getElem.mp hmem
        simp only [List.length_drop, hlen] at ht
        have h1 := congrArg Fin.val hte
        simp only [List.getElem_drop, ex] at h1
        have : (n + n + t) % n = 0 := by
          have ht0 : t = 0 := by omega
          subst ht0; simp
        rw [this] at h1
        exact hj (Fin.ext h1.symm)
  6. The total count of j in the round-robin sequence is at most 2. automation

    Linear integer arithmetic (`omega`) combines the bounds from the three segments: at most 1 from the first, at most 1 from the second, and 0 from the tail, showing 1 + 1 + 0 ≤ 2.

    line 34

      omega
congrArg
Applying a function to equal arguments yields equal results: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
le_rfl
The reflexive property of inequality: a ≤ a.
List.count_append
The count of an element in the concatenation of two lists is the sum of its counts in each list.
List.count_eq_zero.mpr
If an element does not belong to a list, its count in that list is 0.
List.drop_drop
Dropping i elements from a list already dropped by j elements is equivalent to dropping j + i elements: drop i (drop j l) = drop (j + i) l.
List.getElem_drop
The j-th element of drop i xs is xs[i + j].
List.getElem_take
The i-th element of take j xs is xs[i].
List.length_drop
The length of drop i l is length(l) - i.
List.length_take
The length of take i l is min(i, length(l)).
List.mem_iff_getElem.mp
If an element belongs to a list, it appears at some index i < length(l).
List.nodup_iff_injective_getElem
A list has no duplicate elements (Nodup) if and only if its indexing function i ↦ l[i] is injective.
List.nodup_iff_count_le_one.mp
If a list has no duplicate elements (Nodup), then every element appears at most once in the list.
List.take_append_drop
A list can be reconstructed by appending its drop to its prefix: take i l ++ drop i l = l.
Nat.add_mod_left
For natural numbers x and z, (x + z) % x = z % x.
Nat.mod_eq_of_lt
If a < b for natural numbers, then a % b = a.
rr_l1_count_take_le_one
In a round-robin sequence of n agents, any prefix of length k ≤ n contains each agent at most once.
rr_l1_seq_getElem
The numerical value of the t-th element in round_robin_sequence n m is t % n.
rr_l1_seq_length
The length of round_robin_sequence n m is m.

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

theorem round_robin_sequence_count_le_two_of_ne_zero (n : ℕ) [NeZero n] (j : Fin n) (hj : j ≠ 0) :    (round_robin_sequence n (2 * n + 1)).count j ≤ 2 := by  set seq := round_robin_sequence n (2 * n + 1) with hseq  have hlen : seq.length = 2 * n + 1 := rr_l1_seq_length n _  have ex : ∀ (t : ℕ) (ht : t < seq.length), (seq[t]).val = t % n :=    fun t ht => rr_l1_seq_getElem n _ t ht  rw [← List.take_append_drop n seq, List.count_append, ← List.take_append_drop n (seq.drop n),    List.count_append, List.drop_drop]  have h1 := rr_l1_count_take_le_one n (2 * n + 1) n le_rfl j  rw [← hseq] at h1  have h2 : ((seq.drop n).take n).count j ≤ 1 := by    apply List.nodup_iff_count_le_one.mp    rw [List.nodup_iff_injective_getElem]    intro ⟨x, hx⟩ ⟨y, hy⟩ hxy    simp only [List.length_take, List.length_drop, hlen] at hx hy    have h1 := congrArg Fin.val hxy    simp only [List.getElem_take, List.getElem_drop, ex] at h1    have e1 : (n + x) % n = x := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)]    have e2 : (n + y) % n = y := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)]    rw [e1, e2] at h1    exact Fin.ext h1  have h3 : (seq.drop (n + n)).count j = 0 := by    apply List.count_eq_zero.mpr    intro hmem    obtain ⟨t, ht, hte⟩ := List.mem_iff_getElem.mp hmem    simp only [List.length_drop, hlen] at ht    have h1 := congrArg Fin.val hte    simp only [List.getElem_drop, ex] at h1    have : (n + n + t) % n = 0 := by      have ht0 : t = 0 := by omega      subst ht0; simp    rw [this] at h1    exact hj (Fin.ext h1.symm)  omega
See it in the graphDiscuss this resultChallenge it