经典证明:为什么n=5时不存在Langford数列?

    还记得小时候有一道经典奥数题,大概是让你把两个数字 1 、两个数字 2 、两个数字 3 和两个数字 4 排成一个 8 位数,使得其中两个数字 1 之间正好夹着 1 个数字,两个数字 2 之间正好夹着 2 个数字,两个数字 3 之间正好夹着 3 个数字,两个数字 4 之间正好夹着 4 个数字。稍作尝试便可得出正确答案: 4, 1, 3, 1, 2, 4, 3, 2 。如果把逆序后的数列视作本质相同的数列,那么上面这个答案是唯一的。这个问题是由 C. Dudley Langford 在 1958 年提出的,因此我们把它叫做 Langford 数列。

    当 n = 3 时, Langford 数列也是唯一的: 2, 3, 1, 2, 1, 3 。我小时候曾经没日没夜地试图寻找 n = 5 时的 Langford 数列,结果却怎么也找不到。后来才知道, n = 5 时的 Langford 数列根本就不存在。这是为什么?你能证明这一点吗?

Read more…

经典证明:为什么n=5时不存在Leech树?

    在一棵树中,任意两个顶点之间的路径都是唯一的。如果一棵树有 n 个顶点,那么这棵树总共会有 n(n-1)/2 条路径(每两个顶点都会确定出一条路径来)。 1975 年, John Leech 提出了这么一个问题:有多少顶点数为 n 且边上带权的树,使得图中所有 n(n-1)/2 条路径的权值之和正好是 1, 2, …, n(n-1)/2 ?Leech 本人给出了五个这样的例子,其中四个如下图所示,顶点数 n 分别为 2 、 3 、 4 、 4 。第五棵满足要求的树拥有 6 个顶点,把它找出来将会是一个不小的挑战,感兴趣的读者不妨尝试一下,本文最后会公布答案。 Leech 注意到了 n = 5 时是无解的,但却并没有给出一个解释。

      

    1977 年, Herbert Taylor 给出了一个非常漂亮的解释:如果一棵树满足上述要求,那么顶点数 n 一定是形如 m2 或者 m2 + 2 的数。让我们来看一看这个精妙的证明。

Read more…

趣题:同时等分三角形周长和面积的直线

    求证:对于任意一个三角形,一定存在一条直线,它把这个三角形的周长和面积同时分成了两等分。

 
 
    大家知道,三角形的三个内角的角平分线一定交于一点,这个点就是三角形的内心,它到三角形三边的距离是相等的。一个令人吃惊的结论是,经过内心的直线如果平分了三角形的面积,就一定平分了三角形的周长!

      

    如图, I 是三角形 ABC 的内心, ID 、 IE 、 IF 是 I 到三角形三边的垂线段,它们的长度是相等的,不妨把这个长度值记作 r 。假设直线 PQ 经过点 I ,并且平分三角形的面积。这说明, PA · r / 2 + AQ · r / 2 = PB · r / 2 + BC · r / 2 + CQ · r / 2 ,也就是 PA + AQ = PB + BC + CQ 。因此,直线 PQ 也平分了三角形 ABC 的周长。

Read more…