如果 10 个非负数 x1, x2, ..., x10 满足 x1 + x2 + x3 + ... + x10 = 1 ，那么这 10 个数都均匀地分布在 [0,1] 之间吗？显然不是。为了说明这一点，最好的方法或许是把分布情况变得有限——我们可以把 [0,1] 区间划分成若干个小区间，并说明这 10 个数不可能均匀地分布在这些区间内。比方说，把 [0,1] 分成 [0, 0.25), [0.25, 0.5), [0.5, 0.75), [0.75, 1] 这四段：如果 10 个数都落在 [0, 0.25) 里，它们的和是有可能为 1 的；但若 10 个数都落在 [0.75, 1] 里，显然它们的和不可能为 1 。一个有趣的问题由此产生：考虑 10 个数的 4^10 种分布，它们的和有可能为 1 的有多少情况？

 
 
    显然， 10 个区间的右端点之和一定比 1 大。因此，只要 10 个区间的左端点之和不超过 1 ，就可以保证在这些区间中选的数之和可能为 1 。不妨把区间 [0, 0.25), [0.25, 0.5), [0.5, 0.75), [0.75, 1] 依次编号为 0, 1, 2, 3 ，由于它们的左端点分别为 0/4, 1/4, 2/4, 3/4 ，因此左端点之和不超过 1 相当于 10 个区间的编号之和不超过 4 。而和不超过 4 的 10 个非负整数，又与 4 个小球和 10 个隔板的排列顺序一一对应，它们一共有 C(14, 4) = 1001 种情况。但在这 1001 种情况中， (4, 0 ,0, ..., 0), (0, 4, 0, ..., 0), ……, (0, 0, 0, ..., 4) 这 10 种情况是要排除的，因为区间编号只有 0 到 3 。因此，在 10 个数的 4^10 种区间分布中，只有 991 种分布才满足它们的和可能为 1 。

查看更多 »

23. 一些硬币互不重叠地放在桌上。四色定理告诉我们，若要对硬币进行染色，使得挨在一起的硬币颜色不同的话，最多只需要四种颜色就可以了。存在至少需要四种颜色的构造吗？

答案：存在。如图，若只允许三种颜色的话， A 的颜色必须与所有阴影硬币颜色相同， B 的颜色也必须与所有阴影硬币颜色相同， A 、 B 将会同色。

  

查看更多 »

引言 什么是算法
如何寻找稳定的婚姻搭配

 
    据说，一本书开篇就直言不讳地谈起两性的话题，这本书准能畅销。有幸的是，在众多可以用来引入“算法”的话题中，我最喜欢的那一个还真与两性有那么一些关系。假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中的排名⁽¹⁾，你应该怎样为他们牵线配对呢？
    最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。这虽然很完美，但绝大多数情况下都不可能实现。比方说，男 1 号的最爱是女 1 号，而女 1 号的最爱不是男 1 号，这两个人的最佳选择就不可能被同时满足。如果出现了好几个男人的最爱都是同一个女孩儿的情况，这几个男人的首选也不会同时得到满足。当这种最为理想的配对方案无法实现时，怎样的配对方案才能令人满意呢？
    其实，找的对象太完美不见得是个好事儿，和谐才是婚姻的关键。如果男 1 号和女 1 号各自有各自的对象，但男 1 号觉得，比起自己现在的对象，女 1 号更好一些；女 1 号也发现，在自己心目中，男 1 号的排名比现男友更靠前一些。这样一来，这两人就可能会发生外遇，最后扔下各自现在的对象，一起私奔了——因为这个结果对他们两人都更好一些。在一种男女配对的方案中，如果出现了这种情况，我们就说婚姻搭配是不稳定的。作为一个红娘，你深深地知道，对象介绍得不好没有关系，就怕婚姻关系不稳定。给客户牵线配对时，虽然不能让每个人都得到最合适的，但婚姻搭配必须得是稳定的。换句话说，对于每一个人，在他心目中比他当前的伴侣更好的异性，都不会认为他也是一个更好的选择。现在，我们的问题就是：稳定的婚姻搭配总是存在吗？应该怎样寻找出一个稳定的婚姻搭配？

