CHOMP游戏中“几乎不行动”策略适用场景及矩形棋盘右上角开局胜势相关技术问询
CHOMP游戏中“几乎不行动”策略适用场景及矩形棋盘右上角开局胜势相关技术问询
最近这个问题也在MO上被讨论了:
用策略偷取法证明矩形棋盘上的CHOMP是先手胜时,会用到先手第一步取右上角方块的思路。但要注意,这个反证法的性质决定了,这不代表右上角开局在所有情况下都是好招——事实上有大把矩形棋盘,先手第一步走右上角反而会陷入败局。
注:不同版本的CHOMP毒方块位置不一样,这里统一采用相关资料里的约定。
我现在想搞清楚,右上角开局到底有多大概率是胜招?(补充一句:根据策略偷取法的逻辑,如果某个棋盘上右上角是胜招,那它其实是唯一的胜招,我一开始还没意识到这点。)
这个问题可以从两个角度来问:
问题1
固定$n$,定义$c_n$为满足“$m×n$棋盘上,先手走右上角是胜招”的所有$m$构成集合的上渐近密度,求$c_3$的值?
(很容易就能得出$c_1=0$、$c_2=1$,所以$c_3$是第一个值得深入研究的情况。当然更高阶的$c_i$也很有意思,但我担心它们的求解难度会很高。)
问题2
是否对任意正整数$k$,都存在$m,n>k$,使得在$m×n$的CHOMP棋盘上,先手走右上角是胜招?(甚至当$k=2$时,这个结论是否成立?)
备注:内容来源于stack exchange,提问作者Noah Schweber
相关产品推荐
相关产品推荐

