Skip to content

Erdős problem 872

Each move claims exactly one pool element, so the minimax value never exceeds the number of already claimed elements plus the number of still unclaimed elements.

Sources

The source's own material, retained exactly.

6 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

872.lean

Retained formal statement2 of 6

Erdős Problem 872, part (ii) (strong form): for every ϵ>0\epsilon > 0, the game length is at least (1−ϵ)⋅n/2(1-\epsilon) \cdot n / 2 for all sufficiently large nn.

Status note: the forum thread (April-May 2026) records Shortener strategies giving L(n)≤(23/48+o(1))⋅nL(n) \leq (23/48 + o(1)) \cdot n (described in the thread as accepted as correct, with a Lean formalization in progress) and a claimed L(n)≤0.19⋅nL(n) \leq 0.19 \cdot n, either of which would answer this question negatively under the Prolonger-first convention. Neither is published, so the statement is recorded here as the original Erdős question.

FormalConjectures/ErdosProblems/872.leanErdos872.erdos_872.parts.ii1 lineExact file
True ↔ ∀ ε > 0, ∀ᶠ (n : ℕ) in Filter.atTop, ↑(Erdos872.L n) ≥ (1 - ε) * ↑n / 2
OpenStatement only, no proof