趣题:用 26 次机会找出任意一张对方想要的牌

看守打算和 A 、 B 两名囚犯做一个游戏。首先,看守从一副牌中取出大小王,将剩余的 52 张牌洗好,并在桌子上从左至右地把它们摆成一排,每张牌都是正面朝上。然后,看守让囚犯 A 来到桌前,允许囚犯 A 观察牌面,并交换其中两张牌的位置。接着,看守将囚犯 A 关回牢房,把所有牌全都翻到背面朝上(但位置不变),让囚犯 B 来到桌前。看守随便报出一张牌的花色和点数(比如“梅花 3”),要求囚犯 B 找出这张牌。囚犯 B 每次可以翻开任意一张尚未翻开的牌,但一共只有 26 次机会。如果囚犯 B 在这 26 次机会之内找到了看守想要的牌,则两名囚犯赢得游戏,无罪释放;如果囚犯 B 翻开了 26 张牌之后,还没找到看守想要的牌,则两名囚犯输掉游戏,立即死刑。在整个游戏开始之前,两名囚犯可以商量一个策略;游戏开始后,两人就不能有任何其他形式的交流。果不其然,这又是一个关满了数学天才的监狱。两名囚犯碰头后,很快就商量出了一种必胜的策略。这种必胜的策略是什么?

Read more…

趣题:怎样向别人证明两个图不同构?

若干个顶点(vertex)以及某些顶点对之间的边(edge)就构成了一个图(graph)。如果图 G 和图 H 的顶点数相同,并且它们的顶点之间存在着某种对应关系,使得图 G 中的两个顶点之间有边,当且仅当图 H 中的两个对应顶点之间有边,我们就说图 G 和图 H 是同构的(isomorphism)。直观地说,两个图是同构的,意思就是它们本质上是同一个图,虽然具体的画法可能不一样。下面的两个图就是同构的。其中一种顶点对应关系是: 1 – a, 2 – c, 3 – d, 4 – b, 5 – e, 6 – g, 7 – h, 8 – f 。

目前,人们还没有找到任何高效的算法,能迅速判断出两个图是否同构。在普通计算机上,判断两个图是否同构,这需要花费大量的时间。因此,人们经常以图的同构为例,来解释复杂度理论和现代密码学中的诸多概念。

假设你家里的计算机十分强大,能很快判断出两个图是否同构,还能在两个图确实同构的情况下,给出一种顶点对应关系。但你的同桌家里的计算机却非常弱,没法做什么大型运算。课堂上,老师向全班展示了两个很复杂的图,不妨把它们叫作图 G 和图 H 。老师布置了一个特别的选做题:判断出这两个图是否同构。每个同学都可以提交答案,答案里只需要写“是”或者“不是”即可。按时提交答案并答对者,期末考试会获得 5 分加分;按时提交答案但答错了的,期末考试成绩将会倒扣 30 分;不参与此活动的同学,期末考试既不加分也不扣分。显然,每个同学都不敢随意提交答案,除非百分之百地能保证自己获得的答案是正确的。回到家后,借助家里的超级计算机,你很快判断出了这两个图是同构的。你给你的同桌发送了信息:“我已经算出来了,这两个图是同构的。”但是,你的同桌却回复说:“你不会是骗我的吧?”你打算怎样说服他,这两个图确实是同构的呢?

Read more…

