现在的位置: 首页 > 综合 > 正文

棋盘问题

2013年08月17日 ⁄ 综合 ⁄ 共 898字 ⁄ 字号 评论关闭

校内转载---->很有意思!

Alice和Bob两人玩一种硬币游戏。游戏在一个2*2的棋盘上进行,棋盘上每个格子上都有一枚硬币。

在每一回合,Alice可以决定选择翻转某两枚或者一枚硬币,接着Bob可以选择将棋盘旋转90,180或者270度,也可以什么都不做。

Alice在整个游戏过程中,不知道游戏刚开始棋盘的状态,也无法看到棋盘上的硬币,甚至不知道Bob每回合是否旋转了棋盘。

游戏轮流进行,直到棋盘上所有硬币都正面朝上或者反面朝上,Alice获得胜利。

Alice有策略能够获得胜利么?他的最优策略是什么?

 

回复不能超过500字符,我就自己开一贴了~~

这个题目真好玩~

Alice有必胜策略
棋盘可以分为4个状态:
1. 只有一个正面或者反面
2. 有两个正面和两个反面,同面的组成一条边
3. 有两个正面和两个反面,同面的组成一个对角
4. 全部正面或者反面,目的状态
操作可以分为三种:
A. 反转某对角
B. 反转某边
C. 反转某点

然后能够发现:
状态1通过A,B还是到1,通过C能到2或者3,或者4(取胜)
状态2通过A还是2,通过B到3,或者4(取胜),通过C到1
状态3通过A到4(取胜),通过B到2,通过C到1

这里能够发现很有趣的现象,考虑A操作,对于状态3能够直接取胜,对于另外两种状态,并不改变状态本身,所以A操作应该作为必胜策略的第一步。于是我们有  A->...

第一步之后还不取胜的只有状态1,2,第一步之后他们的状态不变,这是可以考虑操作B,因为操作B不改变状态1(操作完后还是状态1),而状态2会变为状态3,对于状态3我们已经考虑过了。于是我们的必胜策略增加两步变成:A->B->A->...

对于初始状态为2,3的情况,前面这3步就能保证达到目的状态了。

那么状态1呢?我们发现前3步中,状态1从来没有变过,只有操作C会使状态1达到目的状态,或者转化成状态2,3。此时结论就显而易见了。

我们的必胜策略就是A->B->A->C->A->B->A

对于任意初始状态1,2,3,一定在7步之内保证达到目的状态

可能会有人问,如果初始状态就是目的状态呢?
那么就在7步之前加一步C好了:
C->A->B->A->C->A->B->A

抱歉!评论已关闭.