IPT 201310 赌徒问题

作者:, 发表于

2013年九月份的IBM Ponder This问题(英文地址):

Alice和Bob与赌场玩一个赌博游戏:

每轮由Alice先亮出0/1,之后是Bob亮出0/1,赌场(Casino)最后亮出0/1。如果三个人的牌数相同(都是0或都是1),则Alice&Bob赢得此轮,否则赌场赢得此轮。由于Casino是最后出的,为防它作弊在赌局开始前casino需要将它以后每轮的出牌按顺序事先写好并密封起来。

现在,假设Bob在赌局开始前能偷看到Casino密封的出牌。他在偷看之前可以和Alice商量好出牌策略,但一旦偷看后就不能再和Alice有任何交流。

容易看出Alice和Bob有策略在最坏情况下也能赢得至少一半轮次的赌局,策略为:Alice在奇数轮随机出,偶数轮出上一轮Bob出的数;Bob在奇数轮出下一轮Casino要出的数,偶数轮出本轮的数。这样他们至少能赢得所有偶数轮。

问题:进行9轮赌局,请设计策略,保证Alice和Bob在最坏情况下也能赢至少6局。

更进一步的:当赌局轮数n趋于无穷大时,他们能不能做得更好?此时最坏情况下的最大获胜的比例是多少?

似乎不简单。待我好好想想。

Q.E.D.


上一篇:IPT 201307 八个数中任三数之和不等2013年7月3日
一个八面体骰子,每一面都有一个数。扔三次,三个数之和最多有120种可能性。若要使这120种可能性都不相同,八面体八个数中最大数最小可能是多少?

下一篇:神奇的椭圆迭代问题2013年10月13日
平面上任何一个多边形(可自交),不断取各边的中点重新连线,同时按比例放大,往复操作最终会趋近于一个椭圆。人人网上有不少同学对这个问题进行了不同的扩展,有些角度和结论非常有趣。


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。