趣题:如何在数据库中秘密地查询隐私数据

    日常生活中经常会出现这样的场景:你想在数据库上查询某个东西,但却不希望留下线索,让别人知道你查询了什么。比方说,投资人可能会在数据库上查询某支股票的信息,但却不希望任何人知道他感兴趣的股票究竟是哪一支。看上去,似乎唯一的办法就是把整个数据库全部拷回家。然而,这些数据往往都拥有非常庞大的体积,全部拷走通常都是很不现实的;另外,考虑到数据内容的隐私性和数据本身的宝贵价值,数据的持有者通常也不允许其他人把整个数据全盘拷走。不过,随着分布式数据库的广泛应用,上面的难题有了一个两全其美的好办法:假设有两个内容完全相同的数据库,投资人可以先在第一个数据库上执行一个不会透露目的的查询,再在另一个数据库上执行另一个不会透露目的的查询,两次查询结合起来便能推出想要的结果。只要没有人刻意去收集并且对比两个数据库的查询记录,那么谁也不会知道投资人真正想要查询的是什么。在这个背景下,我们有了下面这个有趣的问题。

    服务器随机产生了一个 {1, 2, …, 100} 的子集 S ,并且同时发送给了 A 和 B 两名前台工作人员。 A 、 B 两名前台都接受其他人的提问,但为了保护数据,两个人都只能用“是”或者“否”来回答问题,并且都不允许同一个人重复提问。你非常关心某个数 n 是否在这个子集里。其实,你本来可以直接问 A 和 B 中的任何一个人“数字 n 是否在集合 S 里”,但是这样一来,对方就知道了你想要查询的是什么。为此,你可以向 A 和 B 各问一个问题(结合两人的回答便能推出集合 S 里是否包含数字 n ),但却不能让 A 和 B 当中的任何一个人知道你查询的是哪个数(我们假设 A 、 B 两人不会串通起来,把他们各自收到的问题联系在一起)。事实上,你需要保证 A 和 B 两人都不能从你的问题中获取到任何信息,也就是说,对于 A 和 B 当中的任何一个人来说,各种问题出现的概率不会随着 n 值的改变而改变。再换句话说,如果 n 的值变了,那么 A 和 B 各自将会听到的问题应该拥有和原来相同的概率分布。

Read more…

跨越千年的RSA算法

    数论,数学中的皇冠,最纯粹的数学。早在古希腊时代,人们就开始痴迷地研究数字,沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后,几千年来的数论研究成果突然有了实际的应用,这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》,但受篇幅限制,只有一万字左右的内容。其实,从数论到 RSA 算法,里面的数学之美哪里是一万字能扯完的?在写作的过程中,我查了很多资料,找到了很多漂亮的例子,也积累了很多个人的思考,但最终都因为篇幅原因没有加进《程序员》的文章中。今天,我想重新梳理一下线索,把所有值得分享的内容一次性地呈现在这篇长文中,希望大家会有所收获。需要注意的是,本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释,一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述,可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后,希望大家能够积极指出文章中的缺陷,我会不断地做出修改。

======= 更新记录 =======

2012 年 12 月 15 日:发布全文。
2012 年 12 月 18 日:修改了几处表达。
2021 年 9 月 13 日:根据 Chang 的指正做了修改。

======== 目录 ========

(一)可公度线段
(二)中国剩余定理
(三)扩展的辗转相除
(四)Fermat 小定理
(五)公钥加密的可能性
(六)RSA 算法

Read more…

趣题:八根并排放置的水管

    下面这个有趣的问题来自于 2012 年 4 月的 IBM Ponder This 谜题

    有 8 根很长的并且颜色不同的水管并排放在一起, A 、 B 两人分别位于这些水管的两端。两个人手中各有若干根很短的橡皮管,他们可以用这些橡皮管任意连接自己这一侧的水管口。 A 的旁边还有一个水龙头, A 可以用橡皮管把水龙头与自己这一侧的其中一个水管口相连。

    A 、 B 两人各将获得一个五位 01 串,然后两人可以根据自己手中的 01 串来连接水管口。当 A 打开水龙头后,容易看出,水必然会从其中一侧流出。两人需要保证,如果两人手中的 01 串相等,则水从 A 的一侧流出,否则水从 B 的一侧流出。他们事先可以商量一个策略,但游戏一旦开始,两人一旦拿到各自的 01 串之后,就不允许再交流了(因此两人都不知道对方手中的 01 串是什么)。请你想出一个能保证两人获胜的策略。

Read more…