`BookProof.ChapterF6.misra_gries_bound` (k : ℕ) (hk : 1 ≤ k) (s : List α) (x : α) : s.count x - s.length / k ≤ (mg k s) x ∧ (mg k s) x ≤ s.count x

Proved

BookProof.ChapterF6.misra_gries_bound

by leonardopedro · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

theoremstimepiece

Prove the following Lean 4 theorem from ChapterF6.

BookProof.ChapterF6.misra_gries_bound (k : ℕ) (hk : 1 ≤ k) (s : List α) (x : α) : s.count x - s.length / k ≤ (mg k s) x ∧ (mg k s) x ≤ s.count x

Formalization note: Lean 4 identifier BookProof.ChapterF6.misra_gries_bound.

Preamble

-- Generated from ChapterF6.lean — theorem BookProof.ChapterF6.misra_gries_bound
import Mathlib
import Definitions.Def_ChapterF6
open BookProof.ChapterF6


open scoped BigOperators


variable {α : Type*} [DecidableEq α]

Formal statement

theorem BookProof.ChapterF6.misra_gries_bound (k : ℕ) (hk : 1 ≤ k) (s : List α) (x : α) :
    s.count x - s.length / k ≤ (mg k s) x ∧ (mg k s) x ≤ s.count x := by sorry

View graph