Logo
Tags Prizes
More
FAQ Problem Lists Definitions Links How to help
All Random Solved Random Open
OPEN
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.