小乐数学科普：许俊珥 June Huh ，组合数学和国际象棋骑士问题的奇怪魅力

luyuanhong

小乐数学科普：许俊珥 June Huh ，组合数学和国际象棋骑士问题的奇怪魅力

许俊珥（June Huh）因其对组合学领域的变革性贡献，特别是他在组合学和代数几何之间建立的桥梁而于 2022 年被授予菲尔兹奖。然而，他的故事一点也不线性和直接——它与诗歌、科学和特定类型的国际象棋问题交织在一起。


许俊珥在里约热内卢举行的 2018 年国际数学家大会上

图源：Wiki Commons（CC BY 3.0）

作者：Andrei Mihai 海德堡桂冠论坛 HLF 博客 2024-5-1

译者：zzllrr小乐（数学科普公众号）2024-5-5

数学之诗

  高中时，许俊珥想成为一名诗人。他甚至从高中退学，专注于诗歌创作，因为不懈的学习而感到疲惫不堪。他的诗作并不那么好。

  他的大学学习也充满了困难。他想主修物理和天文学，并成为一名科学记者。然而，他的出勤记录很差，几门课程不及格后，他不得不重读。

  如果说有什么是许俊珥知道不想做的，那就是数学。“除了数学之外，我在大多数科目上都表现得很好，”他告诉《纽约时报》。然而，我们也能瞥见许俊珥的数学才华，但它看起来并不像数学。

  许俊珥回忆起这样的一幕来自最不可能的场景：一款电脑恐怖游戏。《第 11 小时》是一款 1995 年的电脑游戏，玩家需要调查一系列可怕的事件并将事情拼凑起来。玩家的任务是解决各种问题，其中一些问题非常复杂。

  其中，有一个谜题困扰着许俊珥。这是一个国际象棋谜题。


（图片由作者创建）

  这个谜题看起来很简单。它只有几个方格，并且只有四个骑士（骑士以“L”形移动，就像常规国际象棋一样，也像中国象棋中的马，但没有“蹩马腿”的限制）。目标也很简单：交换黑白骑士的位置。

  乍一看，这项任务似乎微不足道。你只需移动骑士直到奏效为止。但事情没那么简单——尝试一下看看。

  小许花了一周的时间才解决，但对他来说，这不仅仅是解决问题那么简单。这是关于理解问题的实际含义。

  从数学意义上来说，骑士的移动方式并不重要。棋盘的形状和尺寸也并不重要。重要的是棋盘分块的几何形状以及它们之间的关系。本质上，国际象棋谜题可以重新解释为图。每个骑士都可以移动到该图上未占据的空间，这使得解决问题变得更加容易。

  第一步是建立符号。


图问题的不同可视化（图片由作者创建）

  使用这种符号，你可以将它们视为从一个空间到另一个空间的可能移动的图，而不是以几何方式可视化骑士的移动。


同一国际象棋问题的另一种可视化方式。骑士从“1”开始跳到“5”，然后跳到“7”。（图片由作者创建）

  骑士只能从“1”移动到“5”，不能移动到其他地方。它可以从“5”返回到“1”或“7”。事实上，唯一一个可以让骑士去三个地方的盒子是“2”。关键就在这里。

  当我们添加骑士数量时，问题会呈现以下形式：


（图片由作者创建）

  通过上图，前进的方向就变得更加明显了。我们有方格“9”，可以将其用作一名骑士的藏身处，同时操纵其他三名骑士。如果我们想交换白色和黑色的骑士，我们只需一次将黑色的骑士移开，然后将白色的骑士移到左侧（如图所示）。尝试一下！

翻译成数学

  这种以数学方式可视化问题的方法让许俊珥着迷，并吸引他走向数学。这种特殊类型的问题称为染色多项式（chromatic polynomial）。

  想象一下，你有一张地图或由边连接的节点网络，就像由道路连接的城市或地图上有边界的区域一样。该网络（或图）的染色多项式告诉你染色方法种数：使用给定数量的颜色对节点（或区域）进行着色，使得没有两个相邻节点（或相邻区域）拥有相同颜色。

  这个想法不仅仅与国际象棋有关。它在物流和优化问题、统计物理（特别是相变研究）和网络分析中具有实际应用。

  将问题转化为数学表达式对许俊珥来说不仅仅是一种爱好。在大学的最后一年，许开始真正爱上数学。他参加了 1970 年获得菲尔兹奖的日本数学家广中平佑（Heisuke Hironaka，1931 -）的课程。他后来成为广中平佑的硕士生，并收到了推荐信。这是一个奇怪的组合：一个学生没通过几门数学课程，但却得到了一位顶尖数学家的热情推荐。这几乎还不够。许俊珥申请的大学中，除了一所之外，其他所有大学都拒绝了他。伊利诺伊大学厄巴纳-香槟分校将他列入候补名单，最终录取了他。

  由此许俊珥开始了研究之旅。沿着一条不情愿的数学之路，他继续彻底改变组合数学领域，重振该领域并将其与一些最深奥的几何领域交织在一起。

  然而，许俊珥远不是唯一一位对国际象棋骑士谜题感兴趣的数学家。

