Problem 872

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?

Source: erdosproblems.com/872

Number theory
Primitive sets

Wiki page

Status

Open

No claim settles this problem.

Open on the site (OPEN; page last edited 24 April 2026; one proof claim is listed as full on the proof-claims thread). The frontmatter standing derives from the claim pages: the pending partial claim Price's Shortener strategy would answer the second displayed question in the negative with Prolonger moving first, and the pending partial claim Buddhdev's sublinear bound would answer both displayed questions in the negative while leaving the order of the game's length open; no full claim is recorded.

BPW16: Biró, Csaba and Horn, Paul and Wildstrom, D. Jacob, An upper bound on the extremal version of Hajnal's triangle-free game. Discrete Appl. Math. (2016), 20-28.
Er92c: Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. 15 (1992), 34-50; the game is on p. 47. Library home: Erdős 1992.
FuSe91: Füredi, Zoltán and Reimer, Dave and Seress, Ákos, Hajnal's triangle-free game and extremal graph problems. Congr. Numer. (1991), 123-128.

Problem 872

Status

Proof claims

Discussion