趣题:存在三个Fibonacci数a,b,c使得a^2+b^2=c^2吗?

问题1: 请找出所有满足a^2 + b^2 = c^2的三元组(a,b,c),其中a、b、c三个数都是Fibonacci数。
答案: 你被忽悠了。注意到一组勾股数中绝对不可能有相等的数,而对于任意的m < n < p,以Fm、Fn、Fp为边长的三角形都不存在,因为Fm + Fn ≤ Fn-1 + Fn = Fn+1 ≤ Fp始终成立。

问题2: 求以(Fn, Fn+1, Fn+2)、(Fn+3, Fn+4, Fn+5)、(Fn+6, Fn+7, Fn+8)、(Fn+9, Fn+10, Fn+11)为顶点的四面体的体积,其中Fn表示第n个Fibonacci数。
答案: 你又被忽悠了。事实上,这个四面体根本就不存在。事实上,对任意m、n、p、q,以(Fm, Fm+1, Fm+2)、(Fn, Fn+1, Fn+2)、(Fp, Fp+1, Fp+2)、(Fq, Fq+1, Fq+2)为顶点的四面体都不存在,因为它们都落在平面x+y=z上,四个点共面,所构成的四面体体积总为0。

来源:http://www.cut-the-knot.org/blue/FibonacciQuickies.shtml

Harvard-MIT Mathematics Tournament 2009: Guts Round

摘录几道题目。

计算1·2^2 + 2·3^2 + 3·4^2 + … + 19·20^2
原式 = (1^3 + 2^3 + … + 20^3) – (1^2 + 2^2 + … + 20^2) = 44100 – 2870 = 41230

求2^x = 3^y – 1的所有正整数解
x=1时(1,1)是一个解;当x>1时,方程模4后左边永远等于0,右边则是(-1)^y – 1,可知y为偶数。令y=2z,那么有2^x = (3^z – 1)(3^z + 1),这就要求3^z-1和3^z+1都是2的幂;但它们只相差2,因此它们只有可能是2和4,于是z=1,即原方程的另一个解为(3,2)。

圆周上有2008个点。选择两个点连成一条线,再选另外两点连一条线,这两条线段相交的概率为多少?
给定四个点,在三种连接方案中恰有一种会发生相交。取遍所有C(2008,4)种组合,相交的总情况数总是占了1/3,因此所求的概率就是1/3。

Read more…

从“迷失的8”到生成函数:小数展开的秘密

    小学时经常在计算器上面按12345679这个神秘的8位数。这个数牛就牛在,它乘以9的结果正好等于111111111。你可以在计算器上输好12345679,然后问MM“你的幸运数字是多少”;如果她说“7”,你就在计算器上按“乘以63”,计算器上将会显示出清一色的7字,看上去无比壮观。
    假如123456789×9=1111111111的话,我倒不会觉得奇怪。网上流行过一个火星帖子,写了一大堆诸如111111111 * 111111111 = 12345678987654321的式子来展示数学之美,以至于大家会认为123456789×9的结果也一定是一串很有规律的数字。因此,如果我不在这里说一句123456789×9其实并不等于1111111111的话,估计很多人都发现不了问题。事实上,123456789×9=1111111101,偏偏就差一个“1”。而怪就怪在,去掉被除数中的数字“8”,偏偏又有了12345679×9=111111111,一个极其别扭的算式反而得到了完美的结果。不要让你的直觉被数学之美所蒙蔽,数学上有大量出人意料的、看上去很不对称的结论。
    为什么偏偏要少一个“8”呢?难道这真的是算术中的一个不可抹去的疤痕?我们急需要寻求一个解释,填补上算术中的这个不和谐的“漏洞”。一种解释是,我们看到了123456789×9=1111111101并不美观,想要对其进行改造,进而得到(123456789+1)*9 = 1111111101+9 = 1111111110,于是(123456789+1)*9/10 = 12345679*9 = 111111111。用这种办法的确可以解释“迷失的8”,不过这个解释并不漂亮。为了寻求一个更好的解释,我们来看一看111111111和9的关系。

Read more…

密码学协议举例(五):两个人能够在电话上打牌吗?

    密码学的应用范围非常广泛。每一样简单的社交活动里都有很大的学问。考虑这样一个问题,两个人想通过一部电话打牌,但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议,并且保证游戏的公正性呢?
    扑克牌的信息隐蔽性带来了很多与密码学协议相关的有趣问题。两个象棋大师可以在洗澡间一边冲澡一边大喊“炮八平五”、“马八进七”,一对围棋情侣可以在床上一边亲热一边呻吟“点三三”、“拆二”。等事情办完了,一盘精彩的棋局或许也就结束了。这些棋类游戏之所以可以“盲下”,就是因为在棋类游戏中,双方的局面信息都是完全公开的。不过,打牌就是另外一码事了。你说你出方片7,我怎么知道你有一个方片7?事先发牌?那谁来负责发牌呢?怎样发牌呢?难道我告诉你“发到你手中的是两张3一张5一张8一张9”?这样一看,两个人“盲打扑克牌”似乎是不可能的了,要么需要借助道具,要么需要第三者的帮助。不过,运用密码学知识,我们可以设计一套扑克牌协议,该协议能够实现随机的、隐蔽的、公平的发牌,并且不需要其它东西的帮助。我们以一手五张牌为例,说明如何实现“两人各摸五张牌”的程序。

Read more…

密码学协议举例(四):秘密数字的比较

    让我们来看一个很实用的问题:A和B两位女士希望知道她们俩哪个年龄大,但又都不愿意透露自己的年龄。有什么方法能够让她们在不泄露年龄的情况下比较出年龄大小呢?我们假设双方都是诚实可信的。她们会严格遵守协议并且不会撒谎。她们唯一不希望做的仅仅是泄露自己的年龄。
    不妨设A的年龄为a,B的年龄为b。为简便起见,假设这两个数都是21到30之间的整数。下面这个协议可以让双方比较出a和b的大小,而不透露a和b的实际值。这个协议也不需要第三方的参与。
    协议开始前,B生成一对RSA钥匙,例如n=3233, e=17, d=2753。首先,A选取一个大随机数x,比方说1117。A用B的公开钥匙给随机数1117加密,得到密文1652。A把1652减a的值发给B。如果A是一个22岁的漂亮MM,那么B实际接收到的数就是1630。
    接下来,B尝试用私人密钥来恢复x。由于B不知道a是多少,于是B枚举所有21到30之间的整数,用私钥对

1651, 1652, 1653, 1654, 1655, 1656, 1657, 1658, 1659, 1660

    这10个数分别解密,得到的结果分别为

527, 1117, 1499, 2606, 3026, 3169, 3043, 1353, 1053, 1633

Read more…