OPEN
This is open, and cannot be resolved with a finite computation.
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?
A number theoretic variant of a combinatorial game of Hajnal, in which players alternately add edges to a graph while keeping it triangle-free. This game must trivially end in at most $n^2/4$ moves, and Füredi and Seress
[FuSe91] proved that it can be guaranteed to last for $\gg n\log n$ moves. Biró, Horn, and Wildstrom
[BPW16] proved that it must end in at most $(\frac{26}{121}+o(1))n^2$ moves.
This type of game is known as a saturation game.
Erdős does not specify which player goes first, which may result in different answers.
View the LaTeX source
Additional thanks to: Desmond Weisenberg
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #872, https://www.erdosproblems.com/872, accessed 2025-11-16
