Matrix67 |
2010-03-08 11:44 | 
来源：MathOverflow
不得不说，确实很妙！
Nov
13
空间中有六个点，它们两两间的距离都互不相等。考虑所有以这些点为顶点构成的三角形。证明：存在某个三角形，它的最长边是另外某个三角形中的最短边。
这个结论并不是显然的。为了说明这一点，只需要注意到同样的结论对n=5的情况是不成立的。考虑平面上一个正五边形的五个顶点（微调它们的位置使得两两间的距离互不相等），容易发现任意三个点所组成的三角形，其最长边都不可能是另一个三角形的最短边。
Sep
15
今天下午在上语言统计分析课时，我听到了一个非常有趣的问题。考虑同时抛掷两个骰子所得到的结果——它们的和有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。不过，这个问题有一个异常巧妙的解法，它能够把两个骰子的点数进行整体求解。你能想到这个做法吗？
Aug
10
考虑直线x+y=n，其中n是一个素数。这条直线将恰好通过第一象限里的n-1个格点（如上图，图中所示的是n=11的情况）。将这n-1个点分别和原点相连，于是得到了n-2个灰色的三角形。仔细数数每个三角形内部的格点数，你会发现一个惊人的事实：每个三角形内部所含的格点数都是一样多。这是为什么呢？
Jul
12
大家在玩俄罗斯方块的时候有没有想过这样一个问题：如果玩家足够牛B的话，是不是永远也不可能玩死？换句话说，假设你是万恶的游戏机，你打算害死你面前的玩家；你知道任意时刻游戏的状态，并可以有针对性地给出一些明显不合适的方块，尽量迫使玩家面对最坏情况。那么，你有没有一种算法能保证害死玩家，或者玩家无论如何都存在一种必胜策略呢？注意，俄罗斯方块的游戏区域是一个宽为10，高为20的矩形，并且玩家可以预先看到下一个给出的方块是什么。在设计策略时，你必需考虑到这一点。
相信很多人有过这样的经历：玩俄罗斯方块时一开局就给你一个“S”型方块，让完美主义者感到异常别扭；结果，第二个方块还是这个“S”，第三个方块依旧是“S”，相当令人崩溃。于是，我们开始猜测，如果游戏机给你无穷个“S”形方块，玩家是不是就没有解了？答案是否定的。如图1，从第10步开始，整个局面产生一个循环；只要机器给的一直都是“S”方块，玩家可以不断重复这几个步骤，保证永远也死不了。
不过，这个循环是在游戏场地清空了的情况下才产生的。有人会进一步想了，要是在玩着玩着，看着你局势不好时突然给你无穷多个“S”方块呢？事实上，此时局面的循环依然可能存在，如图2。在第5个“S”形方块落地后，循环再次产生。
Jul
5
今天在写一个稿件时又翻阅了一下Erich Friedman的Math Magic，发现了一个有趣的东西——场地大小为n的推箱子游戏所需要的最少步数最坏情况是多少。下面这个构造说明，最坏情况至少也是指数级的。
首先，让我们来看看该构造中的一个基本单元：
这个构造中共有6个箱子，且它们都已经在目的位置上了。不难看出：
1. 假如你人在这个区域之外，你只可能从右上角的出入口进入该区域，从其它地方进去都会导致死局
2. 从右上角进入后你只能往下走，进入1区；走左边的话直接导致死局
3. 你可以通过2区前往3区，但若从3区左上角的出口出去了，则2区动过的箱子将永远无法回到原位（除非你原路返回）
4. 你可以通过2区前往3区，并把3区左边的那个箱子左移一格，再返回2区；这样下次你再从右上角进入该区域时便可以直接经过3区从左上角出去
5. 最后你只能从4区离开
May
22
这里有一个有趣的问题：在集合{1, 2, ..., n}中选取尽可能多的子集，使得任意两个子集的交集有且仅有一个元素。例如，当n=7时，选取{1,2,3,4}、{4,5,6,7}、{1,7}这3个集合可以满足条件。子集数还可以更大一点吗？最大是多少？给出一种构造，然后证明这个数目不可能更大了。
当n=7时，仅仅取3个子集实在是太弱了。一种最简单的办法就可以让子集数达到6，只需取{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}即可。再仔细观察，我们发现这个结果还可以进一步改进：我们还可以再往里面添加进一个子集{1}，使得这7个子集两两间仍然恰有一个公共元素。这下我们似乎不能再往里面添加任何新子集了。我们还可以做得更好吗？一个新的思路是在{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}里面加上{2,3,4,5,6,7}，这同样可以让子集数达到7个，可惜我们仍然无法再往里面添加新的子集了。经过若干次尝试后，我们逐渐开始确信，在集合{1, 2, ..., n}里面最多只能选出n个两两恰有一个公共元素的子集，并且构造方法无外乎上面两种。这一猜想不但与直觉相符，而且貌似也很好证明。你或许会从一些看似很直观的结论出发开始证明：“显然不可能有两个大小为1的子集”，“选取多个元素个数大于2的子集显然不划算”……但牛B就牛B在，偏偏就有这样一种子集数为n的取法，每个子集里都有不止两个元素，但仍然保证任意两个子集间恰有一个公共元素：
{1,2,3}、{1,4,5}、{1,6,7}、{2,4,7}、{3,4,6}、{3,5,7}、{2,5,6}
这一个例子对我们的猜想足以构成威胁：子集数为n真的已经到极限了吗？证明结论有那么容易吗？看来，情况貌似比我们想象中的要复杂得多。
May
18
大学生活混起来很快，不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆，因此今年我主动去报了名（上次是被人给拖去的）。今年有点装怪，题目数量不变，但时间缩短为4个小时。原计划是从8:00做到12:00，结果可能是因为我们所在的7号机房迟迟没有开门，时间临时改成了8:15到12:15。总的来说，今年的题目比去年要糟糕得多，但也不乏一些精彩的题目。
和去年一样，第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁，我猜不少队伍都卡在这儿了吧。
后来我完全打翻前面的全部思路，猛然想到了一个具有决定意义的想法：街道的选取唯一地决定了整个路线。例如，假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的，其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此，我们可以用排列组合直接计算出答案来。向上走的路是五选二，向右走的路是七选三，向下走的路是四选三，向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是，计算所有的路线数只需要从小到大枚举拐弯的次数，每一次计算都是常数的，总复杂度是O(n)的；整个算法的瓶颈反倒是O(n^2)的组合数预处理，不过这个复杂度完全可以承受。
