Erdős 问题 #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?

问题陈述引自 erdosproblems.com/872（Thomas Bloom 维护），保留英文原文。原始出处：[Er92c,p.47]。该网站上的当前状态：未解决。

AI 贡献

以下记录来自 Terence Tao 的 Wiki AI contributions to Erdős problems（数据截至 2026 年 6 月 30 日）。🟢 完整、🟡 部分、⚪ 待核实、🔴 有误。

说明

Wiki 中的分类是暂定的，也不是一份评测榜单。许多 Erdős 问题从未有过完整的文献调研，看似新的结果日后可能被发现早已存在；也有一些问题本身的表述有歧义或错误。完整的讨论见问题页面。

∎