← All problems

Erdős Problem #872 — Maximizing moves in a divisibility game

34 years old · traced to

Let n≥2n\ge 2 be an integer. Starting with no selected integers, two players alternately add an integer from {2,3,…,n}\{2,3,\ldots,n\} to a common set AA, subject to the rule that no two distinct members of AA divide one another: for distinct a,b∈Aa,b\in A, neither a∣ba\mid b nor b∣ab\mid a 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 ϵn\epsilon n for positive ϵ\epsilon and sufficiently large nn, or at least (1−ϵ)n/2(1-\epsilon)n/2. 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

Progress summary

Never refreshed

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.