出典:IBM Ponder This。
涉及知识:情报/密码学
说Alice和Bob两人被迫参加一个邪恶的赌局,规则是这样的:
Alice猜一个数0或1并公开,然后Bob猜一个数0或1并公开,然后庄家翻开事先已经藏好写在纸上的一个数字0或1,只有这三个数都相等时,Alice和Bob才视为赢。
如果Alice和Bob两孩子特别傻,就闷头乱猜,那么一局里赢的概率显然只有25%。
如果Bob比较聪明,看Alice猜什么自己就跟着猜什么,那么一局里赢的概率立刻会上升到50%,效率高多了。
然而,如你所知,上文里的数字都是概率,即使50%概率获胜也可能屡战屡败惨死。
明天比赛就要开始了,今晚Bob得到了一个振奋人心的好消息:
明天比赛开始后,Bob有内线,可以拿到庄家藏好的纸上所有的情报!
但是比赛一旦开始,Alice和Bob就再也无法交流,只能眼睁睁的看着他们选择了0还是1。
那么,Alice和Bob开始讨论,他们有什么办法,可以确保在明天的9局比赛里,赢下至少4局呢?
哦,这个问题并不复杂,Bob大可以放弃第1357局,不管Alice猜了什么,Bob都明确给出下一局庄家藏起来的数字,然后第2468局Alice和Bob只要一起猜这个数字,就可以安定的拿下来4局,可喜可贺,可喜可贺。
多么好的策略,但还是不够。
明天的9局比赛里,Alice和Bob要至少拿下6局,才能逃出升天。
现在,商量一个办法,让两个人都能活命吧。
涉及知识:情报/密码学
说Alice和Bob两人被迫参加一个邪恶的赌局,规则是这样的:
Alice猜一个数0或1并公开,然后Bob猜一个数0或1并公开,然后庄家翻开事先已经藏好写在纸上的一个数字0或1,只有这三个数都相等时,Alice和Bob才视为赢。
如果Alice和Bob两孩子特别傻,就闷头乱猜,那么一局里赢的概率显然只有25%。
如果Bob比较聪明,看Alice猜什么自己就跟着猜什么,那么一局里赢的概率立刻会上升到50%,效率高多了。
然而,如你所知,上文里的数字都是概率,即使50%概率获胜也可能屡战屡败惨死。
明天比赛就要开始了,今晚Bob得到了一个振奋人心的好消息:
明天比赛开始后,Bob有内线,可以拿到庄家藏好的纸上所有的情报!
但是比赛一旦开始,Alice和Bob就再也无法交流,只能眼睁睁的看着他们选择了0还是1。
那么,Alice和Bob开始讨论,他们有什么办法,可以确保在明天的9局比赛里,赢下至少4局呢?
哦,这个问题并不复杂,Bob大可以放弃第1357局,不管Alice猜了什么,Bob都明确给出下一局庄家藏起来的数字,然后第2468局Alice和Bob只要一起猜这个数字,就可以安定的拿下来4局,可喜可贺,可喜可贺。
多么好的策略,但还是不够。
明天的9局比赛里,Alice和Bob要至少拿下6局,才能逃出升天。
现在,商量一个办法,让两个人都能活命吧。