取格子游戏的构造性策略

作者: , 共 513 字
系列:头脑风暴

查看该系列所有文章

在 MIT BBS 上看到一个有趣的题目

一个 M*N 的方阵,每个格子里放一个硬币。甲乙轮流取:选定一枚硬币后,必须取走它上方、右方和右上方的所有硬币(如果有的话)。拿走最左下角那个输。问谁有必胜策略?

有人立即给出了答案:

假设后手有必胜策略。

先手取(M,N),如果后手的必胜策略是取(i, j),那么先手开局不取(M,N)而取(i,j),则先手必胜。矛盾。

所以先手必胜。

这样的解法被称为存在性证明。上面问题可以在两个方面加以扩展:

1、求构造性策略。

即需要给出先手的必胜操作具体是怎么样的。比如当 N=M 时,可以先取(2, 2)处的格子(假设左下方格子坐标为(1, 1)),然后与后手对称地取格子。

2、如果是任意的游戏状态,其各方的必胜策略又是如何?

一个游戏状态可以表示为\( a_1, a_2, \cdots, a_n\) ,其中\( a_1\geq a_2\geq\cdots\geq a_n\) ,分别表示第一列到最后一列各列剩余的方格数量。当\( n=2\) 时,\( \{(a_1, a_2)|a_1=a_2+1\}\) 为后手的必胜状态集。对于较大的\( n\) 后手的状态集不太好求。

Q. E. D.

系列: 头脑风暴 »
最近看到一个有趣的问题:
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。
类似文章:
相似度: 0.194
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
相似度: 0.191
\( n\) 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
相似度: 0.146
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个\( 2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
相似度: 0.107
这个题目听说是 MSRA 的面试题。
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
相似度: 0.097
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
相似度: 0.080
最近看到一个有趣的问题:
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。
一个游戏:持续的抛一个均匀硬币,直到抛到出现反面为止,假设在之前你抛除了\( k\) 次正面,你将得到\( 2^{k+1}\) 次方这么多钱。
最近看了几个风险管理和组合管理系统,有几个系统里附带了组合优化模块,也了解到这一方面工业界的最新成果。最新的组合优化模块被称为第二代最优化模型,主要成果就是二阶锥优化算法的应用,其中一个重要的改进为对 alpha 估计的不准确性考虑在内。
Excel 的数据透视表是一个很好用的功能,我写了一个 Matlab 版本,在处理上和 Excel 的透视表差不多,还差一个 filter 而已。