Erdős Problem #872 — Maximizing moves in a divisibility game
Let be an integer. Starting with no selected integers, two players alternately add an integer from to a common set , subject to the rule that no two distinct members of divide one another: for distinct , neither nor may hold. A move is legal only if the enlarged set still satisfies this rule, and the game ends when no legal move remains. Call the player seeking to maximize the total number of moves Prolonger and the player seeking to minimize it Shortener. The question asks how many moves Prolonger can guarantee, and in particular whether the guarantee is at least for positive and sufficiently large , or at least . The original formulation does not specify who moves first, so these questions have separate first-player conventions. Erdős Problem #872
Background
Erdős presented this divisibility game as a number-theoretic variant of a game associated with Hajnal: players add edges to a graph while maintaining the condition that the graph is triangle-free. In both games, the evolving object must avoid a forbidden configuration, and play stops when it cannot be enlarged by a legal move; this family is called saturation games. The analogy is useful for context, but bounds for the graph game do not by themselves give bounds for the divisibility game. Erdős Problem #872
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.