著名的骑士之旅

  也许最著名的骑士问题是所谓的“骑士之旅”。前提再次非常简单。有一个给定尺寸的方形棋盘和一个骑士。你必须以覆盖所有方格的方式移动骑士，而不能两次进入同一个方格。像这样：


图片来源：Wiki Commons（CC BY 3.0）

该问题可以应用于多种不同的棋盘尺寸。


图源：Wiki Commons（CC BY 3.0）

  这也可以概括为图论中的哈密顿路径问题。但与许俊珥的问题不同，这个问题可以追溯到更早的时候。

  已知最早提及骑士旅行问题的文献可以追溯到 9 世纪的一部梵文著作中。克什米尔诗人兼文学理论家楼陀罗托（Rudrata）将骑士之旅以四行八音节的诗句形式呈现 https://youtu.be/DjZB9HvddQk——这是诗歌与数学的又一次令人惊讶的结合。

  著名数学家欧拉（Leonhard Euler，1707 - 1783）也研究过这个问题，但开发第一个可追踪算法来解决骑士之旅的人是 H.C. von Warnsdorf（沃恩斯多夫）。沃恩斯多夫提出了以下规则：“将骑士移动到一个方格，从该方格可以进行的后续移动最少。”


骑士图显示了骑士在标准 8×8 棋盘上旅行的所有可能路径。每个节点上的数字表示从该位置可以进行的可能移动的数量。

图源：Wiki Commons（CC BY 3.0）

  这个简单的规则出奇地有效，但它并不完美。在绝大多数情况下，它都会在小于 50×50 的棋盘上生成有效的遍历，但并非总是如此。

  事实证明，为骑士之旅找到一个可行的、可推广的算法比看起来更困难。这是由于较大棋盘的绝对复杂性造成的。例如，骑士之旅产生解决方案的最小棋盘是 5×5 。对于这种尺寸的棋盘，有超过 1700 种可能的遍历（如果遍历从不同的地方开始或具有不同的轨迹，则被认为是不同的；它们可以被镜像或旋转）。

  这个数字很快就会变得非常非常大。



  值得注意的是，这个问题甚至适用于神经网络算法。1992 年，日本庆应义塾大学的 Yoshiyasu Takefuji 牵头发表的一篇论文 https://www.sciencedirect.com/sc ... ii/092523129290030S 首次讨论了这一问题，并建立了一个网络，使每次移动本质上都是网络中的一个神经元。

  这些骑士问题的吸引力以及由此产生的令人惊讶的丰富性和深度说明了数学本身。数学有一个经常被忽视的普遍特征：其模式和解决方案的内在美。

  对于许俊珥来说，这种认识来自于艺术追求和看似无关的游戏谜题，说明了通往数学成功的道路是如何随着走在这条道路上的个人而因人而异的。

参考资料

https://scilogs.spektrum.de/hlf/ ... ss-knight-problems/

https://www.nytimes.com/2022/07/ ... matic-geometry.html

https://www.sciencedirect.com/sc ... ii/092523129290030S

https://youtu.be/DjZB9HvddQk

https://www.heidelberg-laureate-forum.org/laureate/june-huh.html

小乐数学科普：他曾经辍学成为一名诗人。现在他获得了菲尔兹奖——译自量子杂志 Quanta Magazine

小乐数学科普：2022 年菲尔兹奖获得者简介

菲尔兹奖得主许埈珥侧记三篇：北大校友谈六月，何妨吟啸且徐行

小乐数学科普：那数，那人—— 2022 菲尔兹奖得主雨果·度米尼尔-柯平 Hugo Duminil-Copin 作客HLF海德堡桂冠论坛

小乐数学科普：2022年的4位菲尔兹奖得主在 2023 年国际数学日的寄语（图文纯享版）

原创 Andrei Mihai zzllrr小乐 2024-05-05 10:17 江苏