IT牛人博客聚合

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

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

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

    想像一个圆盘在地面上滚动一周，那么圆周上一点所形成的轨迹就叫做旋轮线（或者摆线）。旋轮线下方的面积是多少，这是一个非常有趣的问题。据说， Galileo 曾经用一种非常流氓的方法，推测出了旋轮线下方的面积。他在金属板上切出一块圆片，再在金属板边缘剪下这个圆形所对应的旋轮线，把它们拿到秤上一称，发现后者的重量正好是前者的三倍。于是，他推测，半径为 r 的滚轮所产生的旋轮线，其下方的面积就是 3πr2 。

    

    不过，今天我第一次知道，这个结论对于正多边形是同样成立的。

  

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

    一个小镇上即将进行大选，候选人有 m ≥ 3 个，选民一共有 n 人。选举时，每个选民在选票上写下一个候选人的名字，然后由计算机根据某种选举机制算出大选的获胜者来。如果把 n 个选民的选票依次记为 x1, x2, ..., xn 的话，那么选举机制的算法其实就是一个映射到 {1, 2, ..., m} 的函数 f(x1, x2, ..., xn) 。

    为了保证选举程序的公平性，让每个人手中的选票都能发挥作用，政府提出了“差异性原则”：如果每个人的选票都变了，那么竞选的获胜者也应当改变。也就是说，如果对于所有的 i 都有 xi ≠ yi

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

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

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

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

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

    今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。

    假设初始时有 A 、 B 两位玩家，他们分别位于两个孤

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

    数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质，其中一个性质是，每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说，如果把第 n 个 Fibonacci 数记做 Fn ，那么有：

      Fn+1 · Fn+1 - Fn · Fn+2 = (-1)n

    今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。

 

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

    有一个正方形的房间，房间的四壁都是镜子。房间里有一个天使和一个恶魔。假设房间是一个单位正方形 [0, 1] × [0, 1] ，那么天使和恶魔便是这个正方形内的两个点 (a, b) 和 (c, d) 。恶魔想要在原地发射致命激光杀死天使（激光可以无限地在镜子间反射）。天使可以根据恶魔的位置，预先在房间里放置一些守卫为自己挡住激光（守卫实际上也是一个个点）。当然，天使可以在自己周围密密麻麻地放一圈守卫，围成一个封闭的圆形，从而让恶魔不管朝什么方向发射激光，最终都无法击中天使。我们的问题是，能把守卫的数量减少到可数个点吗？能把守卫的数量减少到有限个点吗？

  &nbs

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

    同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了另一篇论文，给出了实数集不可数的另一种证明方法。此后，这个简单到不可思议的证明不断地震撼着每一个初学集合论的人：

    事实上，实数区间

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

      

    左图是一个凹多边形，而且凹得相当厉害。作为一个完美主义者，我很难容忍这么一个图形，总想着要把凹进去的部分翻出来，把它还原为一个凸多边形。不幸的是，翻折之后的结果仍然不是凸多边形，图中又产生了新的凹陷。于是，我们想继续把凹进去的部分往外翻，直到整个图形变成凸多边形为止。问题是，这个过程有完吗？换句话说，我们一定能通过有限多步翻折，把凹多边形变成凸的吗？

    这个问题有着非常纠结复杂的历史。这个问题最早可能是由数学家 Paul Erdős 正式提出的。 1935 年，他

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

    在集合 {1, 2, ..., n} 中选出尽可能多的子集，使得每个子集所含的元素个数都是奇数，但是任意两个子集的交集都含有偶数个元素。那么，我们最多能够选出多少个这样的子集来？

    容易看出，我们至少可以选出 n 个子集。例如，当 n = 4 时， {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗？简单地尝试后，你会觉得似乎不行。不过，这却并不是显然的，因为存在一些不那么平凡的方案，也能让子集的数量达到 n ，例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4}

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

    n 个小朋友在圆桌上坐成一圈。初始时，每个小朋友都拥有一定数量的糖。接下来，反复进行下面两个操作：

      1. 如果有人手里的糖数是奇数，就向老师再要一颗糖，把手里的糖数补成偶数；

      2. 每个人都把自己手中一半的糖传给他右边的人（同时接到从左边传过来的糖）。

    证明：总有一个时刻，所有小朋友手中都会拥有相同数量的糖。

    附加题：这是一个非常经典的问题。

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

    这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题：是否有可能在平面上画不可数个不相交的 8 ？答案是否定的。证明方法非常简单。对于任意一个 8 字形，在两个洞里各取一个有理点 P 、 Q （由于平面上的有理点是稠密的，这是总能办到的），则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交，因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的，因此 8 字形的数量也是可数的。

      

   &n

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

    Heron 公式是一个已知三角形三边长便能直接求出其面积的经典公式。把三角形的三边长分别记作 a 、 b 、 c ，令三角形的半周长 p = (a + b + c) / 2 ，则三角形的面积可以用 Heron 公式 S = √p(p - a)(p - b)(p - c) 求出。如果把 p = (a + b + c) / 2 代入式子，得到的公式其实也挺对称的： S = √(a + b + c)(a + b - c)(a - b + c)(- a + b + c) / 4 。

    现在，我们把这个公式看作是一个关于 c 的函数： f(c) =

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

    今天的趣题来自 UyHiP 今年十月的趣题。

    许多快递公司都依据物件的长、宽、高三边之和来收费，一些航空公司也要求托运行李的三边长相加不能超过某个限制。那么是否有人想过，有没有可能把一个三边之和较大的盒子装进一个三边之和较小的盒子里，从而骗取更低的费用呢？有人会说，恐怕不行吧，长宽高之和更大的盒子体积不也应该更大一些吗？不见得。比方说，盒子 A 的长宽高分别是 10 、 10 、 10 ，盒子 B 的长宽高分别是 9 、 9 、 12.1 。盒子 B 的三边长之和显然比盒子 A 要大，但体积只有 980.1 ，比前者要小近 20 个单位

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

    网友 @ipondering 分享了一个非常精彩的数学趣题集，里面有很多我之前从没见过的趣题，其中有些问题的题目和解答都相当漂亮。近段时间里，我打算从中选一些最精彩的题目来讲讲。今天的题目是该趣题集中的第二题，原题背景涉及到 King Arthur 和 Merlin 的故事，我就舍去简化了。

    某个国王手下有 n 个大臣。国王定期主持国家会议，届时 n 个大臣将会间隔均匀地坐在圆桌上。每个座位前都有一盏照明灯，只有所有的灯都亮了，会议才能开始进行。如果有些灯没亮，国王会下达指令，让指定位置上的大臣按下座位前的灯的开关，把没亮的灯都打开。例

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

    今天听说了 Conway's Soldiers ，这是 Conway 大牛在 1961 年提出的一个数学谜题（似乎 Conway 的出镜率也太高了），我觉得非常有意思，在这里跟大家介绍一下。内容基本上来自于 Wikipedia 的相关页面。

    假设有一个无限大的棋盘。棋盘上可以放置一些象征着士兵的棋子。一个棋子可以跳过并吃掉和它相邻的一枚棋子（就像孔明棋一样）。这是棋子的唯一一种移动方式。现在，在某个位置画一条无限长的水平线，你需要在水平线下面放置足够多的棋子，使得它们前仆后继地往水平线上方跳，最终能够跳到水平线以上 n 个单位的位置。

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