IT牛人博客聚合

    数学之美不但体现在漂亮的结论和精妙的证明上，那些尚未解决的数学问题也有让人神魂颠倒的魅力。和 Goldbach 猜想、 Riemann 假设不同，有些悬而未解的问题趣味性很强，“数学性”非常弱，乍看上去并没有触及深刻的数学理论，似乎是一道可以被瞬间秒杀的数学趣题，让数学爱好者们“不找到一个巧解就不爽”；但令人称奇的是，它们的困难程度却不亚于那些著名的数学猜想，这或许比各个领域中艰深的数学难题更折磨人吧。

    作为一本数学趣题集， Mathematical Puzzles 一书中竟把仍未解决的数学趣题单独列为一章，可见这些问题有多么令人着迷。

查看全文: http://www.udpwork.com/item/3986.html

    今天又学到一种证明素数无穷多的方法。它是由 Filip Saidak 发现的，论文曾发表在 2006 年的 The American Mathematical Monthly 上。

    首先注意到，两个相邻自然数一定是互质的（否则，假设他们有大于 1 的公因数 k ，则他们的差也能被 k 整除，这显然是不可能的）。现在，取一个自然数 n > 1 。由于 n 和 n + 1 是相邻自然数，因此 n 和 n + 1 是互质的。也就是说，n 的质因数和 n + 1 的质因数完全没有重合，因而 n(n + 1) 至少有两个不同的质因数。类似地，由于

查看全文: http://www.udpwork.com/item/5651.html

    给定一个正方形纸片，用上面这种方法可以折出一个等边三角形。你能看出这是为什么吗？

  

    由对称性，组成等边三角形的前两道折痕显然一样长，我们只需要证明它们之间的夹角是 60 度即可。注意到，如图折叠后将会立即产生直角边是斜边长度一半的直角三角形， 30 度角由此产生。由此可知，前两道折痕和纸片边上的夹角都是 15 度，两折痕之间的夹角自然也就正好是 60 度了。

    这个等边三角形的折法来源于 这里。同一个网站还给出了折出其它正 N 边形的方法，感兴趣的读者可以尝试着证

查看全文: http://www.udpwork.com/item/4269.html

    今天是我第一次听说这个故事。

    1933 年，匈牙利数学家 George Szekeres 还只有 22 岁。那时，他常常和朋友们在匈牙利的首都布达佩斯讨论数学。这群人里面还有同样生于匈牙利的数学怪才——Paul Erdős 大神。不过当时，Erdős 只有 20 岁。

    在一次数学聚会上，一位叫做 Esther Klein 的美女同学提出了这么一个结论：在平面上随便画五个点（其中任意三点不共线），那么一定有四个点，它们构成一个凸四边形。Szekeres 和 Erdős 等人想了好一会儿，没

查看全文: http://www.udpwork.com/item/4994.html

    下面这些文字来源于我在初三数学竞赛课的一份讲义。这节课的主题本是四点共圆，但由此引出了三角形中很多漂亮的性质，让人深感数学之美。在此整理出来，献给所有还在中学读书的读者，以及早已远离中学数学的 80 后。不管大家是否喜爱数学，想必都会被这些奇妙的结论所震撼。

    

    三角形的奇迹首先表现在各个“心”上：三角形内部的每一组有几何意义的线条都交于一点。三条角平分线交于一点，这个点就叫做三角形的“内心”，它是三角形内切圆的圆心；三边的中垂线交于一点，这个点就叫做三角形的“外心”，它是三角形外接圆的圆

查看全文: http://www.udpwork.com/item/5031.html

    很多看上去很显然的结论，其实是需要严格证明的，并且有时候证明相当困难。比方说算术基本定理，每一个数分解质因数的方法都是唯一的。这看上去几乎是显然的，但证明过程需要很多深刻的数论知识。更极端的例子则是 Jordan 曲线定理，即平面上每一条不与自身相交的封闭曲线都把平面分成了里外两部分。这几乎就是一句废话，但要想严格证明起来相当不容易， Camille Jordan 本人的证明最后发现竟然也是错误的。

    最近 MathOverflow 上有人提了一个非常有趣的问题：有那么多结论很显然但证明很困难的定理，那有没有什么结论很不可思议但证明过程却

