[在 criblate.com 提交字幕更正] 2025年，来自世界各地的600多名青少年聚集在澳大利亚阳光海岸参加国际数学奥林匹克竞赛。这项比赛包含六道极具挑战性的题目，其中第六题是迄今为止最难的一题。尽管每位参赛者都是各自国家顶尖的世界级解题高手，但只有不到1%的学生在这道题上获得了满分。这似乎也是最后一道由人类解决的IMO题目，而AI无法解决任何难题——这句话如果放在五年前，对于熟悉竞赛数学的大多数人来说简直是荒谬的。如果你不在这个圈子里，你需要理解的是，这些题目被设计为需要想象力和创造力元素。这绝不仅仅是死记硬背或计算。解决这类问题并不意味着给出一个正确的数值答案，而是写出完整的严格证明。比赛的精神在于，寻找证明的过程应该要求对特定情境有细致而深刻的理解。
如果我们把时间倒回2021年，尽管当时AI在棋类游戏中已经取得了令人印象深刻的成果，自然语言扩展定律也变得清晰明了，但许多人仍将IMO视为完全不同的游戏。它需要严谨性与创造力的结合，而在撰写证明时你可以做出的逻辑步骤搜索空间实际上是无限的。事实上，我在2023年参加Dwarkesh Patel的播客时，他曾问过这个问题：当AI模型能在国际数学奥林匹克竞赛中获得金牌时，那是否就意味着通用人工智能（AGI）？然而就在第二年2024年，Google DeepMind的AlphaProof团队推出了一款模型，回答了当年考试六道题目中的四道。这里有一个小注脚：该系统需要人类手动将问题从英语翻译成Lean，这是一种数学证明即程序的编程语言。但AlphaProof系统处理了寻找证明的核心内容，即便只是用另一种语言表述，这本身就让许多人感到惊讶。
到了2025年，多个不同组织的模型尝试参加测试，这次既有采用Lean方法的，也有完全通过自然语言端到端进行的。如今模型回答了比赛中的所有题目，除了第六题。而到了2026年……只需提示可用的公共推理模型就足以正确回答所有六道题目。这极大地低估了这些模型在过去几年中在数学领域取得的进步。IMO几乎感觉像是作为基准测试的远古历史，因为在过去一年里，一切都已经加速进入了研究数学领域。我将在最后更多地讨论这一点，到时候我会说很多关于AI与数学的事情。但此刻，这个视频主要不是关于AI的。更重要的是，它是对一个非常美丽的问题的深入探讨。
随着我们探索解决它的路径以及所需的洞察，我认为反思一下为什么少数才华横溢的学生能找到答案而机器不能是有趣的。我实际上向Thang Luong提出了这个问题，他是Google DeepMind团队的研发总监，该团队开发了攻击当年测试的推理模型。他给出了一个非常有趣的答案。他说：“我们真的没有教模型学会耐心。它不会花时间理解问题，去感受问题，而不是试图去解决问题。”随着我们今天的逐步深入，我相信你会同意耐心是绝对需要的因素之一。你也会明白他关于“在尝试解决之前先理解”的含义，但我想至少补充一个额外的要素。就我与模型的互动而言，它们似乎对什么使问题或策略变得美丽缺乏很好的感觉，而找到这里的解决方案绝对得益于对美的欣赏。
让我们开始吧：这个问题是什么？作为学生， figuring out 如何解决问题会有什么感觉呢？展示问题时，题目开始写道：考虑一个2025乘以2025的单位正方形网格。显然，这在图示上有点笨拙，所以对于屏幕上的动画，让我们从更小的尺寸开始，比如10乘以10。Matilda希望将一些矩形瓷砖（可能大小不同）放置在网格上，使得每块瓷砖的每条边都位于网格线上，并且每个单位正方形最多被一块瓷砖覆盖。这很合理，瓷砖之间不重叠。现在问题陈述要求我们找到遵循某个关键规则的最小瓷砖数量：每行必须恰好有一个单位正方形未被任何瓷砖覆盖。我将用X标记这些间隙，同样地每列也恰好有一个单位正方形未被任何瓷砖覆盖。
所以在我们的10x10小案例中，铺砌中有10个不同的间隙。但在实际问题陈述的完整网格中，铺砌中将总共有2025个间隙。我们不妨先建立一些关于这类铺砌外观的直觉。例如，回到我们的10x10案例，这里有一个使用总共21块瓷砖的例子。你会注意到它遵循关键规则：没有两个X位于同一行或列中。但如果我们要最小的瓷砖数量，这肯定不是最好的。通过选择不同的集合，在不同的位置留下间隙，这里的例子给了我们十七块瓷砖。即使这还有改进的空间；这里是又一次尝试，仅用十六块瓷砖就完成了任务。鉴于这是国际数学奥林匹克竞赛，你的任务不仅仅是给出这个最小瓷砖数量的数值答案，而且也不仅仅是展示如何实现该最小铺砌的构造。
这种构造将是其中的一部分，但真正的挑战在于严格证明无论你找到的最小值真的是最好的。当你在脑海中玩弄这个时，你可以感受到为什么这是一个困难的问题，因为很难想到……关于瓷砖放置的可推广描述。也许最简单的情况是将所有X放在对角线上，然后使用水平瓷砖覆盖剩余区域。如果你添加一个边长为n的网格，你会注意到这里右侧的瓷砖数量是n-1，同样地对于左侧也是如此。
左侧部分，这给了我们总共 2(n-1) 块瓷砖。然而，这种构造相当明显，不太可能是国际数学奥林匹克竞赛（IMO）所要求的答案。因此，你真正渴望的是另一种放置 X 的通用方法，以及围绕它们放置瓷砖的一般方式，从而得到一个随 n 变化的、比这更小的计数。
那么，你该如何着手解决这样的问题呢？究竟从哪里开始？现在退一步看，我认为关于解题的一个非常重要的普遍教训是：看似天才的表现通常是经验的残留。洞察并非凭空而来，在这种情况下，在我们一头扎进那道具有挑战性的第六题之前，我希望你要有耐心。我想告诉你
一个看似完全不同的关于切割立方体的脑筋急转弯。它比 IMO 题目更简单，非常有趣，尽管看起来它与铺砖谜题毫无关系，但我的目的是强调这种过去的经验可能会为着手解决主要问题提供第一步的启示。所以这里是这个脑筋急转弯：想象
你有一个 3x3x3 的立方体，你想把它切成 27 个不同的 1x1x1 小立方体。你如何用最少的切割次数做到这一点？规则是，你用刀进行的每一次切片都是沿着一个单一的平面；没有之字形或锯齿形的切割。一开始，有一个相当明显的方法可以用六次切片来完成：你在每个
坐标方向上进行两次平行切割，将边缘分成三等份，将每个面分成九等份，并将整个立方体分割成这 27 个一乘一的块。但这里有一个主要的变体，会让这个问题变得有趣：假设在每次切片后，你都可以重新排列你所拥有的任何碎片，也许堆叠现有的块，以便下一次切片可以穿过更多的总
材料。再次提问：如何用最少的切片次数将这些切成 27 个不同的一乘一立方体？暂时从立方体推广开来，如果你只是在切割任何形状，每一次新的切片最多只会使当前的碎片数量翻倍。这是假设你可以重新排列所有碎片以落入下一次切割所在的平面中。
这意味着四次切片最多只能给你十六个不同的碎片，因此我们可以排除这种可能性，因为我们试图将立方体切成这 27 个碎片。现在五次更有趣一些。原则上，通过重新排列，五次切片最多可以给你 32 个小碎片，但在这里我们 specifically 需要这些小碎片处于一个平面中。这是
为了成为 1x1x1 的立方体。目前还不清楚我们在切割过程中可以进行什么样的巧妙重新排列来实现这一点。如果你以前没见过这个问题，请暂停一下，试一试。我有点讨厌过早地剧透这样一个好问题，但对于今天的视频来说，我不得不这样做。我提起这件事的唯一原因是答案将有助于突出洞察
关于我们如何着手解决那道具有挑战性的第六题。好了，你准备好了吗？诀窍是关注那个内部的 1x1x1 立方体。为了将其完全切出，它的六个面中的每一个都需要一次独特的切片。单次切片永远无法同时释放超过一个面。因此，即使你被允许以任何你想要的方式重新排列和堆叠它们，无论你能想象出多么富有创意的方法，
simply 没有可能使用少于 6 次的总切割次数。我提起这件事的要点是，洞察并不在于寻找更少切割次数的某种巧妙策略，而在于如何证明 6 是最优数量。而这个证明涉及关注那个内部立方体的面。你可能可以看到这如何与我们的铺砖谜题相关联。最终目标不仅仅是找到
我们可以使用的最小瓷砖数量（虽然这本身已经是一个有意义的挑战）；最终目标是证明我们找到的是最好的！我想提出，如果你在过去见过这个立方体谜题或类似的东西，它可能会引导你的思维去考虑我们图表上所有被 X 标记的正方形的边缘。你可能会注意到
每个这样的边缘都必须与一块瓷砖相关联。我们在另一个方向上也有不错的对应关系：由于没有两个 X 在同一列，给定瓷砖的左边或右边最多只能接触一个 X。同样地对于顶部和底部，给定瓷砖的四条边每条都最多接触一个 X。为了让你对如何实际使用这一点有一些直觉，
我想让你看看这两种不同的铺砖图案，其中右侧使用的瓷砖明显少于左侧。右侧那个图案为什么更有效率？首先想象放置 X 是有帮助的，在我的脑海中，“没有两个可以共享行或列”这一关键规则让我想到了互不攻击的车（国际象棋中的 Rook）。让我们想象
突出显示每个 X 标记正方形的四条不同边缘，然后每次你在棋盘上添加一块瓷砖时，我们就会关闭该瓷砖所接触的突出显示边缘。随着你不断放下新的瓷砖，关闭它们接触的任何突出显示边缘，有些瓷砖设法关闭了多个边缘，有时多达 4 个，而其他你放下的瓷砖只关闭了 1
甚至 0 个突出显示边缘。但无论瓷砖的排列如何，你都知道最终每个突出显示的边缘都必须被关闭。好吧，几乎全部有四个例外基于那四条边接触图表的外部边界。这实际上给了我们一种很好的方式来描述左侧图像中哪些部分效率较低。注意所有这些瓷砖
都只接触 1 个甚至 0 个 X。相比之下，看右边，注意这些瓷砖中的每一个都接触总共 4 个 X。从这种角度来看，每个都是尽可能高效的，因为瓷砖的主要职责是覆盖那些间隙之一的边缘。这种直觉实际上对于后续所有内容都足够基础，值得将其写为
一个猜想：最高效的铺砖应该是尽可能多的瓷砖接触 4 个不同的 X。如果任何瓷砖接触的少于这个数量，感觉就像是浪费了它的潜力。因此，考虑到这一点，我们可以暂时从网格中抽象出来，只想象这些瓷砖自由漂浮，每个都在其边界附近的某个地方接触 4 个 X。目标是
以某种方式将这些拼在一起，就像拼图一样。为了理解这里的约束条件，我希望你只关注其中一个X，并想象在它的右侧上方和下方各放置两块其他瓷砖。当我这样做时，你有没有注意到这个图表中有什么低效之处，或者至少即将变得低效的地方？你希望图中的每一块瓷砖都接触四个X，但我们新引入的这两块会在它们的左侧边缘产生冲突。因为它们的左边是对齐的，而且同一列中不能出现两个X，所以它们不可能同时接触左侧的一个X。其中一块必须放弃这一点。
每当一个X接触到其边缘中间的某块瓷砖时，同样的基本问题就会出现。另一方面，如果我们把这个X滑到角落上，注意我们如何可以舒适地在它周围以这种风车模式放置四块瓷砖而不会引起任何必要的冲突。这给了我们下一个直觉，即我们不仅希望每块瓷砖接触四个X，更具体地说，如果它们要和谐共存，这些X必须位于瓷砖的角上。
到目前为止，我们仍然有自由选择任何形状的瓷砖的自由，但既然正方形非常对称，而数学往往在尊重其对称性时奖励你，不妨先从尝试正方形开始。此外，对于给定的周长，正方形覆盖的总面积更大，所以当我们希望最终用尽可能少的瓷砖覆盖整个网格时，这感觉就像是高效的选择。
一旦你假设最优铺砖使用正方形瓷砖，且X围绕其角落以风车模式出现，将它们拼在一起确实就像拼图一样，而且是非常令人满意的实体拼图。注意这些零件像这样堆叠得非常好。在这里我们任意选择尝试测量5乘5的正方形瓷砖。所以，当我们把四块叠在一起时，如果我们要再加一块……这会导致上面的这个X与下面的那个X落在同一列。
因此，为了尽可能多地拼合在一起，让我们把下一块附在右边的这里。然后继续构建图表。如果你像这样继续下去，你最终会得到一个非常令人愉悦的略微倾斜的4乘4正方形瓷砖图案，每个周围都有一个X的风车模式，总共使用25个X。你会注意到这些X确实位于不同的行和列中，所以如果我们在周围画一个大网格，它就符合最初的问题描述。
我们确实需要在边缘添加几块瓷砖来填充它们，所以并不是每块瓷砖都接触四个X，但内部的所有瓷砖确实如此，所以这感觉非常高效。从5乘5的瓷砖开始是一个任意选择；如果我们改为从4乘4的正方形瓷砖开始，我们会得到这个更小的排列，总共有16个空位。如果我们从3乘3的瓷砖开始，那将给我们一个总共有9个间隙的东西。
一般来说，如果我们让变量k代表我们开始使用的正方形瓷砖的边长，这种形成的图案为我们提供了一种非常令人满意的方式来铺砌一个侧面长度为k^2的大网格。如果你是一个解题者，到这个时候你应该在微笑了，因为如果你要参加2025年的IMO（国际数学奥林匹克竞赛），你绝对会知道2025是一个平方数，具体来说是45的平方。
所以如果我们将k设为45，这就为原始问题陈述提供了一个非常漂亮的铺砖方案，我们可以现在推测这代表了最少可能的瓷砖数量。利用2025这个数的平方性质使得这种情况感觉极其有希望，是IMO可能想要我们找到的那种最优构造。再次强调天才经验的残留这一主题，如果你是一名2025年IMO的参赛者，还有另一种方式可能会让你被这种图案所吸引。
那就是在澳大利亚阳光海岸机场（你将在该年比赛期间降落的地方），这实际上是你在机场地板上看到的瓷砖图案。太棒了，我们现在至少对最佳铺砖的样子有了猜想，让我们继续将其写成一个公式，即描述我们使用的瓷砖总数的公式。在视频的其余部分，我想继续保持k代表那些正方形瓷砖的边长，而k^2将代表大网格的边长。
在我们用k等于5绘制的原始案例中，你会注意到正方形瓷砖的总数是16，更一般地我们可以将其写为(k-1)^2。但是那些边界周围的瓷砖呢？我们使用了多少块？在这种情况下，你会注意到边界的每一侧使用4块这样的瓷砖。而且不难看出这推广到了k-1。所以我们可以再加4乘以(k-1)到我们的总数中。
如果你更喜欢展开它，这将表明最终计数看起来像k^2加2k减3。在我们的页面上圈出这个，这给了我们一个真正的、可以深入研究的切实猜想。感觉很好，但我们离完成原始问题还很远，因为我们的目标现在是证明这个表达式给出了所需的最小瓷砖数量。
任何其他可能的排列，无论X在哪里以及瓷砖如何围绕它们放置，都必须使用比这更多的瓷砖。或者至少我们需要证明在网格边长是平方数的特殊情况下也是如此。但是你该怎么做呢？你如何证明这样的事情？所有可能的X排列和围绕它们的铺砖模式的集合非常复杂。那么你甚至如何获得一个立足点来做出涵盖所有这些模式的严谨声明？
看，这才是真正的挑战。当然会有真正的挑战。这是IMO中最难的问题；没有任何世界会让这变得容易给我们。但我们实际上有一个优势，因为记得我是如何激发整个构造的？我们专注于瓷砖需要覆盖其中一个X的每一条边缘这一事实。这种直觉的魅力不仅在于它指导我们去构造，虽然这本身就很令人愉悦；它还为我们提供了寻找所需证明的立足点。
你看，这个图表中X的总数是k^2，对于屏幕上的小例子来说只是9。如果你突出显示这些被划掉的正方形的所有边缘，那将给出4k^2条高亮显示的边缘，而且你知道你放下的每一块瓷砖最多接触4条高亮边缘。所以这立刻给了你一个界限，告诉你至少需要k^2块总瓷砖。
实际上，那并不完全正确，因为……
图中整个边界上有四条高亮边不需要被任何瓷砖覆盖。因此，真正相关的、最终需要接触瓷砖的高亮边只有 4k² - 4 条。同样，每块瓷砖最多接触其中的四条边。所以实际的推论是，你至少需要 k² - 1 块瓷砖。一方面，太棒了！我们成功证明了下界并写出了表达式。但另一方面，这个下界比我们要的弱。如果你看我们实际的猜想——那个来自 hopefully 最优构造的猜想——里面还有另一项，与 k 成正比，而 k 是网格大小的平方根。
这很有道理，因为如果你看我们制作的最优排列（或者至少是我们希望是最优的），并不是每块瓷砖都接触四个叉号。边界周围的那些只接触两个。坦白说，当我在笔记本上琢磨这个问题时，我花了很长时间试图找出一个基于限制位于图表边缘的瓷砖总数的优雅论证。如果我要诚实地展示解题过程，我会向你展示所有那些死胡同，那也会让这变成一个九小时的视频。所以我就不详述了，简单说：没什么真正奏效。
实际上有一个根本原因。但这并不意味着我们不能继续富有成效地利用关注高亮边的想法。让我们回想一下最初用来激发一切灵感的切立方体谜题。那个谜题的关键在于如何证明至少需要 6 次切片，方法是使用一一对应关系——即内部立方体的面与刀切之间的对应。而我们目前的铺砖问题，正如我所描述的，并不那么干净；它更像是叉号正方形的边与必须接触它们的瓷砖之间的四对一关系。
但实际上，有一种更简单的方法来论证你至少需要 k² - 1 块瓷砖，那就是尝试建立一对一的关联。与其高亮每个叉号正方形的所有边，不如只高亮它们所有的右边。每条这样的右边缘必须接触一块瓷砖，重要的是任何给定的一块瓷砖最多只能接触一条这样的边。原因是没有两个叉号出现在同一列中。同样，在边界处也有例外：最右边的边缘实际上不需要接触瓷砖。所以这再次给了我们一种证明方法，得出至少需要 k² - 1 块总瓷砖。
但这种框架感觉更有成效，因为你可以更清楚地看到哪里效率低下。你会注意到我们漏掉了大量瓷砖，特别是在图表的左侧；同样地，如果你选择只高亮顶部边缘并将它们与相应的瓷砖关联起来，你就会漏掉许多位于图表底部的瓷砖。对于任何单一方向都是如此；你遗漏的瓷砖聚集在一侧。我常说，数学奖励尊重对称性的人，而我们现在看到的是它如何惩罚不这样做的人。选择任意方向显示出关联中的明显弱点，这种弱点反映在我们写在上面的不等式的薄弱中。
该关联证明了至少需要 k² - 1 块瓷砖，但请记住我们真正想要的是什么。我们要证明的是至少有 k² + 2k - 3 块总瓷砖。这是来自我们希望是最优排列的那个数字。所以，对于坐在 IMO 赛场上竞争、旨在证明这个更紧密下界的精明的解题者来说，你能做什么？现在是暂停思考的好时机。我想再次强调我们正在处理的问题有多难。
请记住，这是 IMO 的 P6（第六题），只有六名学生在这道题上得了满分，而且它是所有 AI 都绊倒的唯一一题。所以可以说，我们写的任何证明都将很难找到。事实上，在继续前进之前，我认为现在是伸展身体、稍作休息的好时机。对于任何可能对技术职业机会感兴趣（无论是实习还是全职）的观众，我想在这里做一个简短的介绍。基本上，这里的安排是：与其进行普通的视频赞助（我会插播并试图向你推销产品或订阅），我觉得让 3Blue1Brown 以招聘合作伙伴关系的形式运作更符合我的理念。
所以，如果你访问 3b1b.co/talent（即 talent.3b1b.co），你会发现一组具有两个特性的公司。一是它们希望雇佣像你这样好奇且具备技术思维的人——那些观看关于 IMO 最难问题视频的人；二是我见过那里的团队，并有明确的证据表明人们喜欢在那里工作。在该页面上，你会看到技术解谜者、我与团队的采访以及其他材料，帮助你了解每个团队文化的独特之处。这就是我想说的。你可以看看这是否相关，但现在让我们回到证明中最难的一步。
让我们退一步，总结一下我们目前的情况。我们的策略是突出显示特定的一组边，然后论证每条边都接触一块独特的瓷砖，从而推断出瓷砖数量至少与高亮边的数量一样多。虽然这没有给出我们想要的下界，但我们确实有了关于该策略具体哪里薄弱的直觉。只在一个方向上高亮边给出了在图表一侧附近的瓷砖看起来更紧密的对应关系，但它遗漏的大多数瓷砖聚集在对侧。
我们想要的、目前的目标是将 k² - 1 的下界提高到更大的数字 k² + 2k - 3。一个自然的问题是，作为解题者的你可能会问：如何修改相同的策略来弥补这个弱点？你能否高亮更多的边（最好是 k² + 2k - 3），以某种方式避免专注于任何单一方向所带来的低效？现在，当你这样做时，你必须非常小心。为了让这种策略奏效，你必须确保如果你遍历所有……
对于每个瓷砖，询问它接触了多少条高亮边，答案总是至多一条。该策略的基本前提是论证每条高亮边上至少有一块瓷砖，因此我们必须确保没有重复计数。现在，我描述的目标中有一点奇怪之处。想想表达式 k² + 2k - 3，以及当 k 变得越来越大时每一项的样子。如果这旨在描述最终的高亮边数量，它暗示在那些更大的案例中，某种方式下大多数但不是所有的 X 都只有一条高亮边，而其中一些数量级约为其平方根两倍的 X 则有多条高亮边。
这可能会让人觉得奇怪，甚至几乎与我们追求优美对称构造的目标背道而驰。老实说，下一步可能是整个论证中最难解释动机的一步，但我认为从构思的高层概要开始会有所帮助。正如我所说，我们知道仅仅高亮所有 X 的右侧边在图表的右侧附近感觉效率更高。那么，如果只在该完整网格的某个特定向右区域中的 X 才高亮其右边呢？此时我对那个“向右区域”具体指代什么保持一点模糊。
同样，也许你只想高亮位于图表向上区域中的 X 的顶部边，从而希望能与该区域内的瓷砖建立更紧密的联系。同理，仅当它们位于某个向左区域时高亮左边，仅当它们位于底部区域时高亮底边。再次强调，我对这四个区域具体是什么以及定义它们之间边界的内容保持模糊，但我现在只想勾勒一个策略的轮廓。这个策略受避免我们之前仅关注单一方向时所看到的弱点来源这一想法驱动。
这种模糊的直觉也有助于指出额外的高亮边可能来自何处。我们知道我们需要的瓷砖数量多于 X 的数量，因此无论我们如何最终定义这四个区域，任何位于这些边界之间的 X 都可能会获得多条高亮边，因为它在某种程度上同时属于两个区域。为了使这一切具体化，让我们受这种将图表划分为四个区域的松散想法驱动，缩小到一个更小的例子。每个区域都偏向一个方向，我将画一条向右上延伸的路径连接一系列 X，同样再画另一条向右下延伸的路径。
这使我们在整个图表上留下一个大的波浪形十字交叉。我想穿过 X 的原因是，我们希望它们落在边界上，以便对于在边界的这些 X，如果我们高亮多条边的话能得到更高的数量。现在选择了这样两条路径后，我们可以更精确地定义区域的方式：如果一个 X 位于两条路径的右侧，则高亮其右边；如果它坐在两条路径上方，则高亮其上边；左右两侧同理。对于边界上的任何 X，根据其所在的象限高亮其两条边。
这感觉是一件值得做的事。我们知道最终需要的高亮边数量略多于 X 的总数。记住目标：我们为什么要高亮边？我们希望论证，无论网格上 X 的排列如何，也无论覆盖剩余方格的瓷砖图案是什么，我们要证明使用的瓷砖数量必须至少等于我们高亮的边数。只要每条边接触一块瓷砖，并且重要的是每块瓷砖至多接触一条高亮边，这就会成立。
你会注意到屏幕上的例子，如果我们在每个瓷砖上标记它接触的高亮边数量，你确实只会得到零或一。从来没有一块瓷砖同时接触多条高亮边的情况。值得深入思考为什么在这种情况下确实如此。按照我们目前定义的设置，为什么一块瓷砖不能接触两条高亮边？这是一个非常重要的问题需要回答，因为整个论证都建立在这个假设之上。
专注于一个特定的瓷砖会有所帮助，也许是这个位于左侧区域的特定瓷砖。你会发现这块瓷砖实际上接触了四个 X，但只有一个 X 的高亮边接触到该瓷砖。你可能会问，为什么它接触的其他那些 X 没有高亮边碰到这块瓷砖呢？好吧，这块瓷砖位于向左区域，所以它上方的任何 X 只能高亮其左边或上边。
我们知道根据我们定义这些区域的方式，底边根本不可能被高亮。同样地，对于瓷砖下方的任何 X，其顶边也不可能被高亮；而左边的 X 肯定不能高亮右边，因为那要求它位于图表的向右区域。换句话说，我们将网格划分为四个总区域的直觉不仅加强了高亮边与瓷砖之间的紧密关联，还保持了那个关键属性：没有两条高亮边可能接触同一块瓷砖。
这里这张图正是本视频证明的核心。但我们仍有一些工作要做，以展示为什么这种设置确实给出了我们要追求的那个特定紧密界限，即 k² + 2k - 3 这个数字。这归根结底在于计算在这种新方案下我们总共高亮了多少条边，而这又取决于理解有多少个 X 位于这两条穿过图表的边界线上。
正是在这个时候，最后有助于贴上标签来描述所有 X 的位置，而不是纯粹从图形角度思考。也许在每个 X 上方写下一个数字描述它所在的行。由于每一行恰好有一个 X，这意味着所有这些标签代表了从 1 到 k² 的每一个可能数字，只是顺序被打乱了。换句话说，这是一个排列。
当你画一条向右上延伸的路径连接其中一些 X 时，你会注意到它们对应的标签是严格递增的。在术语中，人们会称之为排列中的递增子序列。同样地，对于你画的向右下延伸的路径，如果圈出
每个 x 对应的数字构成一个递减子序列。让我们称那个递增子序列的长度为 A，递减子序列的长度为 B。如果你想计算高亮边的数量，请注意图中所有的 k² 个 x 中，每一个都至少有一条高亮边。或者更准确地说，几乎每个都有。实际上应该有四个例外情况，即那些接触网格边界的 x，因为它们不需要触碰瓷砖。所以我们要减去这部分。但是还有一些额外的情况，因为递增子序列上的每个 x 都会多出一条边，这给我们的表达式增加了 a；同样地，递减子序列上的每个 x 也获得一条高亮边，给总数增加了 b。
如果我们真的想注重细节——而我们必须如此——还有另一种可能性：一个 x 同时位于两条路径上，即递增和递减子序列。在这种情况下，它实际上会有四条边都被高亮显示，但按照我们目前的计数方式，它只被计算了三次——一次是因为它的存在，一次是因为它在递增子序列上，还有一次是因为它在递减子序列上。因此，在这种特殊情况下，我们需要在总数中再加一。到这里为止，我们得到了一个具体的表达式，它 tantalizingly（令人向往地）接近我们要找的结果。
到目前为止，我们实际上已经证明了：对于你构思出的任何可能的 x 排列（由从1到 k² 的数字的某种置换描述），如果你选择一个长度为 a 的递增子序列和一个长度为 b 递减子序列，你可以保证无论情况如何，所需使用的瓷砖数量必须至少达到这个数值。如果将这个结论与我们试图证明的猜想进行对比，自然的希望是论证 A 加 B 必须大于或等于 2k，即网格边长的两倍平方根。
这显然很接近且非常诱人，但也可能听起来有点奇怪：你怎么能保证无论 x 的排列如何，都能选择一个递增子序列和一个递减子序列，使得它们的长度之和至少是网格大小的两倍平方根？首先，我们可以规定 A 不仅代表任意递增子序列的长度，而是最长可能的那个。事实上，为了更具描述性，让我们改变它的名称并称之为 LIS（最长递增子序列）。
同样地，我们有自由指定选择哪条特定的向下路径，所以它不妨是最长的可能递减子序列，让我们将其长度称为 LDS。稍微调整一下，我们证明的最后一步将是展示这两个长度的平均值始终必须大于或等于 k，这里的 k 是置换大小的平方根。这个最终事实不再与网格有太多关系；它是一个关于置换的纯粹事实，我们可以让视觉元素暂时从网格中抽象出来。
也许我们可以用高度等于该数字的条形图来表示这些数字中的每一个。你可能会注意到，所有递减子序列都非常短的置换往往具有非常长的递增子序列；反之亦然，任何所有递增子序列都很短的置换都会拥有非常长的递减子序列。为了完成证明，我们需要使这种权衡定量化。
我们需要展示无论我们处理什么样的置换，这两个数量的平均值必须至少是置换大小的平方根。这有点拗口，所以如果花点时间暂停并消化这个目标究竟是什么也没关系。我也想承认到目前为止我们已经经历了很多，在一个证明之中再抛出一个证明可能会超出我能合理要求你保持专注的程度，但请坚持一下。我们要做的最后一步是一个真正的瑰宝。
我还想诚实地说，对于一位走到这一步的实际奥林匹克学生来说，他们可能会引用他们在训练中见过的东西——埃尔德什-塞凯赖斯定理（Erdős-Szekeres theorem），我们稍后会讨论它。但我做这个视频的目的不仅仅是凭空引入一些事实，我真的喜欢让一切感觉像是你可以自己发现的东西。这给原本就漫长的旅程增加了几分钟，但我认为你会同意这是值得的。
好吧，所以我们正在思考最长递增和最长递减子序列，为了建立一些直觉，让我们只看极端情况：平凡置换，即按顺序列出从1到 N 的所有数字。这有一个长度为 N 的最长递增子序列，而每个递减子序列的长度仅为1。你可以做的另一件事是先按顺序列出所有偶数，然后列出所有奇数。在这种情况下，最长递增子序列的长度至少为 n/2，而现在最长递减子序列的长度是 2。
我说“至少”n/2 而不是恰好 n/2，是因为当 n 可能是奇数时的情况。继续这一趋势，如果你以3为步长计数，最终你会得到一个置换，其中最长递增子序列的大小至少为 n/3，而最长递减子序列的大小为 3。现在如果你仔细思考这一族例子，你可能会得出结论：这两个数字的乘积必须始终大于或等于 n。
这个家族中其实有一个例子看起来非常熟悉。如果 n 恰好是一个平方数，比如 k²，你最终得到的正是对应于我们最优网格排列中 x 的模式。在这种情况下，对于最长递增子序列有很多选择，但它们的长度都是 k，屏幕上的视觉画面给了你一个小小的提示。同样地，所有最长递减子序列的长度也都是 k。
在特殊情况下，两者的乘积是 k²，这恰好就是置换的大小。基于所有这些激励性的例子，我们的猜想是更一般地讲：对于任何置换，这个乘积将大于或等于 n。现在如果你将这个猜想与我们实际上试图证明的目标进行比较——即展示这两个长度的平均值必须至少是置换大小的平方根……
二是至少为 n 的平方根。这些看起来可能不同，但对奥林匹克竞赛学生来说，这显然能得出我们所需的结果。你看，任何这类学生都会倒背如流的一个非常常见的不等式是：任意两个数 a 和 b 的算术平均数 (a+b)/2，总是大于或等于这两个数的几何平均值 sqrt(ab)。因此应用到我们的例子中，l_i 和 l_d 的算术平均数必须大于或等于它们乘积的平方根；如果我们的猜想成立，那么整个表达式将至少为 sqrt(n)。
请记住我们在此处关心的原因是：之前关于高亮边缘的论证中，那两条将网格分成四个区域的路径给出了一个基于这两条路径长度的表达式。我们要证明这个值至少与目标表达式一样大，即最优网格构造中使用的瓷砖数量。这归结为声称这两条路径的长度之和至少等于 2k，而根据我刚才提到的算术-几何平均不等式，只要该猜想成立，这就会是真的。
即这两条路径长度的乘积始终至少为 n（排列的大小）。如果这听起来需要记住的东西太多，请允许我提醒你我们正在处理的是一个多么困难的问题。关键在于，一切现在都归结为这一个猜想。在你和我坐下来反思这个问题的更广泛意义之前，我们还有最后一英里要走，需要解释为什么这个不等式成立。
你和我并不是第一个提出这一事实猜想的人。在排列的研究中，这众所周知，被称为 Erdős-Szekeres 定理。在实际的奥林匹克竞赛中，学生只需引用该定理即可完成证明。坦率地说，我可以省去你的认知努力并在此同样做：只需声明这是一个事实，或许链接到维基百科页面，然后结束视频。
但这个证明本身非常优美，我认为为了节省两分钟的视频时长而剥夺你欣赏它的乐趣是一种遗憾。所以请相信我，这是一个非常令人愉悦的收尾点缀，然后我们再退后一步进行反思。思路是只看列表的一部分，并询问在该点结束的最长递增子序列和最长递减子序列的长度。
例如屏幕高亮显示的那个，在该点结束的最长递增子序列长度为 2，而在该点结束的最长递减子序列长度为 3。我要你做的是把这些写下来作为一个数对，放在横线下方。事实上，我想让你对列表中的每个其他点也做同样的事情：用一对数字标记排列中的每一项。
现在你可能不清楚为什么要这样做，但为了明确其含义，再看一个例子：这里的横线之所以最长递增子序列长度为 3，是因为它左边有两条递增的线。但结束于该线的最长递减子序列长度仅为 2。这里巧妙的想法是，所有这些数对必须是唯一的，并且有一个非常漂亮的方法可以说明原因。
只关注两根线中的两根，假设左边的标记为 x 和 y。记住，我们处理的是一个排列，所以序列中的所有数字都是不同的，这意味着其中一根线必须比另一根高。如果第二根线更高，你总是可以将结束于第一根线的任何最长递增子序列（长度为 x）延伸一步到达第二根线，这意味着结束于该第二根线的最长递增子序列至少为 x+1。
同理，如果那根线更短，你可以取结束于第一根线的任何最长递减子序列（长度为 y），并至少延伸一步到达那根第二线，这意味着该第二线上的第二个标签始终应至少为 y+1。因此无论如何，第二对中的两个数字之一必须大于第一对中对应的数字，所以标签确实是不同的。
从这里开始，写下了一堆这样的数对后，很难不尝试通过将它们作为点绘制在坐标网格上来进行可视化。如果你仔细想想，整体最长的递增子序列看起来就像这里的最大 x 坐标（我围绕它们画出的边界框的宽度），而整体最长的递减子序列看起来就像最大的 y 坐标（该边界框的高度）。
此外，注意这个矩形的面积——其宽度乘以高度——与计算这里的格点数相同。由于排列的每个元素都对应一个唯一的格点，你可以得出结论：这两个数的乘积必须大于或等于排列中的元素数量。就是这样，这就是我们的猜想。我觉得这真的很可爱，太美了以至于不想不分享它。
有了这个最后的部分，让我们退后一步总结我们刚才所做的一切，因为确实很多。问题本身要求找出留下每列一个间隙和每行一个间隙的最小瓷砖数量。我们的主张是，最小数量的瓷砖来自这种特殊的网格模式：一种令人愉悦的、由边长为 k 的正方形瓷砖填充的模式。我们计算出的总使用瓷砖数量为 k^2 + 2k - 3。
为了证明这一点，我们在视频的前半部分花了大部分时间引导并激励这个图表的出现。这也是你将要写下的实际证明开始的地方。你会说，对于任何可能的铺砖方式，考虑它们留下的间隙（我们用 x 标记的这些网格方块），并画出两条不同的路径：一条连接最长递增子序列，另一条连接最长递减子序列。
这两条路径将图表分成四个单独的区域，然后我们利用这些区域定义了一个特殊的所有 x 标记正方形边缘的子集，我们要高亮显示它们。在右侧区域时高亮右边缘，在上侧区域时高亮上边缘；如果在边界上有两条边（你记得所有那些规则）。我们之所以这样做，是因为我们可以论证……
每一条被高亮的边都对应着一块唯一的瓷砖，这意味着瓷砖的数量至少与高亮边的数量一样多。在此基础上，我们计算出高亮边的数量为 $k^2$ 加上最长递增子序列的长度再加上最长递减子序列的长度，最后减去四。此外，如果这些路径相交，你实际上可以再加一
这就会变成负三。而在这里其实有一个细微之处是我到目前为止略过的：即使路径彼此不相交，你仍然可以在总瓷砖计数上加一。因为如果它们在被打叉的方格中没有相交，那就意味着它们会在某块瓷砖中相交。在那种特殊情况下，中间的那块特定瓷砖将不会
接触任何高亮边。所以你可以放心地将一加到你的计数中。关键在于，这里的表达式确实给出了瓷砖数量的一个下界。这反过来足以证明我们想要的实际界限，即来自最优网格铺砖的表达式 $k^2 + 2k - 3$，只要这一部分——即这两条路径长度之和
确实大于或等于 $2k$。这正是我们在上一节中，结合算术-几何平均不等式和埃尔德什-塞凯赖什定理所证明的内容。将这个表达式代入 $k=45$，你就得到了原问题的数值答案。但再次强调，那个数值答案只是要点的一小部分。真正的重点在于
构造过程以及找到某种严谨的证明来表明它是最优的。这可能需要一段时间，甚至需要相当大的耐心，但我们确实做到了这一点。
那么重点是什么？通过观看如何解决这样的问题，我们学到了什么？实际上，我觉得面对面做这个结尾可能更好。你知道，我把整个问题介绍为人工智能无法解决的最后一道 IMO 题目。这可能意味着我们可以自然地将其总结为类似 Lisa Dahl 与 AlphaGo 之间的第四局比赛，也就是人类在机器变得绝对更强大之前的最后抵抗。
我想象许多观众可能一直在思考的是，这道题中有什么特点使得人工智能难以解决？那里有一些自然的推测。你知道，我们花了很多时间在非常直观的直觉上。我想象这比纯粹的符号推理更难训练。一个更微妙的观点是 Dang Luong 提出的，即这种类型的问题你不能立即开始写解决方案。你必须先理解它并感受它，然后再写出那个方案。这种结构对于强化学习环境来说本质上更难处理。
但如果我思考自己与这个问题的个人关系……这个问题以一种完全不同的、而且可以说更重要的方式，与当前关于人工智能和数学的更广泛故事相关联，这与 AI 何时能或不能解决此类问题无关。我与 Nishad Dulkhar 合作制作了这段视频，当我们着手去做时，目标并不是为未解决的问题找到新的证明。显然已经存在了证明，YouTube 上也有这个证明。例如有一个叫 Dedican Cuts 的频道涵盖了包括这道题在内的许多 IMO 题目。
那么为什么要制作这段视频？我们认为有什么新的贡献？对我来说，知道一个证明只是深入理解给定数学知识的一小部分。这个特定的证明是我和 Nishad 看着它说：“好的，我看到这行得通，但究竟怎么想出这个呢？”你知道你定义了这个最长递增子序列、最长递减子序列，边与瓷砖之间的某些关联。但在没有任何引导背景的情况下，你可以跟随那些步骤，却感觉像是从天而降的意外之喜。
在视频中我谈到了发现构造过程与阐述证明的感觉之间存在质的差异。我没有提到的是，还有另一个层面的参与也感觉在质上不同，那就是创建一个叙事，让观众觉得那个证明几乎是显而易见的。我们知道这个证明并不显而易见。只有六名学生解决了这个问题。这是一个显然很难的问题。但如果我们做得好，我希望当我们最终落脚于阐述证明本身时，它不再感觉像是从天而降的意外之喜。
对我来说找到那种叙事是深深令人满足的。它非常有创造性。我总是觉得，通过理解证明之外的事物来学习数学，比仅仅理解证明让我对数学的理解更深。我认为甚至有必要给这种不仅仅是证明的其他东西起个名字。由于缺乏更好的名称，我就称之为“有动机的解释”。
跳出这个玩具问题到当前数学界的更广阔世界，机器能够产生非常著名的未解问题的证明。你所看到的是许多数学家退后一步反思数学的目的，即他们理解的实践一直是为了推进人类的理解。证明和开放问题的角色一直是作为指路明灯，帮助人们知道在哪里以及如何推动那种理解向前发展。
问题解决方案并不是你要将其插入世界应用并从中获得效用那样简单的事情。这比那微妙得多。更像是为了让人类找到这些证明，他们必须弄清楚思维模式、构建和新数学对象的结构。这提升了他们的理解力，使得那个证明变得可用。但有用的不是证明甚至结果本身，而是所有那些
周围的理解以及它可能对工程界产生的溢出效应。所以如果你能够生成不一定伴随人类理解的证明，那就完全违背了重点。但这提出了一个关于如何衡量学术进步的严肃问题，因为使用证明作为代理的想法深深植根于我们给予学术认可的方式中。这暴露了一个非常鲜明的需求，即需要一种新的、独特的方式来衡量某人的出版产出是否真的推进了人类理解。
就我而言，我认为“有动机的解释”这一想法可以在很大程度上填补这一空白。我认为我们作为一个社区应该尝试正式定义我们对“有动机的解释”的含义，然后将其提升
拥有同样的地位，并获得与证明历史相同的学术认可。关于这个话题我还有更多想法。我为特里·陶（Terry Tao）的博客写了一篇客座文章，讨论这个问题，我也在这个频道上录制了相关的视频。如果没有的话……如果你感兴趣，可以去看看。我猜测这将是我想表达的关于人工智能与数学问题的众多想法中的第一个。
不过，今天让我们把焦点重新放在这个非常有趣的2025年IMO（国际数学奥林匹克）问题上，我想以Patreon评论区里一句非常动人的话作为结尾。你们中的许多人知道，我总是为支持者提前发布视频。在这种情况下，其中一位支持者在评论区留下了他们朋友的一句话，这位朋友解决了这个问题：
“这道题并没有促进对数学的深刻理解。它并不比数学研究特别困难。相反，它的价值在于：当我解决它时，它温暖了我的心；一年多过去了，它依然让我感到温暖。就像一本好书或一首感人的歌曲一样，这里的价值是人性化的。”
称我为一个人文主义者吧，但我真心相信，作为一个数学发现，这道题的价值超过了普通的博士论文。