Erdős Problem #872

The problem

Consider the two-player game in which players alternately choose integers from $\{2,3,\ldots,n\}$ to be included in some set $A$ (the same set for both players) such that no $a\mid b$ for $a\neq b\in A$.

The game ends when no legal move is possible. One player wants the game to last as long as possible, the other wants the game to end quickly. How long can the game be guaranteed to last for?

At least $\epsilon n$ moves? (For $\epsilon>0$ and $n$ sufficiently large.) At least $(1-\epsilon)\frac{n}{2}$ moves?

Statement quoted from erdosproblems.com/872, maintained by Thomas Bloom. Original source: [Er92c,p.47]. Current status there: open.

AI contributions

As recorded in Terence Tao's wiki AI contributions to Erdős problems (data as of 30 Jun 2026). 🟢 full, 🟡 partial, ⚪ unverified, 🔴 incorrect.

Caveats

The wiki's classifications are provisional and are not a benchmark. Many Erdős problems have never had a thorough literature review, so a result that looks new may later turn out to be known; some problems were also stated ambiguously or incorrectly. See the problem page for the full discussion.

∎