|
Aug
21
在一棵树中，任意两个顶点之间的路径都是唯一的。如果一棵树有 n 个顶点，那么这棵树总共会有 n(n-1)/2 条路径（每两个顶点都会确定出一条路径来）。 1975 年， John Leech 提出了这么一个问题：有多少顶点数为 n 且边上带权的树，使得图中所有 n(n-1)/2 条路径的权值之和正好是 1, 2, …, n(n-1)/2 ？Leech 本人给出了五个这样的例子，其中四个如下图所示，顶点数 n 分别为 2 、 3 、 4 、 4 。第五棵满足要求的树拥有 6 个顶点，把它找出来将会是一个不小的挑战，感兴趣的读者不妨尝试一下，本文最后会公布答案。 Leech 注意到了 n = 5 时是无解的，但却并没有给出一个解释。 1977 年， Herbert Taylor 给出了一个非常漂亮的解释：如果一棵树满足上述要求，那么顶点数 n 一定是形如 m2 或者 m2 + 2 的数。让我们来看一看这个精妙的证明。
Mar
8
1996 年 9 月 10 日，《旧金山纪事报》的体育版上登载了《巨人队正式告别 NL 西区比赛》一文，宣布了旧金山巨人队输掉比赛的消息。当时，圣地亚哥教士队凭借80场胜利暂列西区比赛第一，旧金山巨人队只赢得了 59 场比赛，要想追上圣地亚哥教士队，至少还得再赢 21 场比赛才行。然而，根据赛程安排，巨人队只剩下 20 场比赛没打了，因而彻底与冠军无缘。 有趣的是，报社可能没有发现，其实在两天以前，也就是 1996 年 9 月 8 日，巨人队就已经没有夺冠的可能了。那一天，圣地亚哥教士队还只有 78 场胜利，与洛杉矶道奇队暂时并列第一。此时的巨人队仍然是 59 场胜利，但还有 22 场比赛没打。因而，表面上看起来，巨人队似乎仍有夺冠的可能。然而，根据赛程安排，圣地亚哥教士队和洛杉矶道奇队互相之间还有 7 场比赛要打，其中必有一方会获得至少 4 场胜利，从而拿到 82 胜的总分；即使巨人队剩下的 22 场比赛全胜，也只能得到 81 胜。由此可见，巨人队再怎么努力，也不能获得冠军了。 在美国职业棒球的例行赛中，每个球队都要打 162 场比赛（对手包括但不限于同一分区里的其他队伍，和同一队伍也往往会有多次交手），所胜场数最多者为该分区的冠军；如果有并列第一的情况，则用加赛决出冠军。在比赛过程中，如果我们发现，某支球队无论如何都已经不可能以第一名或者并列第一名的成绩结束比赛，那么这支球队就提前被淘汰了（虽然它还要继续打下去）。从上面的例子中可以看出，发现并且证明一个球队已经告败，有时并不是一件容易的事。为了说明这一点，我们展示一组虚构的数据（这是在 1996 年 8 月 30 日美国联盟东区比赛结果的基础上略作修改得来的），如下表所示。
其中，纽约扬基队暂时排名第一，总共胜 75 场，负 59 场，剩余 28 场比赛没打，其中和巴尔的摩还有 3 场比赛，和波士顿还有 8 场比赛，和多伦多还有 7 场比赛，和底特律还有 3 场比赛（还有 7 场与不在此分区的其他队伍的比赛）。底特律暂时只有 49 场比赛获胜，剩余 27 场比赛没打。如果剩余的 27 场比赛全都获胜的话，是有希望超过纽约扬基队的；即使只有其中 26 场比赛获胜，也有希望与纽约扬基队战平，并在加赛中取胜。然而，根据表里的信息已经足以判断，其实底特律已经没有希望夺冠了，大家不妨自己来推导一下。
Feb
28
一个树林里有 100 个村庄，它们之间有 1000 条小路，每条小路都连接着两个不同的村庄。每条小路 e 都有一条难度系数 l(e) ，所有小路的难度系数都不相同。现在有一个探险家，他想要选择一条长度为 20 的路径，使得所经过的小路的难度系数不断增加。求证：他总能找到这样的路径。 探险家可以任意选择路径的起点和终点。
Jan
28
今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。
Nov
9
这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题：是否有可能在平面上画不可数个不相交的 8 ？答案是否定的。证明方法非常简单。对于任意一个 8 字形，在两个洞里各取一个有理点 P 、 Q （由于平面上的有理点是稠密的，这是总能办到的），则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交，因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的，因此 8 字形的数量也是可数的。 注意到，平面上显然能够容下不可数个不相交的直线段，也显然能够容下不可数个不相交的圆（比方说一系列同心圆）。在 Mathematical Puzzles 一书里， Peter Winkler 提出了这样一个问题：我们能在平面上写下不可数个不相交的字母 Y 吗？
Jun
10
给定 n 个村庄的位置，要想把他们全部连通，最少需要修建多长的公路？这个问题被称为 Steiner 问题，是由数学家 Jakob Steiner 提出来的。注意，和最小生成树不同的是，公路是可以在中间汇合、分岔的。目前已经知道，Steiner 问题是 NP-hard 的，在规模很大的情况下，不能有效地得出最优解来。 然而，大自然却是无敌的，它可以迅速秒杀这样的难题。由于肥皂膜总会试图让自己的表面积最小，利用肥皂膜实验，我们可以轻易获得 Steiner 问题的解。我在很多书上都看到过肥皂膜实验的方法，不过却从没见过真正的实验视频。今天我终于看到了这样的视频，把它搬进墙来，和大家分享。这个视频也很好地解释了一个普遍存在的误区：说肥皂膜实验一举解决了 NP 问题是不恰当的，因为这个实验只能找到极小值，并不能找到最小值，运气不好的话，实验结果会是失败的。
Apr
4
一个公司里有 n 个员工，其中某些员工之间有“好友”的关系（这是一个对称的关系）。每天早晨来到公司，员工们都会从茶和咖啡中选择一样作为早饮。此时，每个员工都会观察自己的朋友们都在喝啥：如果超过一半的人都在喝茶，第二天他自己也会跟着喝茶；如果超过一半的人都在喝咖啡，第二天他自己就会跟着喝咖啡；如果喝茶喝咖啡的人数各占一半（仅当他有偶数个朋友时才会发生这种情况），则第二天他的决策不变，继续喝自己今天喝的东西。
Apr
2
某公司有 n 间办公室。每间办公室都有一盏灯，拉动它的开关即可改变电灯的状态。某些办公室之间存在“业务相关”的关系（这是一个对称的关系）。一个办公室可以和 0 到任意多个办公室相关。愚人节那天，有人在大家上班之前偷偷对办公室的电灯开关做了手脚：拉动任何一个办公室的电灯开关，都会同时改变该办公室以及所有相关办公室的电灯状态。初始时，所有灯都是关着的。证明：等到大家来上班后，总能用有限次的开关，最终把所有办公室的灯都打开。 |
|
|
来自： AMI66 > 《mathematica》
Matrix67 |
2013-08-21 12:46 | 
