关于算术级数制造者-破坏者游戏中阈值s(k)的显式值与渐近性质的问询

咱们先明确这个两人游戏的规则：两名玩家轮流从1到n中选取一个整数，每个数只能被选一次。玩家1获胜的条件是，自己选中的数集合里包含一个长度≥k的算术级数；玩家2的目标则是阻止这件事，直到所有数都被选完时玩家1仍未达成条件，玩家2就获胜。

我一直有个猜想——除非我漏了什么核心细节，否则对于每一个k，应该存在一个阈值s(k)：当n < s(k)时玩家2有必胜策略，当n ≥ s(k)时玩家1有必胜策略。现在我想知道：有没有人已经算出s(k)的显式值，或者至少有不错的渐近估计呢？

我目前的研究进展： #

• 首先是一些 trivial 的结论：s(1)=1，s(2)=3。我还通过与m,n,k-游戏对比，证明了s(3)≤12、s(4)≤30、s(5)≤225，但我感觉s(5)的实际值应该比这个上界小很多。不过当k≥6时，这种对比的方法就不再管用了。
• 关于获胜集合的数量，我得到了通用表达式：w:=tn - (t²+t)/2*(k-1)，其中t=⌊n/(k-1)⌋。根据Erdős和Selfridge的结论：
  • 如果 w < 2^(k-1)，那么玩家2有必胜策略；
  • 反过来，如果 w > 2^(k-4)*(k²−k)*n，玩家1有必胜策略（不过这个上界应该还能进一步优化）。
• 但这些界的实用性并不强，比如对于k=10，只能得到101≤s(10)≤103690，这个范围实在太宽泛了。

题外话： #

除非能找到什么巧妙的通用策略，不然我觉得当n在100到200之间的时候，这个游戏会相当有意思，尤其是选一个合适的k（至少10吧），再引入pie rule（让后手可以选择交换身份的规则）来平衡局势！

后续补充： #

• 补充1：当k足够大时，s(k) > 2^(k/2)*√(k-1) 成立。
• 补充2：已经确定s(3)=5。
• 补充3：我朋友通过计算机搜索证明了s(4)=15。
• 补充4：我最初给出的那些上界是错误的。

备注：内容来源于stack exchange，提问作者Michał Zapała