AFTD Auto-Formalizing Theoretical Domains

team_half_symm

lemmaverified

Symmetry of the fair binomial: S_k(t) + S_k(k+1-t) = 1.

Statement

lemma team_half_symm (k : ℕ) : ∀ t, t ≤ k + 1 →
    team_tail (List.replicate k (1 / 2 : ℝ)) t
      + team_tail (List.replicate k (1 / 2 : ℝ)) (k + 1 - t) = 1
Source
step towards team_thm4_part2_false / team_thm4_part2_exists_false (The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2))
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • team_tailPoisson-binomial upper tail: team_tail [q₁, …, qₙ] t is the probability that at least t of n independent events with success probabilities…
  • team_tail_zeroThe probability of at least 0 successes is 1.
  • team_tail_gtThe probability of more successes than there are events is 0.
Used by 1
  • team_half_oddAn odd number 2m+3 of fair coins: at least m+2 heads with probability 1/2.

Lean source view module on GitHub

/-- Symmetry of the fair binomial: `S_k(t) + S_k(k+1-t) = 1`. -/lemma team_half_symm (k : ℕ) : ∀ t, t ≤ k + 1 →    team_tail (List.replicate k (1 / 2 : ℝ)) t      + team_tail (List.replicate k (1 / 2 : ℝ)) (k + 1 - t) = 1 := by  induction k with  | zero =>    intro t ht    interval_cases t <;> simp [team_tail]  | succ k ih =>    intro t ht    rcases Nat.eq_zero_or_pos t with h0 | hpos    · subst h0      rw [team_tail_zero, team_tail_gt _ _ (by simp)]      ring    · rcases Nat.lt_or_ge t (k + 2) with hlt | hge      · -- 1 ≤ t ≤ k + 1        rw [List.replicate_succ]        simp only [team_tail]        have e1 := ih (t - 1) (by omega)        have e2 := ih t (by omega)        have h3 : k + 1 + 1 - t - 1 = k + 1 - t := by omega        have h4 : k + 1 - (t - 1) = k + 1 + 1 - t := by omega        rw [h3]        rw [h4] at e1        linarith      · have : t = k + 2 := by omega        subst this        rw [team_tail_gt _ _ (by simp), show k + 1 + 1 - (k + 2) = 0 by omega, team_tail_zero]        ring
See it in the graphDiscuss this resultChallenge it