IT牛人博客聚合

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

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

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

    给定 n 个村庄的位置，要想把他们全部连通，最少需要修建多长的公路？这个问题被称为 Steiner 问题，是由数学家 Jakob Steiner 提出来的。注意，和最小生成树不同的是，公路是可以在中间汇合、分岔的。目前已经知道，Steiner 问题是 NP-hard 的，在规模很大的情况下，不能有效地得出最优解来。

     

    然而，大自然却是无敌的，它可以迅速秒杀这样的难题。由于肥皂膜总会试图让自己的表面积最小，利用肥皂膜实验，我们可以轻易获得 Steiner 问题的解。我在很多书上

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

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

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

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

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

 

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

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

    大家或许还记得 Quake III 里面的一段有如天书般的代码，其中用到的神秘常量 0x5F3759DF 究竟是怎么一回事，着实让不少人伤透了脑筋。今天，我见到了一段同样诡异的代码。

    下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 0 。比如， 123 456 的二进制表达是 1 11100010 01000000 ，因此这个程序给出的结果就是 6 。

unsigned int v;  // find the number of trailing zeros in 32-bit v

int r;

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

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

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

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