查看全文: http://www.udpwork.com/item/5405.html

    在这个 Blog 的一篇很老很老的文章里，我曾经讲过一个非常有趣的几何作图问题，这个问题最早是由 D. Pedoe 教授在 1983 年提出的：给定 A 、 B 两点，只用一个生锈的圆规（没有直尺），如何找出一个点 C ，使得 A 、 B 、 C 恰好构成一个等边三角形？所谓“生锈的圆规”，也就是一个被卡住的圆规，它的两脚张角不能改变。我们不妨假设，它只能画出单位大小的圆。1987 年，我国的侯晓荣等人成功地解决了这个问题，并借助复平面理论得到了很多一般的结果，其研究成果《锈规作图论》发表在了《中国科学技术大学学报》上。

    锈规作出等边三

查看全文: http://www.udpwork.com/item/5289.html

    由于某些原因，最近在整理以前的日志。偶然翻到这篇日志时，顺便在 Wikipedia 复习了一下 Arrow 不可能性定理的证明，惊奇地发现这个定理的证明过程非常困难但又非常初等，是一个门槛很低、老少咸宜的思维游戏。虽然不少人都翻译过 Wikipedia 上的这段证明，但我也想自己写一个自己的理解，一来做个笔记，二来也锻炼一下自己的表达能力。

    Arrow 不可能性定理是一个与选举制度有关的定理。选举制度，说穿了就是把所有选民的意见综合成一个全体意见的算法。选民的意见，无非是候选对象在心目中谁优谁劣，完整地反应在选票上，就是候选对象们从优到

查看全文: http://www.udpwork.com/item/4769.html

    公式 h = (1/2)·g·t^2 里， t 头上的平方并不奇怪。显然，物体下落的路程是与重力加速度 g 和时间 t 有关的，高度 h 就由这两个变量决定。注意到 g 是一个加速度单位，是米除以平方秒的形式；为了得出一个以长度为单位的结果，我们必须要消除分母位置上的“平方秒”，因而时间变量 t 必须要以平方的形式出现。

    类似地， E = m·c^2 里的平方也不是凭空而来的。能量的单位是牛乘以米，牛本身又是千克乘以米每平方秒，刨根到底能量的单位就该是 千克·(米^2)/(秒^2) ，正好符合等式右侧“质量乘以速度平方”的量纲。

&n

查看全文: http://www.udpwork.com/item/4323.html

    下面这个精彩的问题来自于刚刚结束的 IMO 2011 中的第 2 题：

    设 S 是平面上包含至少两个点的一个有限点集，其中没有三点在同一条直线上。所谓一个“风车”是指这样一个过程：从经过 S 中单独一点 P 的一条直线 l 开始，以 P 为旋转中心顺时针旋转，直至首次遇到 S 中的另一点，记为点 Q 。接着这条直线以 Q 为新的旋转中心顺时针旋转，直到再次遇到 S 中的某一点，这样的过程无限持续下去。

    证明：可以适当选取 S 中的一点 P ，以及过 P 的一条直线 l ，使得由此产生的“

查看全文: http://www.udpwork.com/item/5554.html

    一个公司里有 n 个员工，其中某些员工之间有“好友”的关系（这是一个对称的关系）。每天早晨来到公司，员工们都会从茶和咖啡中选择一样作为早饮。此时，每个员工都会观察自己的朋友们都在喝啥：如果超过一半的人都在喝茶，第二天他自己也会跟着喝茶；如果超过一半的人都在喝咖啡，第二天他自己就会跟着喝咖啡；如果喝茶喝咖啡的人数各占一半（仅当他有偶数个朋友时才会发生这种情况），则第二天他的决策不变，继续喝自己今天喝的东西。

    由于 n 个员工一共只能产生 2n 种不同的早饮组合，因此总有一天大家喝的东西会和过去的某一天一模一样，从而产生循环。证明：循环的长

