硬币游戏

zhiqiangJuly 27, 2008 科学精华区

Alice和Bob两人玩一种硬币游戏。游戏在一个 $2\times2$ 的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一枚硬币，接着Bob可以选择将棋盘旋转90，180或者270度，也可以什么都不做。

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

如果Alice在游戏过程中无法看到棋盘上的银币，也不知道游戏刚开始的状态，甚至不知道Bob每回合是否旋转了棋盘，那么Alice有策略能够获得胜利么？他的最优策略是什么？

接下来我们推广这个游戏。共有 $n$ 枚硬币，分别放在一个正 $n$ 边形棋盘的顶点上。每回合Alice可以翻转任何一些银币，Bob则可任意以 $n$ 种不同的方式(旋转 $360/n$ 的倍数角度)之一旋转棋盘。游戏一直到所有硬币正面朝上或者反面朝上，Alice获得胜利。

这时候Alice还能取胜吗？

解答在此，但强烈推荐独立思考此题，特别是 $n=4$ 的情况。

via Sariel’s blog

查看更多关于游戏, 策略的内容。

22条留言 -> 跳到留言表格

At 2008.07.27 20:38, LT said:

这就是传说中的unobservable automaton吧

[Reply]
At 2008.07.27 21:05, Goling said:

本人没什么数学知识，只是不太理解这道题：
Alice是可以翻转任意一枚硬币的，那Bob旋转棋盘对Alice有什么影响？
因为Bob无论怎么旋转棋盘，Alice都可以随意选择她想翻转的硬币啊？

见笑了，不好意思。

[Reply]
- At 2008.07.27 21:13, zhiqiang said:
  
  这个前面4个硬币的情形不需要什么数学知识，相当于一个智力题。
  
  Bob旋转棋盘会改变硬币的位置。
  
  注意Alice她不知道她想翻哪枚硬币，她不知道初始状态，也不知道Bob翻转到了哪个位置。
  
  [Reply]
At 2008.07.28 12:42, 布衣 said:

如果Alice的视线会受阻，无法看完整个1/2转盘，就永远转180度好了，假如有2个对称的视线死角他们放的是2枚不同的硬币，那么Alice将不可能赢。
如果视线不受阻，而且手能购得到，这个就不是问题了吧，就翻一个面不就可以了。

[Reply]
- At 2008.07.28 12:53, zhiqiang said:
  
  我没看明白你的推理。但是Alice在第一种情况总是可以赢的，而且七步之内都能赢。方法也很简单。
  
  这个问题困难在于第二部分 $n$ 枚硬币的情况。
  
  [Reply]
  - At 2008.07.28 16:26, FDY1045 said:
    
    你说一下第一种情况的解
    
    [Reply]
    - At 2008.07.28 17:34, zhiqiang said:
      
      这么好的题目，直接把答案说出来多没意思啊。大家自个儿慢慢想。等我把第二部分想清楚了再一起弄出来。
      
      [Reply]
At 2008.07.28 13:30, achilleus said:

第二部分枚硬币的情况是否可以从 n = 2^m (m为正整数)入手？
讨论情况比较多一时想不清楚，可能可以。

[Reply]
At 2008.07.29 11:00, overwindows said:

关于第一个问题
最坏情况下的动作：交叉翻转->同行翻转->随意翻转一个->同行翻转->交叉翻转

[Reply]
At 2008.07.29 11:11, overwindows said:

不好意义，貌似漏了两个"交叉翻转"
交叉翻转->同行翻转->交叉翻转->随意翻转一个->交叉翻转->同行翻转->交叉翻转

[Reply]
- At 2008.07.29 18:28, zhiqiang said:
  
  这个是对的。
  
  一般的情形呢？
  
  [Reply]
- At 2008.07.29 21:26, xdcrypto said:
  
  貌似你给的这个办法不可行的，交叉翻转是指先对角交换然后再依次翻转吗？？还有就是这个算法的解空间有多大，要是利用传统的概率计算出信息熵，不知道可行？？
  
  [Reply]
  - At 2008.07.30 11:34, zhiqiang said:
    
    交叉翻转就是指翻转某对角的两个硬币。
    
    什么信息熵，不太明白，你可以试一试。
    
    [Reply]
    - At 2008.08.22 17:31, dailiang said:
      
      这个问题背后的物理意义是什么呢？这样的问题在什么地方可以用上？
      
      [Reply]
