IT牛人博客聚合

    数列 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

    在集合 {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

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

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

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

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

    今年年初时，我曾经写过一篇名为 千万别学数学：最折磨人的数学未解之谜 的文章，选取并翻译了 Mathematical Puzzles

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

    这次的趣题来源于 UyHiP 今年八月份的谜题：概率均等地随机选取一个恰好含有 n 个 0 和 n 个 1 的 2n 位 01 串，这个 01 串平均会有多少个 0 和 1 个数相等的前缀（包括空串和整个串本身）？

    为了叙述简便起见，下面我们把所含 0 和 1 个数恰好相等的 01 串叫做平衡的 01 串。例如， 010010110011 就是一个平衡 01 串，它有四个平衡前缀，空串、 01 、01001011 以及整个 01 串本身。我们需要求出的就是，任取一个长为 2n 的平衡 01 串，平衡前缀的个数的期望值是多少。

&nbs

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

    在一篇老日志中，我提到了一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续两个正面？它的答案是 6 次。它的计算方法大致如下。

    首先，让我们来考虑这样一个问题： k 枚硬币摆成一排，其中每一枚硬币都可正可反；如果里面没有相邻的正面，则一共有多少种可能的情况？这可以用递推的思想来解决。不妨用 f(k) 来表示摆放 k 枚硬币的方案数。我们可以把这些方案分成两类：最后一枚硬币是反面，或者最后一枚硬币是正面。如果是前一种情形，则我们只需要看前 k - 1 枚硬币有多少摆法就可以了；如果是后一种情形，那么倒数第二枚硬币必须是反面，因而

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

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

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

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

    某公司有 n 间办公室。每间办公室都有一盏灯，拉动它的开关即可改变电灯的状态。某些办公室之间存在“业务相关”的关系（这是一个对称的关系）。一个办公室可以和 0 到任意多个办公室相关。愚人节那天，有人在大家上班之前偷偷对办公室的电灯开关做了手脚：拉动任何一个办公室的电灯开关，都会同时改变该办公室以及所有相关办公室的电灯状态。初始时，所有灯都是关着的。证明：等到大家来上班后，总能用有限次的开关，最终把所有办公室的灯都打开。

 

    证明：对 n 施归纳。只有一间办公室时，结论显然成立。下面假设我们已经有办法让任意 n-1 个办公室的

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

    有六个砝码，它们的重量分别是 1 克、 2 克、 3 克、 4 克、 5 克、 6 克。每个砝码上都标有这个砝码的重量，但由于生产过程中的疏忽，重量有可能被标错了。请你用天平称两次，来检验这些砝码所标克数是否完全正确。

    Update: 实际克数和所标克数都是 1 、 2 、 3 、 4 、 5 、 6 ，“标错”就是指它们的对应关系是错的。称砝码的目的只是检验所标克数的正确性，如果不正确，不用找出问题出在哪些砝码上。

 

 

    答案：先把标有 1 、 2 、 3 的

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

    最近在做网站测试时，遇到了需要在输入框输入 3000 字的测试用例。联想到平时聊天时经常复制粘贴一堆笑脸刷屏讨 MM 欢心的行为，不由想到了一个有趣的问题：为了输入一定数量的字符，最少需要按多少个键？

    大家最常用的策略或许是， 先输一些字符，然后全选复制，粘贴到一定规模后，再全选复制，粘贴到一个新的数量级，如此反复。注意到进入全选状态（并且复制后），第一次粘贴将会覆盖掉选中的部分，第二次粘贴才会增加原来的文本长度。当然，全选复制后按一次向右键也可以消除选中状态，不过却并没有节省按键次数。因此我们规定，在输入字符时只有四种原子操作：

&

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

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

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

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

    对原题的误读，有时竟会产生一些更有意思的问题。果壳问答上，网友 qxx 提问说：

一个房间里面有很多人，我想让房间里面任意两个人的生日相同的概率是 50% 的话那房间里面应该最少有多少人？

    当然，几乎可以肯定，提问人原本是想说“至少两个人”的，而问题的答案就是 23 ——生日悖论带来的惊人的答案。不过，如果把“至少两个人”误说成“任意两个人”，题目意思就完全变了，并且变得明显更有意思了。

    大家很快便会想到，如果任取两个人，他们的生日相同的概率恰好是 50% ，那么房间里最少有四个人，其

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