查看全文: http://www.udpwork.com/item/4731.html

    某大公司有这么一个规定：只要有一个员工过生日，当天所有员工全部放假一天。但在其余时候，所有员工都没有假期，必须正常上班。这个公司需要雇用多少员工，才能让公司一年内所有员工的总工作时间期望值最大？

    假设一年有 365 天，每个员工的生日都概率均等地分布在这 365 天里。

    你的第一感觉或许是，公司应该雇用 100 多人，或者 200 多人吧。答案或许会让你大吃一惊：公司应该雇用 365 个人。注意，雇用 365 个人并不意味着全体员工全年的总工作时间为 0 ，因为 365 个人的生日都是随

查看全文: http://www.udpwork.com/item/5271.html

    因为忙，不少计划写下来的东西都一直搁置着。其中一个拖了很久都没写的就是 UyHiP 一月的题目 了。这是一道看上去非常困难的算法题目，当时我没能解答出来；看到答案后才恍然大悟，拍案叫绝。这是一道非常少见的算法好题，在这里记下来。

    一个国家里有 N 个公民，这些公民从 1 到 N 依次编号。这是一个民主国家，国家做出的每个决定都需要全体公民投票，每个人必须且只能投一票。

    不过，随着该国家人口数量的增加，这种投票方式的效率越来越低。于是，这个国家实行了一种新的民主制度。每过四年，这个国家将会

查看全文: http://www.udpwork.com/item/4532.html

    最多能在平面上找出多少个点，使得它们两两之间的距离都是整数？当然，我们忽略最平凡的解——所有点都在一条直线上。

    三个点的解显然是存在的，只需要构造一个边长为 1 的等边三角形即可。事实上，满足任意两数之和大于第三数的一组整数都可以成为一个三角形的三条边。寻找含有四个点的解也并不困难，一个长为 4 宽为 3 的矩形就能满足要求。不过，我们还有更小一些的解。最小的解貌似是下面这个等腰梯形：上底、下底分别是 3 和 4 ，两腰都是 2 ，两条对角线都是 4 ，正好也都是整数。

     &n

查看全文: http://www.udpwork.com/item/3903.html

    最近忙于写学年论文，一直没时间更新 Blog 。不过，我却并没有停止在网上闲逛的习惯。这几天会慢慢把最近看到的有意思的东西写下来。今天学到的一个比较有趣的东西就是：平均等待时间往往大于平均间隔时间的一半。

    比方说，有这么一趟公交车，平均每 10 分钟发一班车，但具体的发车时间是很不固定的。如果你在某个时刻来到车站，等到下一班车平均要花多久呢？很多人或许都觉得，平均等待时间应该是 5 分钟，毕竟平均间隔时间是 10 分钟嘛。然而事实上，平均等待时间是大于 5 分钟的。这是因为，10 分钟的发车间隔只是一个平均值，实际间隔有时是几分钟，有时

查看全文: http://www.udpwork.com/item/5088.html

    假设 X 、 Y 是两个有限集合，f:X→Y 和 g:Y→X 是两个函数。求证：复合函数 g∘f 和 f∘g 拥有相同数量的不动点（也就是说 g(f(x)) = x 和 f(g(y)) = y 的解的个数相同）。

    下面先提供一个“正常”的解法。观察函数 g∘f 的不动点，可以看出它有以下两个性质：首先，如果某个 x 是 g∘f 的不动点，即 x = g(f(x)) ，那么 f(x) = f(g(f(x)))，这就说明 f(x) 是 f∘g 的一个不动点；另外，如果 x1 和 x2 是 X 中两个不同的不动点，则函数 f 不可能把它们映射

查看全文: http://www.udpwork.com/item/4971.html