1856 年，仍在研究非交换代数的哈密顿发明了二十面体演算：三个符号 $\iota$、$\kappa$ 和 $\lambda$，服从规则 $$\iota^2 = 1, \qquad \kappa^3 = 1, \qquad \lambda^5 = 1, \qquad \lambda = \iota\kappa.$$今天我们会说，它们生成了正二十面体（有二十个三角形面的立体）的旋转群。1857 年，哈密顿在英国科学促进会于都柏林举行的会议上介绍了这种演算，并注意到它描述的是沿正十二面体（有十二个五边形面和二十个顶点的立体）的棱行走的路径。 谜题 为了让这个想法流行起来，哈密顿把十二面体压平画在一块板上，在二十个顶点处开了孔，每个孔标上一个城市的名字，另配二十个编了号的木钉。挑战是：从一个城市出发，只沿着棱走，把其他每个城市恰好访问一次，再回到出发点。1859 年，他以 25 英镑把版权卖给了伦敦的游戏制造商约翰·贾克斯父子公司。这个游戏以“周游世界游戏”（The Icosian Game）的名字出售，还有一个叫“旅行者的十二面体”的袖珍版，但在商业上失败了：只要有点耐心，基本的挑战几分钟就能解决。 圣保罗大学数学与统计研究所 Matemateca 收藏的周游世界游戏复制品。编号的木钉标出了经过二十个顶点的顺序。Estes Objethos Atelier，Alisson Ricardo 摄 · Wikimedia Commons · CC BY-SA 4.0 试一试。字母是哈密顿用来给城市命名的辅音字母： 请启用 JavaScript 以使用这个交互图形。完整的推理见正文。 欧拉解决了，哈密顿没有 每个顶点恰好经过一次再回到起点的路线，今天称为哈密顿回路。这个问题看起来像是柯尼斯堡七桥问题的表亲，在那个问题里欧拉想把每条边恰好走一次。但两者非常不同。对于边，欧拉在 1736 年给出了一个简单的判据：只要看每个顶点连出多少条边。对于顶点，没有人知道简单的判据。1972 年，理查德·卡普把哈密顿回路问题列入他的 NP 完全问题清单：谁能为它找到一个快速方法，谁就有了解决成千上万其他难题的快速方法，还能从克莱研究所赢得一百万美元。 它最著名的亲戚是旅行商问题：在一张地图的所有哈密顿回路中，哪一条最短？它出现在送货路线、电路板钻孔和 DNA 测序中。 柯克曼抢先了一步 1855 年，比哈密顿早两年，英国牧师兼数学家托马斯·柯克曼就已经问过：哪些多面体存在一条经过每个顶点恰好一次的回路？他还给出了一个不可能做到的例子。名字却归了哈密顿，他名气更大，还有一个在售的游戏。 练习：数一数棱在正十二面体中，20 个顶点中的每一个都连着 3 条棱。共有多少条棱？一条哈密顿回路用了其中多少条？ 按顶点数，共有 $20 \times 3 = 60$ 个棱端，每条棱有两个端点：$60 / 2 = 30$ 条棱。一条哈密顿回路经过 20 个顶点再回来，用了 20 条棱；其余 10 条没有用到。
来源： ITA ——第二阶段数学试卷。 文件见 ITA 历年试题页面。 ITA 2024 第二阶段数学试卷共有 10 道解答题。ITA 不公布第二阶段的官方解答；下面的解答 由我们完成，每个答案都用第二种方法（代入、另一个公式或计算机）核对过。 答案一览 题号 内容 答案 1 等差数列与等比数列 $n = 4$ 2 走过所有桥的路线（欧拉路径） 32（每个方向 16） 3 含对数绝对值的不等式 $-4 < x < -\frac14$ 或 $\frac14 < x < 4$ 4 正定矩阵 $-1 < b < 1$ 5 关于 $x = 1$ 对称的多项式 $1 \pm \sqrt{3}$ 和 $1 \pm i\sqrt{6}$ 6 立体内最长的线段 $\frac{4\sqrt{161}}{5}$ 7 与 $y$ 轴相切的圆 $(x - 4 - \sqrt{6})^2 + (y - 3 + \sqrt{6})^2 = (4 + \sqrt{6})^2$ 8 顶点在抛物线上的梯形 $\frac{483}{64}$ 9 复数根与面积 $4\sqrt{5}$ 10 半角的正切 $\frac{1 + \sqrt{5}}{2}$、$\frac{\sqrt{5}}{5}$ 和 $\frac{5 - \sqrt{5}}{10}$ 第 1 题：等比数列前几项之和为 −80？ 题目 设 $(a_n)$ 是等差数列，$(b_n)$ 是等比数列。若 $(a_n)$ 的公差为 $r$（$r \ne 0$），$(b_n)$ 的公比为 $q = 1/r$，$a_1 = b_1 = 4$，且
1652 年版画中的柯尼斯堡，有普雷格尔河、两个岛和七座桥。为了解决七桥问题，欧拉几乎扔掉了这幅画所显示的一切。Merian-Erben · Wikimedia Commons · 公有领域 普鲁士的柯尼斯堡城被普雷格尔河穿过，河中形成两个岛，七座桥把城市的四个部分连在一起。居民们想知道，能不能散一次步，每座桥恰好走一次。1736 年，欧拉证明了不能。历史书在柯尼斯堡七桥那一篇里讲了这个证明。这里关心的是欧拉对图做了什么。 扔掉地图 城市地图显示街道、房屋、距离、河的宽度、岛的形状。欧拉意识到，这些对问题都不重要。重要的只是城市的哪些部分由哪些桥连接。每个部分变成一个点；每座桥变成两点之间的一条线。结果就是今天所说的图：四个点和七条线。 在这张图里，大小、距离和形状都不再有意义。可以把一条线拉长，把一个点挪个位置，把一切都弄弯：只要连接关系不变，图就还是那张图。用皮尔斯的话说，图是一种非常特殊的图像符号：它只在连接关系上与城市相似。这是一种严格挑选了复制什么的图像符号。 正是这张被简化了的图让答案显现出来。散步时，每次从一座桥进入一个点，就要从另一座桥离开；所以路线中途的每个点都必须连着偶数条线。在柯尼斯堡，四个点分别连着 $5$、$3$、$3$ 和 $3$ 条线：全是奇数。这样的散步是不可能的。 不再是地图的地图 1931 年，伦敦地铁的一位技术绘图员哈里·贝克提出了一种新的地图。旧地图遵循地理：线路在市中心缠成一团，在郊区四散开来，没人看得懂。贝克意识到，乘客不需要知道车站在哪里，而需要知道车站按什么顺序排列、在哪里换乘。他只画直线——水平的、竖直的和 $45°$ 的——车站之间的距离都相等。 1933 年出版的贝克地铁图是一张图，而不是一张地图。它完全扭曲了地理，而这正是它好用的原因。几乎世界上所有的地铁——包括圣保罗、东京和上海的地铁——都采用了同样的原则。代价是游客有时会坐地铁去一个步行五分钟就能到的车站，因为在图上它看起来很远。 同一个图，不同的画法 由于只有连接关系重要，同一个图可以有非常不同的画法。一个画了两条对角线的正方形，和从上方看的三棱锥，是同一个图：四个点，两两相连。判断两张画是否表示同一个图，对大的图来说是一个出奇困难的问题，它有一个名字：图同构问题。 有时画法确实重要。如果一个图能画得没有任何两条线交叉，它就是平面图。这决定了，比如说，一块印刷电路能否只用一层做成。 三间房子与三种公用设施 一个古老的谜题要求把三间房子分别连到三种公用设施——水、电、煤气——而且任何两条管道都不交叉。每个尝试的人最后都会遇到一个交叉，这不是因为技术不够：一边三个点、另一边三个点、九条连线全都连上的图，叫作 $K_{3,3}$，它不是平面图。1930 年，波兰人卡齐米日·库拉托夫斯基证明：一个图是平面图，当且仅当它里面没有藏着 $K_{3,3}$，也没有藏着五个点两两相连的图 $K_5$。 练习：第八座桥如果居民们建造第八座桥，连接河的两岸，散步会变得可能吗？ 两岸原来各连着 $3$ 条线；有了新桥，各连 $4$ 条。度数变成 $5$、$4$、$4$ 和 $3$：只有两个奇数点。每座桥走一次的散步变得可能，从一个奇数点出发，在另一个奇数点结束。 练习：为什么 K₃,₃ 不是平面图用平面图的欧拉公式 $V-E+F=2$（顶点数减边数加面数）证明 $K_{3,3}$ 不是平面图。 $K_{3,3}$ 有 $V=6$，$E=9$。如果它是平面图，就有 $F=2-6+9=5$ 个面。$K_{3,3}$ 里没有三角形（每条连线都从房子连到设施），所以每个面至少有 $4$ 条边。由于每条边最多是 $2$ 个面的边界，$4F\leq2E$，即 $20\leq18$，矛盾。所以不存在没有交叉的画法。 本章目录 · ← 阿尔冈平面：找到位置的虚数 · 无字证明 →