趣题:存在三个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

网友来信:另类线段等分法与距离平方和问题的扩展

    在介绍尺规作图等分圆面积时,我提到了利用尺规作图将线段AB任意等分的问题。在初中课本上,这个问题的标准做法如下:

 
 
  1. 过A点向另一方向做射线l;
  2. 从A点开始,用圆规在射线l上截取n个等距的点X1, X2, …, Xn
  3. 连接Xn和B;
  4. 分别过X1, X2, …, Xn-1作直线平行于XnB。

    那么,这些平行线与AB的交点即为AB的n等分点。

Read more…

趣题:选取最多的子集使得任两子集恰有一个公共元素

    这里有一个有趣的问题:在集合{1, 2, …, n}中选取尽可能多的子集,使得任意两个子集的交集有且仅有一个元素。例如,当n=7时,选取{1,2,3,4}、{4,5,6,7}、{1,7}这3个集合可以满足条件。子集数还可以更大一点吗?最大是多少?给出一种构造,然后证明这个数目不可能更大了。

    当n=7时,仅仅取3个子集实在是太弱了。一种最简单的办法就可以让子集数达到6,只需取{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}即可。再仔细观察,我们发现这个结果还可以进一步改进:我们还可以再往里面添加进一个子集{1},使得这7个子集两两间仍然恰有一个公共元素。这下我们似乎不能再往里面添加任何新子集了。我们还可以做得更好吗?一个新的思路是在{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}里面加上{2,3,4,5,6,7},这同样可以让子集数达到7个,可惜我们仍然无法再往里面添加新的子集了。经过若干次尝试后,我们逐渐开始确信,在集合{1, 2, …, n}里面最多只能选出n个两两恰有一个公共元素的子集,并且构造方法无外乎上面两种。这一猜想不但与直觉相符,而且貌似也很好证明。你或许会从一些看似很直观的结论出发开始证明:“显然不可能有两个大小为1的子集”,“选取多个元素个数大于2的子集显然不划算”……但牛B就牛B在,偏偏就有这样一种子集数为n的取法,每个子集里都有不止两个元素,但仍然保证任意两个子集间恰有一个公共元素:

{1,2,3}、{1,4,5}、{1,6,7}、{2,4,7}、{3,4,6}、{3,5,7}、{2,5,6}

    这一个例子对我们的猜想足以构成威胁:子集数为n真的已经到极限了吗?证明结论有那么容易吗?看来,情况貌似比我们想象中的要复杂得多。

Read more…

经典证明:列表染色与可选择数(下)

    我们上次说到,不是所有的平面图都是可4选择的。于是人们接着猜想,是不是所有平面图都是可5选择的呢?1994年,Carsten Thomassen证明了,所有平面图都是可5选择的。这个证明极其简单,论文全文不足两页,证明过程仅十多行。证明对平面图中的区域数n施归纳。有趣的是,归纳的命题比我们待证明的命题要强得多,否则原命题反而证不到。
    为简便起见,我们假设平面图是一般的,它没有同属于四块区域的交界点,也没有中空的“洞”。加入这些条件不会让问题变得更简单,因此这些假设都是合理的。下面再假设最外面那一圈区域(与“外部空间”相邻的区域)有s个,它们彼此相连构成了一个环,我们按逆时针顺序把它们分别记为P_1, P_2, P_3, …, P_s。无妨设P_1和P_2的颜色分别为1和2。下面我们证明一个比原命题更强的结论:若最外面那s个区域的颜色列表中至少有三个颜色,其余那些(被围在内部的)区域的颜色列表中有五个颜色,则一定存在合法的列表染色。当区域数n足够小时结论显然成立。

Read more…