查看更多 »

来源：MathOverflow
不得不说，确实很妙！

    空间中有六个点，它们两两间的距离都互不相等。考虑所有以这些点为顶点构成的三角形。证明：存在某个三角形，它的最长边是另外某个三角形中的最短边。
    这个结论并不是显然的。为了说明这一点，只需要注意到同样的结论对n=5的情况是不成立的。考虑平面上一个正五边形的五个顶点（微调它们的位置使得两两间的距离互不相等），容易发现任意三个点所组成的三角形，其最长边都不可能是另一个三角形的最短边。

查看更多 »

    今天下午在上语言统计分析课时，我听到了一个非常有趣的问题。考虑同时抛掷两个骰子所得到的结果——它们的和有1/36的概率得到2，有2/36的概率得到3，……，有1/36的概率得到12。现在，你能否构造两个新的骰子，使得同时抛掷两个新骰子的结果与原来相同？注意，每个骰子都有6个面，每个面都有一个正整数。这些点数可能超过6，并且可能会有重复。另外，这两个骰子也无需完全相同。
    解决这个问题并不难。首先注意到，为了使得两个骰子的点数之和能够得达到2，每个骰子上都得有一个“1”（并且仅有一个“1”）才行。接下来考虑，为了得到两种和为3点的情况，我们还得在两个骰子上放置两个“2”：我们可以在每个骰子上各放一个“2”，不过这样就与原来的骰子没啥区别了；我们也可以来点不一样的，把两个“2”都放在一个骰子上。现在，其中一个骰子上只放了一个“1”，另外一个骰子已经填了一个“1”和两个“2”，这可以保证它们能产生出一个2点和两个3点。再下一步，我们将考虑如何产生出三个4点。为此，我们需要把三个“3”分配到两个骰子中。这样推下去虽然越来越麻烦，但最终你还是能得到一个合法解：一个骰子上写有1、2、2、3、3、4，另一个骰子上写有1、3、4、5、6、8。不过，这个问题有一个异常巧妙的解法，它能够把两个骰子的点数进行整体求解。你能想到这个做法吗？

查看更多 »

    考虑直线x+y=n，其中n是一个素数。这条直线将恰好通过第一象限里的n-1个格点（如上图，图中所示的是n=11的情况）。将这n-1个点分别和原点相连，于是得到了n-2个灰色的三角形。仔细数数每个三角形内部的格点数，你会发现一个惊人的事实：每个三角形内部所含的格点数都是一样多。这是为什么呢？

查看更多 »

    大家在玩俄罗斯方块的时候有没有想过这样一个问题：如果玩家足够牛B的话，是不是永远也不可能玩死？换句话说，假设你是万恶的游戏机，你打算害死你面前的玩家；你知道任意时刻游戏的状态，并可以有针对性地给出一些明显不合适的方块，尽量迫使玩家面对最坏情况。那么，你有没有一种算法能保证害死玩家，或者玩家无论如何都存在一种必胜策略呢？注意，俄罗斯方块的游戏区域是一个宽为10，高为20的矩形，并且玩家可以预先看到下一个给出的方块是什么。在设计策略时，你必需考虑到这一点。

    相信很多人有过这样的经历：玩俄罗斯方块时一开局就给你一个“S”型方块，让完美主义者感到异常别扭；结果，第二个方块还是这个“S”，第三个方块依旧是“S”，相当令人崩溃。于是，我们开始猜测，如果游戏机给你无穷个“S”形方块，玩家是不是就没有解了？答案是否定的。如图1，从第10步开始，整个局面产生一个循环；只要机器给的一直都是“S”方块，玩家可以不断重复这几个步骤，保证永远也死不了。

    不过，这个循环是在游戏场地清空了的情况下才产生的。有人会进一步想了，要是在玩着玩着，看着你局势不好时突然给你无穷多个“S”方块呢？事实上，此时局面的循环依然可能存在，如图2。在第5个“S”形方块落地后，循环再次产生。

查看更多 »