IT牛人博客聚合

    我老早就写过一个经典的小学几何题。如果你还没看过这个问题，你一定要去看看。一个小学奥数老师曾经告诉我，当年带领学生参加这次竞赛时，领队老师们都没有想到这个问题的“小学生解法”，以至于开始质疑这道题是否超纲了。看到答案后，老师们大为折服——这个问题确实有一个无需任何几何知识的妙解。

      

    今天，同样的事情发生了。今天临时去代一节小学奥数课，见到这么一道题： ABCD 是一个正方形，边长为 4 ， DEFG 是一个矩形，其中 DG = 5 ，求 DE 的长度。还是那段话：

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

    当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题（eight queens puzzle）时，他恐怕怎么也想不到，100 多年以后，这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单：把八个皇后放在国际象棋棋盘上，使得这八个皇后互相之间不攻击（国际象棋棋盘是一个 8×8 的方阵，皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步）。虽然这个问题一共有 92 个解，但要想徒手找出一个解来也并不容易。下图就是其中一个解：

     

    八皇后问题有很

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

    由于某些原因，最近在整理以前的日志。偶然翻到这篇日志时，顺便在 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

    今天见到一种看上去很帅的质数筛选法。在平面直角坐标系上画出抛物线 y = x2 的图像，然后标出抛物线上的所有格点（两坐标均为整数的点）。其中，只有点 (0, 0) 正好在 y 轴上，其余的点要么在 y 轴左侧，要么在 y 轴右侧。把 y 轴左侧除了 (-1, 1) 以外的所有格点与 y 轴右侧除了 (1, 1) 以外的所有格点相连，这些连线将自动避开 y 轴上纵坐标为质数的点。连接足够多的线条之后，质数就逐渐露了出来。

      

    这是因为， (-a, a2) 和 (b,

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

    这个并不是标题党。很多年以前，要想进入莫斯科国立大学的数学系，你必须通过四项入学考试；头两个都是数学考试，一个笔试，一个面试。在面试中，学生和考官都是一对一的，考官可以自由向学生提出任何他喜欢的问题。考官们都准备了很多“棺材问题”，这些问题的答案非常简单，但由于思路太巧妙了，以至于学生很难想到。考官便可以以“你连这个都没想到”为理由，光明正大地拒绝学校不想要的人（主要是犹太人）。这个 Blog 之前就曾经介绍过这样的问题。

    最近网上的一篇文章介绍了 21 个这样的“棺材问题”，其中有些这个 Blog 以前讲过的经典问题，但也有不少我第一

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

今天，我拿到了梦寐以求的大规模中文语料库，总大小超过 1 G ，覆盖了各个时代各种文体的中文资料。有了这个语料库后，我便能完成很多早就想做的事情，比方说，统计各种文体中出现频率最高的四字词。给定一段文本后，基本的统计过程如下：

  1. 统计所有连续四字的出现频数；

  2. 按频数对所有四字组合从高到低排序；

  3. 删掉所有包含非汉字字符（比如数字、标点）的四字组合；

  4. 删掉明显不成词或者不成词组的四字组合（这一步有人为因素，因此下面的数据并不是 100% 客观的）；

  5. 列出频数最高的 10 个四字词。

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

    这道题的答案有几个字母？答案：four。

    有趣的是，这是唯一的答案。如果令函数 f(n) 表示非负整数 n 的英文表达中有多少个字母（不算空格和短横线）， n=4 是该函数的唯一不动点。

       n    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …

      f(n)  4, 3, 3, 5, 4, 4, 3,

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

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

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

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

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

    今天在这里学到一种很诡异的定积分方法。看看下面这个定积分，你打算怎么求解？

      

    当然，我们假设 a 、 b 满足这个定积分的值确实存在。

    下面是一个很妙的做法：

      

    正所谓“用定积分来求解定积分”，实在让人眼前一亮。这告诉我们，“化简”并不一定要化“简”，把问题还原为更复杂的形式，反而会有出其不意

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

    昨天终于读完了《The Annotated Turing》一书，第一次完整地阅读了 Turing 最经典的那篇论文，理解了 Turing 机提出的动机和由此带来的一系列结论。不过，这本书的最大价值，则是让我开始重新认识和思考这个世界。在这里，我想把我以前积累的哲学观点和最近一些新的思考记下来，与大家一同分享。《The Annotated Turing》一书中的一些学术内容，留待以后几篇日志与大家分享。今年是 Alan Turing 诞辰 100 周年，图灵公司将推出这本书的中译本《图灵的秘密》，现在正在紧张的编辑排版中，不久之后就能和大家见面。

   &

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

    英语当中有一种笑话类型。第一次看到的是：

- What's the difference between a girl in church and a girl in the bathtub?

- One has hope in her soul, one has soap in her hole.

    把我给笑坏了。在说这种笑话的时候，只说一半的效果往往更好。又比如：

- What's the difference between a midget magician and a female jogger?

- One i

查看全文: http://www.udpwork.com/item/6922.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

    无论是小学奥数，还是公务员考试，还是公司的笔试面试题，似乎都少不了行程问题——题目门槛低，人人都能看懂；但思路奇巧，的确会难住不少人。平时看书上网与人聊天和最近与小学奥数打交道的过程中，我收集到很多简单有趣而又颇具启发性的行程问题，在这里整理成一篇文章，和大家一同分享。这些题目都已经非常经典了，绝大多数可能大家都见过；希望这里能有至少一个你没见过的题目，也欢迎大家来信提供更多类似的问题。

    让我们先从一些最经典最经典的问题说起吧。选中空白部分显示答案。

    甲、乙两人分别从相距 100 米的

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