At 2008.07.29 12:43, raincatss said:

传说中的量子博弈

[Reply]
- At 2008.07.29 16:19, sunshine said:
  
  怎么解释
  
  [Reply]
- At 2008.07.29 21:27, xdcrypto said:
  
  百度了一下：关于量子博弈。
  
  量子博弈论——连续变量博弈的量子化、信息的不对称
  
  在我们给出具体的量子化方法的时候，我们可以先来看看已有的分立变量博弈在量
  子化的时候有没有什么东东是可以借鉴到连续变量博弈的。我们首先需要明确一下
  经典博弈中策略的“经典性”到底是个什么意思，虽然我们以前在谈这个问题的时
  候把它当作了某种想当然的东东。在这里，策略的“经典性”的意思就是说，两个
  不同的策略在原则上是完全可区分的；这就是为什么在前面提到的分立变量博弈的
  量子化中，我们采用互相正交的量子态代表经典博弈中所有可能的不同结果。这一
  原则应该在量子化连续变量博弈的时候被保持，这样一来，由于这里出现了无穷个
  经典策略从而有无穷种可能的结局，我们不可避免地要采用无穷维的量子体系来负
  载着所有可能的经典结局。
  在Physics Letters A 306, 73 (2002)中，我们给出了第一个基于上述思想的连续
  变量量子博弈模型。并且对一个叫做Cournot’s Duopoly的博弈研究了它的量子版
  本的性质。毫不以外的，量子的Cournot’s Duopoly的性质随着博弈者之间的纠缠
  程度的增加，表现出越来越明显的超越经典博弈的优越性；当达到最大纠缠时，它
  可以给出最好的结果。在这一点上，这个特定的连续变量量子博弈和“囚徒困境”
  是有些类似的。
  我们在接下来的一个工作 [Phys. Rev. E 68, 016124 (2003)]中，我们考察了信
  息的不对称性对这个连续变量量子博弈的影响。之所以要考虑信息的不对称的原因
  是，在现实生活中，博弈参与者们可能并不对所有的相关信息都有完整和正确的理
  解，尤其是当他们的完整性和正确性不等时，将极大的影响到博弈的结果和性质。
  我们发现，对于这类情况，如果信息的不对称程度太大的话，量子纠缠将是有害的
  ，它会降低收益，甚至会使得量子博弈比经典博弈更差。
  
  [Reply]
At 2008.07.30 12:13, 火电厂 said:

没说清楚bob是否知道alice要翻哪两个

[Reply]
- At 2008.07.30 12:36, zhiqiang said:
  
  Ｂｏｂ知道Ａｌｉｃｅ的策略。
  
  不知道也无所谓，策略嘛，当然要考虑最坏的情况。
  
  [Reply]
At 2008.08.10 22:14, zyzi_orc said:

其实很简单，你们被题目误道了，BOB不是可以旋转棋盘么，但没说是水平旋转还是垂直旋转，所以等Ａｌｉｃｅ翻过第一次之后，BOB可以将棋盘在空间内垂直旋转90度就行了

[Reply]
At 2008.08.22 18:54, 天山新怪 said:

1.对角翻
2.平行翻
3.对角翻
4.单个翻
5.对角翻
6.平行翻
7.对角翻

%%%%%百分之一百ok%%%%%

一开始以为没解，仔细一想，就那么几种情况！

[Reply]
At 2008.10.02 19:24, 路途就是目标 » Blog Archive » 我的“情人们” said:

[...] 屋里有一块白板还是很好的。我几乎每天会在它上面写上两三版。特别是与别人讨论问题的时候，用上白板使得交流更加有效。我时不时地会在白板上做些好玩的题，比如这个翻硬币游戏。我觉得自己一天中很快乐的一段时间是与PG同学一起讨论在白板上讨论问题的时候。不仅是因为我们讨论的问题一般会比较好玩，还由于PG同学数学超好(高考我们省的单科最高分) ，从他那里我总可以看到很多好玩美妙的东西。 [...]

[Reply]

« 算法百科全书 - Encyclopedia of Algorithms

中国崛起策三十一：西方媒体操纵大众心理的秘密 »

硬币游戏

查看更多关于游戏, 策略的内容。

22条留言 -> 跳到留言表格

阅微堂