Knuth Verifies Rectangle Paving Conjecture as Stromquist Finds Proof

高德纳验证矩形铺砌猜想，斯特罗姆奎斯特给出严格证明 针对简化矩形剖分的经验计算揭示了紧致铺砌的渐近公式，其令人惊叹的代数化简随后得到了沃尔特·斯特罗姆奎斯特严格证明的证实。 在这场节日演讲中，唐纳德·高德纳（Donald Knuth）梳理了他对蒙德里安风格矩形剖分及极小“紧致铺砌”（即每个网格坐标均包含一条内部线段）的组合学研究。通过将构型分解为骨架规范类型，并利用母函数为切片扩展建模，他发现了适用于任意行数的主导项系数极其整洁的公式：$m^{2m - 3} / ((m - 1)!)^2$。高德纳详细介绍了在完成大规模计算验证后，审稿人沃尔特·斯特罗姆奎斯特（Walter Stromquist）是如何随后证明了这一猜想，并将其与具有迷惑性的高精度“假等式”以及其他未解问题进行了对比，例如比尔·戈斯珀（Bill Gosper）基于伽马函数的黄金比例恒等式，以及无限贪心皇后序列的分叉射线现象。 唐纳德·高德纳研究了矩形的“紧致铺砌”（即剖分为 $m + n - 1$ 个子矩形），并发现了渐近增长主导项的闭式公式：$m^{2m - 3} / ((m - 1)!)^2$。 (43:10) 在高德纳历经 6 小时运行时间、遍历 400 万种类型将该铺砌猜想计算验证至 $m=6$ 之后，审稿人沃尔特·斯特罗姆奎斯特给出了完整且严格的证明。 (48:11) 高德纳提醒，高精度的数值吻合并不保证结论为真，并援引了历史上某些恒等式在吻合达 11 位和 16 位小数后最终失效的案例。 (51:08) 在第一象限的无限贪心皇后问题中，坐标分叉为两条斜率渐近等于 $\phi$ 和 $1/\phi$ 的射线，该模式虽已验证至数千亿级别，但仍缺乏形式化证明。 (55:44)

In his 23rd Annual Christmas Tree Lecture, Donald Knuth explores the nature of mathematical research through the discovery, computational verification, and eventual proof of combinatorial patterns, centered on minimal rectangle dissections termed 'tight pavings.' Reduced Rectangles and Tight Pavings (3:46) While developing a generalized dancing links algorithm for 'The Art of Computer Programming' in early 2017, Knuth needed a non-trivial benchmark and turned to Mondrian-style rectangle dissections. He transformed these layouts into discrete combinatorial structures called reduced representations, where every coordinate line contains at least one divider. For an m by n grid, the number of constituent rectangles is at most m * n and at least m + n - 1. Knuth defined configurations achieving the minimum bound of m + n - 1 as 'tight pavings.' For a 3 by 5 grid, Knuth found 20,165 reduced decompositions, of which exactly 1,071 are tight pavings. Noting that no entries existed in the Online Encyclopedia of Integer Sequences (OEIS) for these counts, he cataloged the initial values for 3 by n grids (1, 11, 64, 282, 1,071) and submitted a formal challenge to The American Mathematical Monthly to evaluate the sequence and its asymptotic behavior. Generating Functions and the Factorial Conjecture (29:09) In tight pavings, exactly one dividing line occupies each row and column, and lines never cross at a single point. Knuth grouped these configurations into canonical skeletal types by stripping out vertical line segments that do not meet horizontal endpoints. By treating the open vertical slices between endpoints as insertion slots with k placement options, each slice yields a generating function factor F_k(z) = z / (1 - kz). Multiplying these rational factors across all canonical types enables an exact count of pavings of arbitrary width n. Evaluating the resulting series revealed an unexpected cancellation. The leading coefficient for the growth term m^n reduced to clean constants: 27/4 for m = 3, 256/9 for m = 4, 78,125/256 for m = 5, and 17,496/25 for m = 6. From these values, Knuth deduced a general formula for the leading coefficient across any row count m: m^(2m - 3) / ((m - 1)!)^2. A six-hour calculation involving over 4 million types confirmed the m = 6 case, and Monthly referee Walter Stromquist subsequently developed a complete, rigorous proof. Limits of High-Precision Empirical Agreement (51:08) Knuth cautioned that extensive numerical agreement does not guarantee a conjecture is correct. During factoring research in the 1970s, an empirical constant matching e^(-gamma) diverged at the 16th decimal place because the integrand had a discontinuous fourth derivative that compromised standard numerical integration formulas. Similarly, competing analyses of the binary Euclidean algorithm matched through 11 decimal places before diverging due to genuine periodic fluctuations. Knuth contrasted this warning with Bill Gosper's unproven identity equating the golden ratio to a combination of gamma functions, which matches to 1,000 decimal places and is likely provable using established analytic machinery. The Infinite Greedy Queens Problem (55:44) Knuth examined an open problem introduced by Neil Sloane: placing queens sequentially in the first quadrant at the leftmost legal position. Numerical data computed through hundreds of billions of values shows that queen coordinates bifurcate into two rays with slopes asymptotically equal to the golden ratio phi (~1.618) and 1/phi (~0.618), with initial stray points vanishing after n roughly equals 4,000. Knuth designed an efficient literate program running in cache-friendly O(n) time and linear space, outperforming the O(n^3) brute-force cost. While Sloane's initial attempt to prove that every integer appears collapsed upon writing, Knuth suggested that a finite proof might never be found, comparing the situation to Goldbach's conjecture where overwhelming empirical evidence substitutes for formal certainty. Knuth emphasized that pure mathematical research is driven by aesthetic satisfaction rather than economic payoff. While the tight paving conjecture was resolved through Stromquist's proof, problems like the greedy Queens ray distribution remain open, demonstrating that computational patterns often generate questions beyond the immediate reach of formal proof.

Donald Knuth在第23届圣诞树讲座中阐述了离散数学研究的核心体验：通过算法实验与数值观察提炼出“不得不真”的数学猜想，并展示了这些直觉从提出到由同行给出严格证明或遭遇意外失效的全过程。 矩形分割问题与紧铺砌分类 (3:46) Knuth在为《计算机程序设计艺术》（TAOCP）编写跳舞链（Dancing Links）扩展算法时，为了寻找具有挑战性的测试问题，研究了类似蒙德里安（Piet Mondrian）风格的矩形网格分割问题。在约简表示（reduced representation）下，每个内部水平线和垂直线坐标都必须包含至少一条分割线段。Knuth指出，一个 $m \times n$ 网格分解出的矩形数量存在严格下界 $m + n - 1$，他将达到该下界的布局定义为“紧铺砌”（tight paving）。例如在 $3 \times 5$ 的20,165个有效约简分割中，紧铺砌恰好只有1,071个。通过进一步观察，紧铺砌内部的线段互不交叉，每行每列恰有一条线段，这使得人们可以通过剥离中间垂直线段将其归约提炼为有限种骨架拓扑类型（canonical types）。 母函数计算与主项系数猜想 (35:45) 为了在理论上精确计数紧铺砌，Knuth利用母函数（generating functions）对各类拓扑骨架在垂直切片中插入额外分割线的方式进行建模。每个切片如果有 $k$ 种切割选择，便对应因子 $F_k(z) = z / (1 - kz)$。对于 $m=3$ 的网格，Knuth枚举了全部52种骨架类型，通过计算机代数系统求出渐近主项系数为 $27/4 = 3^3 / 2^2$。当他进一步计算 $m=4$（共1,464种类型）时，原本由576个有理分式构成的庞大分母发生奇迹般的约分，得出前导系数 $256/9 = 4^5 / 6^2$；随后的 $m=5$ 与 $m=6$（耗时约6小时遍历400多万种类型）计算均完美契合这一结构。基于这一系列计算结果，Knuth提出了 $m^n$ 主项系数的通用公式猜想 $m^{2m - 3} / ((m - 1)!)^2$。该问题随后被提交至《美国数学月刊》（The American Mathematical Monthly），审稿人Walter Stromquist最终给出了完全严格的数学证明。 高精度数值契合的假象与陷阱 (51:08) 尽管紧铺砌猜想得到了圆满证实，Knuth提醒听众，即便数值高度吻合也绝不能替代严格证明。他回顾了20世纪70年代分析整数分解算法时的经历：在计算大数第二和第三大素因子的平均规模时，数值与常数 $e^{-\gamma}$（$\gamma$ 为欧拉常数）在前15位小数完全一致，但在第16位发生分歧。经整整一周排查，他发现程序本身无误，而是所用的数值积分公式要求被积函数具有连续的四阶导数，而该问题中的函数四阶导数并不连续。另一案例来自对二进制欧几里得算法的分析，Richard Brent与Brigitte Vallée的计算在前11位完全相同后出现差异，最终证实这是复变函数内部微小的对数周期性震荡引起的真实物理差异，而非计算错误。 贪心无穷皇后问题的未解之谜 (55:44) 在讲座末尾，Knuth探讨了最新浮现但难以证明的猜想，包括Bill Gosper给出并吻合至1,000位小数的黄金比例 $\phi$ 的伽马函数等式，以及第一象限内的贪心无穷皇后问题。在该棋盘序列中，皇后按照字典序贪心放置在互不攻击的最靠左位置。OEIS创始人Neil Sloane发现，放置点的坐标分裂成由原点发出的两条笔直射线，其斜率渐近于黄金分割率 $\phi$ 和 $1/\phi$。Knuth为此编写了高效的文学化程序（literate program），将传统 $O(n^3)$ 的暴力搜索压缩至线性时间 $O(n)$，并在数百亿规模的数值测试中验证了点群的紧密聚集（偏离极值消失于 $n \approx 4,000$ 之后）。然而，针对该现象目前尚不存在有限证明，甚至连“是否每个整数坐标都会被填入”这一基本命题都仍未获证。 Knuth总结道，数学与理论计算机科学研究的真正魅力在于完全脱离经济回报、纯粹出于对美和规律的追求。面对诸如无穷皇后等可能如哥德巴赫猜想般因压倒性概率而“不得不真”却难以证明的难题，发现新规律并尝试破解是推动科学不断前进的永恒动力。

## Background 该视频由 Stanford Online 于 2017 年 12 月 8 日在 YouTube 平台发布。内容为计算机科学泰斗唐纳德·克努特（Donald Knuth，高德纳）教授带来的第 23 届年度圣诞树讲座（23rd Annual Christmas Tree Lecture），题为“一个必然成立的猜想”（A Conjecture That Had To Be True），讲述了他在组合几何计算中发现的一个优美公式及其背后的研究趣事。 ## TL;DR 高德纳从蒙德里安几何画作启发的矩形网格剖分问题（紧凑铺砖，tight paving）切入，分享了他为测试算法而计算剖分方案时，如何借助生成函数意外发现主导项系数遵循惊人简洁的闭式公式。虽然该模式起初仅在小规模网格上得到验证，但他凭直觉坚信它在真实世界中“不可能不成立”，随后这一猜想在《美国数学月刊》征解后由数学家 Walter Stromquist 成功严格证明。接着，高德纳列举了历史上关于数值巧合真伪的案例，并引出了一个延伸至无穷平面的贪心皇后未解问题，向观众展现了纯粹为了美与热爱而进行数学探索的无穷乐趣。 ## Atmosphere & style 整场讲座洋溢着浓郁的学术好奇心与温馨风趣的圣诞节日氛围，即将迎来八十寿辰的高德纳坐着讲课，如同慈祥的长者围炉夜话般娓娓道来。他的叙述充满自嘲与幽默，在黑板上手绘图表、与观众轻松纠错互动，将抽象的离散组合与生成函数讲解得生动且平易近人。从发现巧合时的通宵达旦，到对“上帝绝不会让公式更复杂”的纯粹感叹，观众能真切感受到一位老学者对数学规律由衷的敬畏与热忱。 ## Bulletin - [45:39](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2739s) 高德纳在分析矩形紧凑铺砌（Tight Paving）时发现，网格尺寸为 $m$ 时主导项系数均严格等于 $m^{2m - 3} / ((m - 1)!)^2$，该猜想随后由 Walter Stromquist 成功给出严密证明。 - [51:08](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3068s) 高德纳警示高精度数值吻合并不代表数学猜想必然成立，例如在因式分解算法数值积分中因四阶导数不连续导致第 16 位小数偏离，以及二进制 GCD 分析中隐藏的微小周期性微扰。 - [55:44](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3344s) 在第一象限开展的“无限贪心皇后问题”呈现出惊人的宏观规律：皇后点位渐近落在斜率分别为黄金比例 $\phi$ 和 $1/\phi$ 的两条射线上，高德纳为此设计出仅需极小常数因子的 $O(n)$ 高效求解算法。 - [01:01:15](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3675s) 高德纳在 80 岁寿辰前夕发表第 23 届年度圣诞树讲座，强调纯粹数学研究往往毫无商业回报，但提出直觉猜想并最终证伪或证明的过程展现了纯粹求知的爱与美。 ## Key takeaways - [01:49](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=109s) 高德纳举办第 23 届年度圣诞树讲座，通过分享亲身经历展现数学与理论计算机科学中提出猜想、验证模式并寻求证明的研究乐趣。 - [05:42](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=342s) 矩形剖分问题通过编号横纵分割线转化为离散的“约化表示”，舍弃几何尺寸而仅保留拓扑邻接关系。 - [09:00](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=540s) 在 $m \times n$ 网格中，最少小矩形数量的紧凑下界为 $m + n - 1$，高德纳将其正式命名为“紧凑铺砖”（Tight Paving）。 - [13:59](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=839s) 高德纳利用舞动链（Dancing Links）算法高效穷举解空间，算出 $3 \times 5$ 网格的 20,165 种约化方案中恰有 1071 种紧凑铺砌。 - [24:31](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=1471s) 紧凑铺砌具有关键结构约束：每条内部网格线上恰有一条线段，且横纵线段严禁十字交叉（类似榻榻米禁忌）。 - [29:09](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=1749s) 通过压缩未连接水平线端点的垂直线，所有铺砌均可规约到有限的基本“类型”（Type），进而通过插入垂直线进行组合扩展。 - [36:06](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2166s) 借助幂级数生成函数 $F_k(z) = z / (1 - kz)$ 的乘积卷积，可精确求得各类型铺砌对应的系数并代数累加求和。 - [45:39](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2739s) 当 $m = 3, 4, 5, 6$ 时，主导项系数经庞杂有理式抵消后均收敛为超简洁分式，归纳出闭式公式 $m^{2m - 3} / ((m - 1)!)^2$。 - [48:11](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2891s) 高德纳在缺乏严密证明时坚信该规律必然成立，问题刊登后由审稿人 Walter Stromquist 完成了最终的严格数学证明。 - [51:08](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3068s) 高德纳提醒即使高精度吻合也可能存在伪巧合，例如整数分解第二大因子均值在第 16 位偏离 $e^{-\gamma}$，以及二进制 GCD 算法中的均值为零周期性微扰。 - [55:44](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3344s) 展示了 Bill Gosper 涉及 Gamma 函数且在前 1000 位小数完全吻合黄金比例 $\phi$ 的待证明代数猜想。 - [55:44](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3344s) 由 Neil Sloane 引入的“无限贪心皇后问题”在宏观上极其精准地沿斜率 $\phi$ 与 $1/\phi$ 的两条射线分布，且离群点在大约 $n = 4000$ 后彻底绝迹。 - [01:03:57](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3837s) 高德纳将无限贪心皇后问题的暴力 $O(n^3)$ 搜索大幅优化为缓存友好的 $O(n)$ 线性时间算法，实现对数千亿项的高效数值验证。 - [01:01:15](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3675s) 纯数学研究虽缺乏直接商业经济回报，但探索未解之谜与欣赏形式之美正是数学家持续探索的核心动力。 ## Detailed walkthrough ### [00:04](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=4s) 介绍与致辞：高德纳的传奇人生与八十寿辰 主持人斯蒂芬妮（Stephanie）热情地欢迎了现场观众，并隆重介绍了唐纳德·克努特（Donald Knuth，中文名高德纳）教授。这是高德纳第23届年度圣诞树讲座（Annual Christmas Tree Lecture），今年的主题是“一个必然成立的猜想”（A Conjecture That Had To Be True）。斯蒂芬妮坦言，很难用简短的语言来概括高德纳的伟大成就，但她依然做出了极佳的总结：他是斯坦福大学的荣誉教授、计算机科学家、数学家，更是享誉全球的巨著《计算机程序设计艺术》（The Art of Computer Programming, TAOCP）的作者。 斯蒂芬妮提到，这部著作涵盖了程序设计、算法及其分析的诸多领域，至今仍被视为该领域最全面、最权威的开山之作。她引用了媒体的极高评价： > “这本书仍被认为是该领域首部也是最全面的论著，被《纽约时报》称为‘该行业的定义性论文’。” 高德纳还因一个有趣的习惯而闻名：任何人在他的著作中发现错误，他都会寄出一张价值2.56美元（即十六进制中的1美元）的支票。斯蒂芬妮开玩笑地鼓励大家“去赢取这张支票吧”。此外，高德纳一生获奖无数，包括首届 ACM 葛丽丝·霍普奇才奖（Grace Murray Hopper Award）、图灵奖（Turing Award）、美国国家科学奖章（National Medal of Science）、冯·诺伊曼奖章（John von Neumann Medal）以及京都奖（Kyoto Prize）等。 除了在学术界的泰斗地位，高德纳还是一位造诣极高的音乐家。他的个人网站上写着，只要给他发个便条，他随时乐意参与即兴演奏（jam session）。高德纳即将迎来80岁寿辰，斯蒂芬妮提议大家提前祝他生日快乐。他的八十寿辰庆祝活动将在瑞典北部举行，届时不仅会举办学术研讨会，还将迎来他历时50年创作的管风琴多媒体巨作《天启幻想曲》（Fantasia Apocalyptica）的世界首演。在全场热烈的掌声中，这位多才多艺的传奇学者登上了讲台。 --- ### [01:49](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=109s) 讲座开场：为什么做研究如此有趣？ 高德纳微笑着向台下的新老朋友致意。因为即将年满80岁，他选择坐下来进行这场讲座。他首先阐述了本次讲座的副标题以及他选择这个主题的初衷——向大家展示为什么做学术研究是一件充满乐趣的事情。 在高德纳看来，科学研究的魅力在于发现规律、提出猜想并最终予以证明的过程。他动情地说道： > “这就是我今天要讲的故事，这种故事在你研究问题时会一次又一次地重复发生，特别是在数学和理论计算机科学领域，你不仅能做出猜测，而且通常还能证明它们。” 他解释说，在研究过程中，你往往会观察到一些极不寻常的现象，随后在不断的尝试中，这些模式一次又一次地得到印证。此时，你心里会无比确信“这个规律绝对不可能是错的”，但同时又会苦恼于“我们到底该怎么去证明它”。高德纳表示，他今天就要分享一个在今年（2017年）4月份发生在他自己身上的、特别有趣的此类经历。 --- ### [03:23](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=203s) 蒙德里安的画作与矩形剖分问题 高德纳在屏幕上展示了一幅荷兰画家皮特·蒙德里安（Piet Mondrian）的著名代表作。蒙德里安以其独特的几何抽象画风闻名于世，他的画作中没有复杂的曲线，只有大大小小的矩形嵌套在更大的矩形之中。高德纳指出，将一个大矩形分割成若干小矩形（即矩形剖分问题）是一个历史悠久的经典问题，早在蒙德里安之前，人们在铺设路面、砌砖等日常建造活动中，就已经在研究如何将不同的矩形组合在一起。 ```mermaid flowchart TD accTitle: 矩形剖分到紧凑铺砖的转化流程 accDescr: 展示如何将几何上的矩形剖分转化为离散的约化表示，并最终定义紧凑铺砖。 A["几何矩形剖分 (如蒙德里安画作)"] --> B["标定水平与垂直坐标 (从0开始编号)"] B --> C["转换为约化表示 (Reduced Representation)"] C --> D{"计算矩形数量 (R)"} D -->|最小数量 R = m + n - 1| E["紧凑铺砖 (Tight Paving)"] D -->|最大数量 R = m * n| F["完全剖分"] ``` 高德纳分享了他关注到这个问题的契机。今年1月，他在撰写《计算机程序设计艺术》中关于“舞动链”（Dancing Links）这一极酷的数据结构章节时，将舞动链算法扩展到了一个更广泛的问题类别。为了测试这个新算法，他需要寻找一个有趣且具有挑战性的测试案例，于是他开始摆弄“矩形剖分为矩形”的问题。 许多人认为，数学家们已经研究了数百年，世界上有成千上万的数学家在日复一日地工作，怎么可能还能找到一个既简单直观、又没有被过度研究的处女地呢？高德纳对此给出了否定的回答： > “答案是，这些问题一点也不罕见；它们每年都会出现好几次。” 他强调，即使是像“矩形剖分”这样最基础的问题，依然有许多未被前人触及的角落。 --- ### [05:42](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=342s) 整数化与“约化表示”的引入 作为一个“以整数为导向的人”（integer-oriented person），高德纳更喜欢将几何上的连续图形转化为他更容易理解的离散数学结构。为此，他引入了“约化表示”（reduced representation）的概念。 他以一幅矩形剖分图为例，说明了这一转化过程： * 找出图中所有垂直分割线，将它们的横坐标从左到右依次编号为 $0, 1, 2, 3, 4, 5$。 * 找出所有水平分割线，将它们的纵坐标从下到上依次编号为 $0, 1, 2, 3$。 通过这种方式，任何一个矩形剖分都可以被重新绘制在一个标准的 $m \times n$（本例中为 $3 \times 5$）的网格上。在黑板上绘制这个 $3 \times 5$ 网格的约化表示时，高德纳不小心画错了一个线条，在台下观众的善意提醒下，他及时进行了修正，并幽默地开玩笑说：“多亏你们纠正，这帮我省了20分钟的时间。” 高德纳指出，这种约化表示丢弃了具体的几何尺寸（如长度和宽度），只保留了矩形之间的拓扑邻接关系。 --- ### [09:00](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=540s) 紧凑铺砖（Tight Paving）的定义与谷歌搜索趣事 将问题约化后，高德纳向观众提出了一个问题：在 $3 \times 5$ 的网格中，总共存在多少种不同的约化矩形剖分？（这也是他书中的练习题 340）。 台下有观众猜测是“100万种”。高德纳公布了正确答案：**20,165** 种。 在这些剖分方案中，包含的小矩形数量各不相同： * **最大数量**：显然是 $3 \times 5 = 15$ 个（即每个网格单元都是一个独立的小矩形）。 * **最小数量**：高德纳指出这是一个非常微妙且容易出错的问题。经过严谨的推导，在满足“约化”条件的前提下（即不能有任何中间坐标线被完全忽略），剖分所需的最少矩形数量公式为 $m + n - 1$。对于 $3 \times 5$ 的网格，这个最小数量就是 $3 + 5 - 1 = 7$ 个。 高德纳将这种达到了最少矩形边界的剖分命名为**“紧凑铺砖”**（Tight Paving）。因为这是一个紧凑的下界，且听起来非常形象。 随后，高德纳分享了一个令人捧腹的学术趣事。为了确认“Tight Paving”这个词是否在数学界被使用过，他特意去谷歌上搜索了这个词。结果令他大出所料，屏幕上显示的全部是各种重型铺路机和道路施工的图片。高德纳笑着说道： > “我知道没有其他人将‘紧凑铺砖’用于数学讨论，但许多真正从事铺路行业的人……拥有非常棒的机器，可以把路铺得很紧凑。” 这证明了他在数学和计算机科学领域独创了这个术语。 --- ### [12:23](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=743s) 核心问题：如何计算紧凑铺砖的数量？ 明确了定义后，高德纳引出了他真正想要探究的核心问题：对于任意给定的 $m \times n$ 网格，究竟存在多少种不同的“紧凑铺砖”？ 高德纳之所以对这个问题着迷，是因为他那设计精妙的“舞动链”数据结构能够以极快的速度自动生成并输出所有可能的紧凑铺砖方案。为了验证自己的程序是否正确，他必须通过理论计算来核对程序输出的数量。 他再次向台下的观众发起互动：在 $3 \times 5$ 网格所拥有的 20,165 种约化剖分方案中，有多少种是属于只有 7 个矩形的“紧凑铺砖”呢？高德纳邀请大家展开想象，并准备在接下来的讲座中揭晓这个隐藏在数字背后的惊人规律。 ### [13:59](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=839s) 紧凑铺砌的计数与 $3 \times 5$ 的 $1071$ 种解法 高德纳（Donald Knuth）提到，他用计算机程序仅仅进行了约 1800 万次内存访问，就完成了对相关案例的穷举运算。在这两万个测试用例中，各案例表现出了鲜明的分布特征：其中 1 例包含 15 个矩形，22 例包含 14 个矩形，199 例包含 13 个矩形等；而在这些情况中最紧凑的极限情形仅包含 7 个矩形。在高德纳抛出“在这两万种情况中究竟有多少种包含 7 个矩形”的疑问后，他公布了答案：恰好有 1071 种方法。 这引出了核心概念——紧凑铺砌（tight paving）。以 $3 \times 5$ 的网格为例，紧凑铺砌指的是将其划分为恰好 $3 + 5 - 1 = 7$ 个矩形，并且网格内部的每一条水平网格线和垂直网格线都必须至少被使用一次。高德纳指出，虽然不可能把全部 1071 种可能逐一画出来，但他将向大家展示如何对其进行系统性计数，以及该问题如何导出一个“必然为真”的数学猜想。 --- ### [15:21](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=921s) 从小规模网格入手：$2 \times 2$ 与 $3 \times 2$ 的手算枚举 为了把紧凑铺砌的概念讲解得清晰透彻，高德纳先带大家推演极小规模的例子：对于 $m \times n$ 的网格，紧凑铺砌要求使用的矩形数量为 $m + n - 1$。 - **$2 \times 2$ 网格**：需要分成 $2 + 2 - 1 = 3$ 个矩形。画出一个基本构型后，通过四向旋转可以得到且仅能得到 4 种解法。 - **$3 \times 2$ 网格**：需要分成 $3 + 2 - 1 = 4$ 个矩形，且必须使用至少 2 条水平线和 1 条垂直线。 高德纳拿出一叠精致的信纸开始现场作画。他笑着分享了一段趣事：去年波兰举行了一场会议，有人送给他这叠非常棒的纸，他极为喜欢，甚至决定在下个月自己的生日派对上也给宾客分发这种便笺纸；不过派对上的便笺将印上三角形网格，因为他始终觉得“很多数学至今没被发明出来，纯粹是因为人们没有拿到三角形网格纸”。 接着，高德纳在纸上一步步寻找 $3 \times 2$ 的 4 矩形划分方案。他先画出一个基础解并翻转得到镜像解；随后构造出带拐弯形态的构型及其镜像；再利用已知 $2 \times 2$ 的 4 种解法拼入构型下方，逐一翻转对称图形，最终在纸上一共排查出 11 种合法方案。高德纳笑着感叹，平时手算往往会遗漏，最后总得靠程序找出落下的，但这一次手算的 11 种答案与计算机程序的结果完全吻合。 ```mermaid flowchart TD accTitle: 紧凑铺砌基础小规模枚举 accDescr: 展示2x2网格和3x2网格如何按矩形数量与几何对称性进行枚举 subgraph Case2x2["2 x 2 网格 (m+n-1 = 3 个矩形)"] A1["基础划分方案"] --> A2["四方向旋转对称"] A2 --> A3["总计: 4 种解"] end subgraph Case3x2["3 x 2 网格 (m+n-1 = 4 个矩形)"] B1["横纵线约束: 2条横线 + 1条竖线"] B2["基础构型及镜像"] B3["利用 2x2 构型拼装组合"] B1 --> B2 B1 --> B3 B2 --> B4["穷举并排除重合镜像"] B3 --> B4 B4 --> B5["总计: 11 种解"] end ``` --- ### [18:49](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=1129s) 数列规律与 OEIS：数学家的“切片面包” 高德纳进一步展示了固定行数为 3、列数为 $n$ 时，对应紧凑铺砌数的变化序列 $a(3, n)$： - $n = 0$: 定义为 0 - $n = 1$: 1 种 - $n = 2$: 11 种 - $n = 3$: 64 种 - $n = 4$: 282 种 - $n = 5$: 1071 种 面对这组数字，高德纳提到了过去三十多年来对数学界极为关键的在线整数数列百科全书（OEIS）。他由衷赞叹道： > “This is just the nicest thing since sliced bread for mathematics because you can compute your way into the literature.” —— Donald Knuth 只要算出一个问题前几个小规模情况的数值并去 OEIS 搜索，就能立刻查明前人是否研究过。高德纳还在演讲中呼吁大家向 OEIS、维基百科（Wikipedia）以及互联网档案馆（Internet Archive）进行年度捐款，以维持其运转。 2017 年 4 月，高德纳在复活节（4 月 16 日）当天完成了这批枚举运算，并在 4 月 17 日将这组数据提交至 OEIS。当时该数列尚未被任何人收录，证明这是一个全新的研究方向。他同时提交了 $m \times n$ 三角形阵列的数据，并在注释中写道：该数列是否存在生成函数？答案是肯定的，存在非常简洁的闭式解，但他将在投递给《美国数学月刊》（American Mathematical Monthly）的征解问题尘埃落定后再行公布。高德纳称赞 OEIS 的审核极度高效而严谨，提交后一天内就有 7 位学者发表评论、润色表述并交叉验证数据。 不久前，该问题正式刊登在《美国数学月刊》上，题目要求：设 $a(m, n)$ 为紧凑 $m \times n$ 铺砌的数量，求出 $a(3, n)$ 关于 $n$ 的表达式；并证明当 $m \ge 3$ 时，极限 $\lim_{n \to \infty} \frac{a(m, n)}{m^n}$ 存在，同时计算出该极限值。高德纳坦白说，虽然期刊刊登出来的文字让人觉得他已经完全解决了所有情况，但实际上当时他仅严格证明了 $m = 3, 4, 5, 6$ 的情形，然而其中呈现出的优美模式让他深信对于 $m \ge 7$ 它必然同样成立。 --- ### [24:31](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=1471s) 拓扑简化：榻榻米禁忌与“类型”（Type）的提出 为了向更普遍的解法迈进，高德纳跳过了繁复的试错过程，直接揭示了一个至关重要的结构性简化定理： - 在任意紧凑铺砌中，**每一条内部横向网格线上恰好存在一条水平线段**，**每一条内部纵向网格线上也恰好存在一条垂直线段**。绝不会出现同一条网格线上断续出现两条线段的情况。 - 所有的横线与竖线**绝不交叉**。它们可以彼此“接触”（T 型相接），但不能形成类似四块日本榻榻米席角汇聚于一点的“十”字交叉。紧凑铺砌中严禁十字交叉。 以一个 $5 \times 15$ 的紧凑铺砌为例，它包含 $5 + 15 - 1 = 19$ 个矩形。除去最顶端和最底端的边界外，中间共有 $5 - 1 = 4$ 条水平线段。若忽略铺砌中其他细节，仅提取各水平线段的起止端点在横向坐标上的位置（例如标定为 $0, 1, 2, 3, 4, 5, 6$ 等），就能定义出该解的**“类型”（Type）**。 因为垂直线段绝不能与水平线段发生交叉，一旦所有水平线段的端点位置确定，各个端点处的垂直线段走向就会被完全强制锁定。于是，一个抽象的“类型”对应着该构型最窄（最小横向尺寸）的基础几何骨架；所有具有相同横向投影结构的更大铺砌，在本质上都属于同一种类型。高德纳指出，只要将关注点集中在水平线段的相对位置及端点上，就能把无限的铺砌分类并归纳到有限的几何骨架中进行精确计数。 ### [29:09](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=1749s) 铺砌类型的定义与压缩原则 高德纳（Donald Knuth）深入解释了如何定义紧密铺砌（tight paving）的“类型”（type）。在对网格铺砌进行分类时，关键规则是忽略所有不对应水平线段端点的垂直线段。如果在某处画了一条垂直线，但该位置并没有任何水平线段在此开始或结束，这条垂直线就会被完全忽略并“压缩”掉。通过这种方式，任何复杂的铺砌都可以被规约（reduce）到一个最简骨架，即它的“类型”。 高德纳展示了一个包含 11 个小示例的白板或幻灯片，用以说明 $3 \times 2$ 等尺寸下所有可能出现的形态。他解释道，某些图案从始至终都没有水平线在内部断开或起始，这类图案在忽略多余垂直线后，其基本类型实际上就是最基础的一列骨架。高德纳强调，这种规约的核心意义在于：“关键的观察在于，对于每一种类型，我们都可以弄清楚并计算出属于该类型的对象究竟有多少个。” ```mermaid flowchart LR accTitle: 铺砌规约与类型映射流程 accDescr: 展示原始紧密铺砌通过剔除冗余垂直线，规约到基本类型的过程。 A["完整紧密铺砌图案"] --> B{"检查垂直线"} B -->|"未连接水平线端点"| C["忽略 / 压缩该垂直线"] B -->|"连接水平线端点"| D["保留为骨架线"] C --> E["核心骨架：铺砌类型 (Type)"] D --> E ``` ### [32:05](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=1925s) 区域插入垂直线与组合计数 为了阐明如何从单个骨架派生出大量的更大铺砌，高德纳在黑板上画了一个纵坐标为 $0$ 到 $5$（即高度为 5）、横坐标标为 $0$ 到 $6$ 的大型示例。在骨架确立后，水平线段之间留出了若干垂直区域。在每个空隙区域内，人们可以自由插入任意数量的额外垂直线，只要不跨越现有的水平线即可： - 在第一个区域，由于没有内部水平阻隔，插入的垂直线只有 $1$ 种摆放方式；若插入 $a$ 条线，就有 $1^a$ 种可能； - 在第二个区域，有一条水平线阻隔，垂直线可以放在上方或下方，提供 $2$ 种选择；插入 $b$ 条线便有 $2^b$ 种可能； - 后续各区域根据未被阻隔的纵向间隙数量，分别拥有 $4$ 种、$3$ 种、$2$ 种或 $3$ 种放置垂直线的选择，分别对应 $4^c$、$3^d$、$2^e$、$3^f$ 种可能。 对于任意选取的非负整数 $a, b, c, d, e, f$，只要总和满足 $a+b+c+d+e+f = n - 6$（对应宽度为 $n$ 的网格），插入这些线后生成的图案都必然是一个紧密铺砌，且都唯一归约回这个初始骨架。高德纳指出：“要点在于，每一种紧密铺砌都有一个确定的类型，而类型的总数是很少的；一旦知道了类型，我就能针对所有的 $n$，精确算出有多少个铺砌属于该类型。” ### [36:06](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2166s) 生成函数法的引入 高德纳通过高度为 3 的情况进一步细化了计数机制。例如对于宽度为 1 的单个骨架，若要扩展到更大宽度，在各列之间插入垂直线时，每一步都有 3 种选择；因此宽度为 3 时有 $3 \times 3 = 9$ 种，宽度为 4 时有 $27$ 种。若骨架由具有不同选择数的多个区间组成（例如一个区间有 3 种选择，另一个区间有 2 种选择），总数就变成形如 $3^a 2^b$ 的柯西乘积求和。 面对这种指数与卷积结构，高德纳赞叹道：“当你计算这种形式的和式时，它是如此美妙，因为生成函数（generating function）方法正是解决这一问题的绝配。” - 令几何级数对应的幂级数定义为 $F_k(z) = \frac{z}{1 - kz} = z + kz^2 + k^2 z^3 + \dots$。 - 若某个类型在各个区间分别拥有 $k_1, k_2, \dots, k_m$ 种选择，则对应于该类型、宽度为 $n$ 的铺砌总数，恰好等于生成函数乘积 $\prod F_{k_i}(z)$ 中 $z^n$ 的系数。 - 对于前面的高度为 5 的复杂例子，其对应的生成函数即为 $F_1(z) F_2(z) F_4(z) F_3(z) F_2(z) F_3(z)$。 高德纳指出，高度为 3 的情况一共只有 52 种类型（其中宽度为 2 的类型有 2 个对应 $F_2^2$、2 个对应 $F_1 F_3$、4 个对应 $F_2 F_3$ 等）。借助计算机代数系统，可以轻松地将这 52 种类型的生成函数全部展开并累加，从而彻底求出精确解。 - 幂级数展开公式：$F_k(z) = \frac{z}{1 - kz} = z + k z^2 + k^2 z^3 + \dots$ - 组合权重乘积：$a_n = [z^n] \prod_{i} F_{k_i}(z)$ - 3 行网格（高度为 3）的全部基本骨架类型总数为 52 个。 ### [43:07](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2587s) 月刊征解协议与 $3 \times n$ 主导项 高德纳话锋一转，提到该问题其实发表在当年 10 月份的《美国数学月刊》（The American Mathematical Monthly）上，并且征解截止日期是 2018 年 2 月 28 日。他幽默地向台下观众表示，自己可不能全盘托出以免剧透：“这里有剧透警告，我不能告诉你们太多细节。”但他还是乐意公布渐近公式的主导项，以便大家能够核对自己的推导结果。 对于高度为 3 的情况（记为 $a_{3,n}$），高德纳写出了形式为 $\frac{1}{4} \cdot 3^{n+3} - 5 \cdot 2^{n+4} + \dots$ 的展开式。他将主导项整理出来，指出当 $n$ 很大时，铺砌总数的增长率主要由底数为 3 的指数主导： $$a_{3,n} = \frac{27}{4} \cdot 3^n + O(2^n)$$ （高德纳在现场黑板书写与口误修正中明确指出，$a_{3,n}$ 的主导系数为 $\frac{27}{4}$）。 ### [45:39](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2739s) 4 行与 5 行的惊人常数巧合 得到 3 行的结果后，高德纳按捺不住好奇心，将算法推向了 4 行网格。对于高度为 4 的情形，铺砌类型的数量猛增至 1464 种。在这些类型中，包含 $F_4$ 因子（即对增长率 $4^n$ 做出贡献）的类型恰好有 576 种。高德纳将这 576 种类型各自对应的复杂有理分式代数累加，奇迹发生了：所有庞杂的中间项全部抵消，最终得到的主导项系数竟然是一个极其简洁的数字——$\frac{256}{9}$。 高德纳兴奋地描述道：“这是 576 个各自都相当恶心丑陋的分数相加，但它们在最后全被抵消合并成了 256/9。”这一惊人结果让他当晚彻底失眠：“那天晚上我没去睡觉，我直接去算了 $a_{5,n}$。” 对于高度为 5 的情形，主导项增长率为 $5^n$，其前面的常数系数算出来是 $\frac{78125}{256}$；而 $78125 = 5^7$，$256 = 4^4 = (4!)^2$。高德纳继续计算了高度为 6 的情形，常数系数为 $\frac{17496}{25}$。对比这几组数据： - $m = 3$：$\frac{27}{4} = \frac{3^3}{2^2} = \frac{3^{2\times 3 - 3}}{((3-1)!)^2}$ - $m = 4$：$\frac{256}{9} = \frac{4^5}{6^2} = \frac{4^{2\times 4 - 3}}{((4-1)!)^2}$ - $m = 5$：$\frac{78125}{256} = \frac{5^7}{24^2} = \frac{5^{2\times 5 - 3}}{((5-1)!)^2}$ 高德纳由此总结出普遍规律：对于任意高度 $m$，主导项系数在每一种检验过的情形下，均严格等于： $$\frac{m^{2m - 3}}{((m - 1)!)^2}$$ 正是这个无论如何“不可能不成立”的惊人闭式猜想，构成了整场演讲的核心悬念。 ### [48:11](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=2891s) 猜想的验证、评审与 Kirkman 的“神学理由” Donald Knuth 回顾了关于组合几何问题的数值检验过程。针对参数 $M = 3, 4, 5, 6$，公式完全成立。在 $M=6$ 的情形下，有效类型（valid types）超过 400 万种，计算机足足运行了约 6 个小时才完成计算。随后 Knuth 将数据喂给 Mathematica，展开所有系数后核对无误。面对如此严丝合缝的巧合，Knuth 意识到“背后一定有什么深刻的规律正在发生”，于是将该问题提交给《美国数学月刊》（The American Mathematical Monthly）寻求解释。 事情迎来了圆满的结局。该问题的审稿人是 Walter Stromquist。主编非常喜欢这个问题，甚至主动破例向 Knuth 透露了审稿人的姓名，促成两人直接通信。Stromquist 最终成功找到了该公式的严格证明，该成果即将于次年发表。此前 Knuth 曾将问题展示给著名组合学家 Richard Stanley 等人，大家都毫无头绪，仅隐约猜测可能与生成树（spanning trees）有关。 谈及为何当初认定这个猜想“必然为真”，Knuth 幽默地提到了 19 世纪的组合数学家 Thomas Kirkman（以“柯克曼女生问题”闻名）。Kirkman 是一位英国教会牧师兼业余数学家，早在 Jakob Steiner 之前就独立提出了后人所谓的 Steiner 三元系。在 Kirkman 的一篇论文中，他给出了一组推广公式并坚称其正确。Knuth 翻阅其论文发现，Kirkman 的论据其实非常单纯：“上帝绝不会让公式比我的更复杂。”虽然 Kirkman 缺乏严谨证明，但他坚信公式为真，纯粹是因为“它错得没有道理”。而这次，Stromquist 终于给出了令人信服的严格证明。 - 计算量细节：$M=6$ 时涉及超过 4,000,000 种有效类型，单次计算耗时约 6 小时。 - 求解进展：该数学猜想由 Walter Stromquist 成功证明，并被安排在次年正式发表。 - 历史趣闻：Thomas Kirkman 在并未给出严格证明的情况下断言其公式成立，理由本质上是上帝不会把自然法则设计得过于复杂。 --- ### [51:08](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3068s) 数值巧合的陷阱：因式分解常数与欧几里得算法 在科学研究中，看到罕见的模式便提出猜想，再用若干案例验证，这种经历极为普遍。然而 Knuth 告诫大家：即便高精度数值吻合，猜想也未必绝对成立。他分享了自己研究生涯中最难忘的两次“翻车与意外”。 第一件发生在 20 世纪 70 年代。Knuth 在分析整数分解算法时，通过数值积分计算出了一个随机 $n$ 位数第二大素因子的平均大小，精度达到小数点后 20 位。他偶然在某本书中看到前 5 位数字完全相同，书中称该常数为 $e^{-\gamma}$（其中 $\gamma$ 为欧拉常数）。Knuth 激动万分，心想答案必定就是 $e^{-\gamma}$。当时本地计算机缺乏强大的符号计算系统，他万分紧张地通过长途电话拨号登录麻省理工学院（MIT）的 Maxima 系统。结果令人大失所望：数值在小数点后第 16 位出现了偏差。 ```mermaid flowchart TD accTitle: Knuth 整数分解常数数值异常排查流程 accDescr: 展示 Knuth 计算随机数因子常数时从怀疑符号解到定位数值积分条件失效的全过程 A["计算因子大小常数 (20 位小数)"] --> B["前 5 位匹配 e^(-γ) 猜想"] B --> C["登录 MIT Maxima 校验高精度"] C --> D["发现第 16 位小数出现不一致"] D --> E["耗时一周审查数值积分代码 (无 Bug)"] E --> F["定位数学根源：数值积分公式要求 4 阶导数连续，被积函数 4 阶导数间断"] ``` Knuth 花了整整一周排查自己的数值积分程序，坚信代码有 Bug，却找不出任何错误。最终原因揭晓：代码毫无问题，但他所采用的数值积分公式严格要求被积函数的四阶导数必须连续，而该问题中的函数四阶导数恰好是不连续的，因而导致了第 16 位小数的细微发散。 第二件是关于二进制欧几里得算法（用于计算最大公约数 GCD）的理论分析。Richard Brent 与法国数学家 Brigitte Vallée 分别给出了各自的独立渐近分析，两者的常数在前 11 位小数上完全吻合，但在其后出现了微小分歧。深入研究后发现，这不是计算误差，而是相关复变函数内部存在幅度极小的震荡现象（带有 $\log\log n$ 形式的周期性微扰且均值为零）。Knuth 以此强调：即使两个数字吻合了很长一段，也绝不意味着猜想就必然成立。 > “在许多情况下，我的猜想都基于我所计算出的某些数值结果。最难忘的一次是我在分析因式分解算法时，能够确定随机 $n$ 位数第二大因子的平均大小，精度达到了 20 位小数。” —— Donald Knuth > > “仅仅因为两个值吻合了非常长的位数，并不意味着猜想就必然为真；我见过正反两方面的情况。” —— Donald Knuth --- ### [55:44](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3344s) Bill Gosper 的黄金比例猜想与无穷贪心皇后问题 Knuth 随后展示了上个月著名黑客兼数学家 Bill Gosper 发给他的一道关于黄金比例（Golden Ratio, $\phi$）的优美猜想。该式结构复杂： $$\frac{2^{2/5} \sqrt{5} \left[\Gamma(1/5)\right]^4}{\left[\Gamma(1/10)\right]^2 \left[\Gamma(3/10)\right]^2}$$ 将该表达式数值求值至 1000 位小数，计算机仅耗时三分之一秒，算出的结果为 `1.61803399...`，与黄金比例 $\phi$ 的前 1000 位完全吻合。Knuth 相信这个猜想“几乎必然为真”，或许很快就会有人给出证明。 讲座的最后，Knuth 引入了一个至今悬而未决的迷人难题。他感叹道：“一方面它必然为真，上帝绝不会容许它是别的样子；但另一方面我又隐隐觉得，或许永远没有人能给出证明，这个结论甚至可能不存在一个有限的证明。” 该问题源于经典的“$N$ 皇后问题”，Knuth 将其拓展至无限平面的第一象限，即“无限贪心皇后问题”（Infinite Greedy Queens Problem / 字典序最小解）。其规则是从原点出发，贪心地按照从左往右的顺序，将皇后放置在不与已有皇后冲突（即同行、同列、同对角线）的最左侧空位上： | 皇后编号 | 坐标位置描述与动作 | |:--- |:--- | | 第 1 皇 | 放置于最靠前的合法位置 | | 第 2 皇 | 不能相邻，跳至马步距离外合法位置 | | 第 3 皇 | 沿当前空隙放置 | | 第 4 皇 | 成功回填至第 2 列 | | 第 5 皇 | 填入第 4 列 | | 后续各皇 | 依次排在位置 9, 11, 13, 15，随后第 6 列被补齐…… | OEIS（整数数列在线大全）创办人 Neil Sloane 在大约一年半前将该数列录入数据库，并发现了一个极其惊人的宏观几何规律：这些皇后的点位几乎严格分布在两条射线上，一条位于 $x > y$ 区域，另一条位于 $x < y$ 区域。更为不可思议的是，其中一条直线的斜率正是黄金比例 $\phi$，而另一条直线的斜率恰好是其倒数 $1/\phi$。 这种几何吻合度异常完美。Knuth 自己为此专门编写了一个“文学编程”（literate programming）风格的高效求解程序，内含诸多巧妙的优化技巧，平均每个皇后仅需约 9 次测试操作即可确定位置。 > “一方面它必然为真，上帝绝不会希望它是别的样子；但我也有一种预感，或许永远不会有人能找到证明，甚至可能根本就不存在一个有限步的证明。” —— Donald Knuth ### [01:01:15](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3675s) 数值实验、黄金分割模式与数学研究的本质 高效率的算法让针对该序列的计算能够飞快推进到数千亿项（several hundred billion）。Donald Knuth 指出，每次计算 $n$ 时只需要很少的内存引用（memory references）。当计算规模达到 10 亿（1 billion）时，绝大多数数值都会极其紧密地落在围绕黄金分割比 $\phi \approx 1.61803$ 或 $1/\phi \approx 0.61803$ 的特定邻域内——具体而言，这些数值非常接近于 $\phi \times 10^9$ 或者 $10^9 / \phi$（Knuth 口误说了“5 times a million or a billion or a billion over 5”，实际对应于含 $\sqrt{5}$ 的黄金比例系数关系）。序列在极少数点上有离群值（outliers），但在达到约 4000 之后，离群现象似乎就彻底停止了，呈现出非常紧致的界限。这说明猜想大概率是完全正确的。 Knuth 随即谈到了这与哥德巴赫猜想（Goldbach's conjecture）的相似性：我们或许永远找不到一个形式化的证明，但凭借压倒性的概率证据，大家都深信它必定成立。借此机会，Knuth 概括了整场讲座的脉络：一切始于当年 4 月他偶然碰到的一个问题，里面包含着由幂和阶乘组成的离奇模式。通过数值验证，他直觉认定“它必须是真的”，并将其提交给了《美国数学月刊》（The American Mathematical Monthly）；随后另一位数学家看到后成功给出了严密证明。Knuth 进一步展示了若干个这类“本以为是真、后来也确实成真”的案例，最后引出了当前这个崭新的未解之题。 关于投身此类纯数学猜想的动机，Knuth 给出了极为纯粹的描述。这类问题没有任何商业应用前景，但恰恰展现了纯粹求知的魅力。Donald Knuth 总结道： > “How many mathematicians are gonna are gonna work on it? It's quite intriguing because you know, yeah, absolutely no economic payoff whatsoever; that's completely—you do it just purely for love and beauty.” 他补充说，数学研究的日常就是这样：当你终于解开一个难题并找到证明时，你会由衷地开心上几天；可随之而来的第二天，你又会发现下一个全新的问题，接着身不由己地投入下一轮求解。 - 算法对每个 $n$ 仅需常数次内存引用，使验证范围能轻易扩展至数千亿项。 - 达到 10 亿级别时，数值高度集中在黄金比相关常数（约 1.61803 或 0.61803）与 $10^9$ 的乘积周围。 - 序列中的离群点在大约 $n = 4000$ 之后基本绝迹，表现出极强的渐近规律性。 ### [01:03:57](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3837s) 现场问答：Gamma 函数恒等式与皇后问题的数学本质 在演讲结束后的问答环节中，观众询问了讲座前面提到的关于 Gamma 函数（$\Gamma$ 函数）猜想的后续进展。Knuth 解释道，数学界本身就存在大量涉及 Gamma 函数的经典恒等式，例如反射公式 $\Gamma(x)\Gamma(1-x)$、乘法公式（triplication/multiplication formulas）等。当前的猜想虽然似乎与三倍角/倍乘公式有关，但他认为对方使用的方式是全新的，并引入了其他数学分支的工具。提出该猜想的学者大约在 10 月初公开发布了相关内容，据 Knuth 所知目前还没有完全解决，不过 Knuth 对其被证出抱有很大信心，因为解析数论和特殊函数领域已经拥有极其庞大、成熟的数学理论工具箱（machinery）。 与此形成鲜明对比的是皇后问题（Queens problem）。在这个离散问题上，数学家甚至连“是否所有正整数都会在序列中出现”都无法证明，极有可能某些坐标会被永远排除在外。Knuth 透露，Neil（Sloane）曾经以为自己找到了证明，但就在动手撰写论文的严密论证阶段，整个逻辑全盘崩溃了。这个问题在本质上带有某种伪随机性，人们只能猜测“既然皇后摆在这些直线上，空位总有可能会被某只皇后占据”；但与此同时，系统内部又存在极其深刻的代数与几何结构。 正是依赖这种精巧的内在结构，Knuth 才能为其编写出极端高效的算法： - 朴素的暴力搜索（brute-force program）需要耗费大致 $O(n^3)$ 的时间复杂度。 - Knuth 设计的算法实现了极其微小常数因子的线性时间复杂度 $O(n)$。 - 在空间方面，程序所需的内存与 $n$ 成正比（$O(n)$），并且其内存访问模式对现代 CPU 缓存极度友好（cache friendly）。 在回答完该问题后，现场没有其他提问，Knuth 以一句欢快的“Merry Christmas”向全场观众致意，并在热烈的掌声中结束了第 23 届年度圣诞树讲座。 ## Notable quotes > [51:08](https://www.youtube.com/watch?v=BxQw4CdxLr8&t=3068s) 仅仅因为两个值吻合了非常长的位数，并不意味着猜想就必然为真；我见过正反两方面的情况。 — Donald Knuth ## Mentioned Donald Knuth, Stephanie, Piet Mondrian, Walter Stromquist, Thomas Kirkman, Jakob Steiner, Richard Stanley, Richard Brent, Brigitte Vallée, Bill Gosper, Neil Sloane, The Art of Computer Programming, American Mathematical Monthly, OEIS, Mathematica, Maxima, Wikipedia, Internet Archive ## Video description Donald Knuth's 23rd Annual Christmas Tree Lecture: A Conjecture That Had To Be True Speaker: Donald Knuth 2017 A few months ago, the speaker did some extensive calculations relating to a curious problem in combinatorial geometry; and the resulting numbers satisfied an amazing formula. Although this formula was known to be true only in the five or six smallest cases of the problem, it was impossible to imagine a decent world in which the formula would not hold universally. View the lecture and learn about the interesting sequel. About the Speaker: Donald Ervin Knuth is an American computer scientist, mathematician, and Professor Emeritus at Stanford University. He is the author of the multi-volume work The Art of Computer Programming and has been called the "father" of the analysis of algorithms. He contributed to the development of the rigorous analysis of the computational complexity of algorithms and systematized formal mathematical techniques for it. In the process he also popularized the asymptotic notation. In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces. [Source](https://www.youtube.com/watch?v=BxQw4CdxLr8)

[51:08] Donald Knuth: 仅仅因为两个值吻合了非常长的位数，并不意味着猜想就必然为真；我见过正反两方面的情况。

[0:04] so let's get started welcome everyone to [0:07] donald knuth a 23rd annual christmas [0:10] lecture entitled a conjecture that had [0:12] to be true it's hard to sum up who Don [0:15] Knuth is in a short introduction but [0:17] I'll definitely give it my best shot as [0:19] many of you know he's a computer [0:20] scientist mathematician and professor [0:22] emeritus at Stanford University he's a [0:24] renowned author of the art of computer [0:26] programming which covers many areas of [0:28] programming algorithms in their analysis [0:30] this book is still considered the first [0:32] and still best comprehensive treatment [0:34] of its subject and what the New York [0:36] Times is called the professions defining [0:38] treatise Don has written several several [0:40] volumes of this book among other books [0:42] as well as you know some some books to [0:44] pick up over here Don is well known for [0:48] sending a check for two dollars and 56 [0:50] cents one hexadecimal dollar to anyone [0:52] who can spot an error in his work so go [0:55] for it I say he has won the first ACM [0:58] grace Murray hopper award the Turing [1:00] award the National Medal of Science the [1:02] John von Neumann medal excuse me [1:05] the Kyoto Prize among other awards very [1:07] impressive also Don is an accomplished [1:11] musician and as his website states if [1:13] you drop him a note he's always down for [1:15] a jam session [1:16] Don will also be turning 80 soon so make [1:19] sure to wish him an early happy birthday [1:21] and we'll be celebrating in style at a [1:23] birthday party in northern Sweden where [1:25] symposium is being held his multimedia [1:28] work for pipe organ that is 50 years in [1:29] the making [1:30] Fantasia Apocalyptica will also make its [1:33] worldwide premiere so very exciting a [1:36] man of many diverse talents we are so [1:38] honored to have him here again for his [1:40] annual lecture so let's give him a round [1:42] of applause [1:49] when what Stephanie it's great to see a [1:53] lot of good friends and a lot of new [1:55] friends here and it's also always fun [1:59] when I go and I have a good story to [2:01] tell so I hope to enjoy what I'm gonna [2:02] be talking about I'm gonna I'm gonna sit [2:04] now as you said I'm almost 80 years old [2:06] after all so the title the title tonight [2:11] is a conjecture that had to be true now [2:15] this is this subtitle is what why is it [2:22] so much fun to do research because this [2:25] look this is the kind of story that I'm [2:27] going to be talking about is is the [2:29] story that gets repeated over and over [2:30] again when when you're working on on on [2:34] problems especially what in mathematics [2:37] theoretical computer science where where [2:40] you actually not only make guesses but [2:44] you can also often prove them and and so [2:49] so you see something that that's really [2:51] out of the ordinary and all of a sudden [2:53] then you get more and more confirmations [2:57] of this pattern you try something else [3:00] and it's still still the pattern holes [3:03] and so you say you know it can't be [3:07] false on the other hand how are how on [3:10] earth are we can approve it and I want [3:12] to I'm gonna show you an example that it [3:14] that effect that I think was [3:15] particularly fun occurred to me this [3:17] year in April and then I'll talk about [3:20] about some other ones F afterwards okay [3:23] so they so they just I gotta learn how [3:28] to use this this thing every year but I [3:31] but I think it'll be easy so let me show [3:34] you [3:38] relevant picture let me try to zoom in [3:43] on this guy here we go okay you see this [3:46] did so so moon ron was a painter who's [3:52] very famous for making compositions [3:56] where he didn't have to worry about [3:57] curves and things like this but he just [4:00] had rectangles inside a rectangle [4:02] and so most of the time tonight I'm [4:05] going to be talking about wreck dividing [4:06] a rectangle into rectangles and this is [4:09] a problem of course that people have [4:12] been working on long before Mondrian I [4:14] mean the yoke we have we have pavements [4:17] in your bricks people laid lay down [4:22] rectangle put them together and make [4:24] other rectangle in many different ways [4:25] and and well this year I'm writing a [4:30] part of part of computer programming [4:32] that deals with a really cool data [4:34] structure called dancing links and any [4:38] January I extended dancing links to a [4:40] much larger class of problems and I was [4:42] thinking what would be a good problem to [4:44] have to use as a interesting test case [4:48] and it turned out it related to breaking [4:50] rectangles and direct angles so I [4:52] started playing with get a pro with [4:54] rectangles into rectangles and and I [4:58] love you know people think that that [5:02] mathematicians have been working for [5:04] hundreds of years and now where's [5:06] there's tens of thousands 100,000 of [5:09] mathematicians all I love spending every [5:12] day working on problems so how could you [5:14] how could you possibly still find us a [5:16] simple down-to-earth problem that hasn't [5:19] already been studied you know way to way [5:22] too much and the answer is that those [5:26] problems aren't rare at all they keep [5:28] they keep coming up several times a year [5:30] and this is this is an example where [5:33] we're even is this very basic problem of [5:35] rectangle into rectangles and all kinds [5:38] of of sort of stones not yet turned okay [5:42] so first of all I'm a an integer [5:49] oriented person so I want to convert [5:51] this into into something that I can [5:52] understand better so here I have a blow [5:56] a picture of that of of that thing but [5:58] what the colors aren't important that [6:00] just if the rectangles into rectangles [6:03] and so the first thing I want to mention [6:06] is that any decomposition of rectangles [6:09] into rectangles can be energized into a [6:13] into what I call a reduced [6:15] so so you look at all the other [6:19] coordinates of the vertical lines and [6:22] you can number them starting with zero [6:24] so this would be number zero this would [6:25] be 1 this would be 2 this would be 3 [6:28] this would be 4 and this would be 5 and [6:31] then similarly for the horizontal line [6:34] so this would be 0 1 not too many of [6:38] those 2 3 ok now so once you once you've [6:42] done that then you can redraw the [6:44] picture to just show what the type of [6:48] this rectangle into rectangle thing is [6:50] so you make this into a 3 by 5 so I have [6:56] 0 1 2 3 and then I have 5 here 1 2 3 4 [7:05] whoops 5 ok and and so now this well the [7:13] boundaries always is always solid and [7:18] then there's also there's also this one [7:22] which is just this square and then and [7:26] this one goes 1 2 3 here is there the [7:28] one there what is wrong one too many [7:51] this is this is interesting but why did [7:54] I look which one am I missing here I [8:03] went from zero to one then I go to 1 to [8:06] 2 I see [8:09] labeled the whoa ok so here we are and [8:22] but that but you know you saved me 20 [8:25] minutes so that's really good ok now ok [8:27] so so anyway you see you see what [8:29] there's going to be it's going to be [8:30] distorted picture where where we have [8:34] you know this is going to be from 2 to 3 [8:37] and this is going to go like all the way [8:40] to 4 isn't it that one there ok it's [8:44] going to be something like that well [8:45] actually you know just look at the book [8:48] and the answer here ok so so here it is [8:54] this is what this is what it alright now [9:00] alright so this is a reduced [9:02] representation and until the first [9:05] question you ask is yeah you know how [9:08] many reduced representations of [9:10] rectangle interact on 3 by 5 are there [9:12] and and so in fact that's what exercised [9:18] 340s for how many of them are possible [9:21] of 3 by 5 okay well any guesses make it [9:30] make it make again there's no prize [9:38] 1 million okay [9:42] how many think it's more than a me so [9:54] it's it's its twenty thousand hundred [9:57] sixty-five okay so now I've almost out [10:02] of all those decompositions three by [10:04] five what's the largest number of [10:07] rectangles that you're going to find get [10:09] caught among them all [10:12] what mm mm no no I'm saying this [10:17] particular one has nine three three four [10:19] five six seven eight but is there one [10:23] that would be kept they would have nine [10:25] or more than eight what's the biggest it [10:29] could be 15 yes okay great what is the [10:41] minimum number now this is actually [10:43] turns out to be a tricky question that [10:44] and I'm not going to take the time to [10:47] prove it but you can think about it [10:50] because it because there are lots of [10:51] wrong ways to get the answer and then [10:54] but there's also a very nice short way [10:56] and the answer is M plus n minus 1 so in [11:01] this case seven all right three plus [11:04] five minus one so so you know if you [11:09] have only six it's not reduced you must [11:12] have left out you know in a reduced case [11:15] you've got to have something that comes [11:16] at coordinate one something that comes [11:19] at coordinate two and so on all the [11:22] intermediate Corden's have to be there [11:23] in order to be reduced okay so so this [11:25] is the and it turns out that that if you [11:31] if you insist on reducing it then then [11:34] the smallest you can get is is M plus n [11:37] minus 1 well this isn't you know you [11:39] think you can check it when m and N [11:41] equals one because you have to have a [11:43] one by one that's all you can do and you [11:45] and okay so there's a there's this [11:50] question of of being the smallest number [11:53] and I and I decided I would call it I [11:55] will call this tight because you know [11:58] it's it's a it's a tight lower bound and [12:01] and and and for in order to have a [12:06] convenient way to refer to it I call a [12:08] tight paving so in tight M by n paving [12:12] is is a reduced construction that has n [12:17] plus and minus 1 [12:20] rectangles inside of an M by n rectangle [12:23] okay now everybody knows that the that [12:26] the Internet is a wonderful it's a [12:28] wonderful resource for finding out about [12:30] any subject so I looked up tight paving [12:32] with Google and and here's what it [12:36] showed me okay so alright so in other [12:44] words I knew that nobody else had used [12:47] tight paving for mathematical discussion [12:50] but but a lot of a lot of people who are [12:53] actually in the paving business you know [12:57] have wonderful machines that will do it [12:58] tight okay all right now next let's try [13:04] to let's cut the big question I want to [13:07] ask is how many tight pavings are there [13:09] like three by five or M by n okay that [13:13] that's that's the question there you [13:15] start telling decided of course [13:16] naturally I wanted to investigate it [13:19] because my my beautiful data structure [13:22] was what was grinding out all the tight [13:25] pavings and I wanted to know if I was [13:27] getting the right number and also I had [13:30] a way to compute these numbers Oh real [13:33] real fast and so what but while we're [13:38] doing his guessing thing how many you [13:41] know I said there were twenty twenty [13:46] thousand yeah [13:49] twenty thousand hundred sixty five [13:51] reduced we do solutions but that [13:54] includes you know the tight ones and [13:56] also this one that it got to trivially [13:58] in the fifty [13:59] so so with my computer found with only [14:03] 18 million references to memory it it [14:06] computed those those 20,000 but now it [14:10] turned out then that one of those cases [14:12] had fifteen twenty two of them had 14 [14:15] 199 had 13 and so on but then you know [14:18] what the smallest case was when there [14:20] were only seven rectangle and how many [14:23] of you think that might have been if it [14:24] goes out of the 20,000 okay as there was [14:30] 107 one okay so 1071 ways to do it so [14:35] I'm not going to draw them all for you [14:36] but I'm going to explain to you how you [14:38] can actually count that and how that [14:40] leads to a conjecture that has to be [14:42] true any questions so far [14:46] okay all right now KB yeah what type [14:55] saving of a three by five is a it gives [15:01] a way to divide a three by five thing [15:03] into seven rectangles and your and you [15:06] have to have used every vertical line at [15:09] least once and every horizontal line at [15:12] least once [15:12] okay now and so but in order to make [15:17] that concept crystal clear let's look at [15:21] smaller cases [15:21] so let's first find all the type pavings [15:25] it has to be M plus n minus 1 so let's [15:28] look at all the type pavings for example [15:31] two by two okay so now I've got to use [15:37] okay so I took two plus two minus one is [15:41] three so so here's what here's one [15:43] example right are there any other so [15:47] yeah we got four of them because I can [15:49] rotate this four ways and that's it okay [15:52] so so two by two we get four solutions [15:55] okay now so let's let's try to get two [15:59] by three or in fact I'm gonna do three [16:02] by n so let me do three by two that so [16:05] I've got a nice like nice piece of paper [16:08] here to work with [16:12] they had a they had a conference in [16:15] Poland died last year and he sent me [16:18] this nice pad of paper and and I liked [16:22] it so much that I that I that I decided [16:28] at my birthday party next month I've got [16:30] to give out note paper but but actually [16:35] the note paper at my birthday party is [16:38] going to be triangle paper because I [16:41] because I have this I have a feeling [16:43] that that all kind of mathematics has [16:45] never been invented yet because people [16:47] haven't been given triangle three by two [16:54] and I know and I got to divide this into [16:57] 4 into 4 rectangles and you know like [17:00] this is one of them all right and and [17:05] well I can I can flip it over and get [17:09] this one okay now let's come up with [17:11] another one it's got to be four and I've [17:14] got to use I've gotta have at least two [17:17] you know two horizontal lines and one [17:19] vertical line was so yeah yeah this is a [17:24] cute one right okay and and it's mirror [17:27] image okay so for these oh we got sine [17:38] waves coming out of here [17:39] alright this what this was what you drew [17:44] this guy here and now we now you know [17:47] four ways to put to put underneath that [17:49] right because we because we already did [17:51] a lot of two by twos so so I can take [17:55] any of those two by twos and stick them [17:56] in there okay so let's you know this way [18:01] and this way and this way okay and and [18:06] well we can flip those over can't we [18:14] you can't flip the last one because it's [18:17] all it's already it's already flipped [18:19] it's already its own flip okay so let's [18:21] input this guy here and then I and and I [18:23] can divide this like that I can do like [18:26] that [18:26] and I can divide this like that okay so [18:29] now I've got eleven okay well it turns [18:31] out that's it okay so so so I run my I [18:36] run my program and I get eleven answers [18:39] and you know often when I do it by hand [18:43] the computer you know finds another one [18:45] but ah till then I tried three by three [18:49] and three by four and three by five and [18:53] and the number of answers I got so I had [18:56] you know okay n equal so 3 by n N equals [19:02] 0 1 2 3 4 5 I don't know what to say for [19:07] N equals 0 N equals 1 there's three by [19:10] one there's one way three by two is at [19:12] 11 3 by 3 it's 64 and here it's 282 and [19:18] then it was 1071 ok now so I I guess 3 [19:32] by 0 is is supposed to be a deposed to [19:38] divide the thing in 2 into 3 plus 0 into [19:41] 2 rectangles anyway it let's say 0 for [19:46] that okay so now okay now the last 30 [19:51] years or more there has been a wonderful [19:53] tool for all kinds of problems of this [19:55] form and and and it's been online for a [20:00] long time and so we have the our online [20:03] encyclopedia of integer sequences and [20:05] this is just the nicest thing since [20:08] sliced bread for mathematics because you [20:13] can compute your way into the literature [20:15] if you want to know if anybody else has [20:17] ever studied a problem all you have to [20:20] do is evaluate the first few cases of it [20:22] and then you look it up [20:23] and there and and the hit rate is is is [20:26] it [20:27] credible and all kinds of mathematicians [20:28] I discovered each other through the [20:31] online encyclopedia annual appeal please [20:34] make a donation to that keep it running [20:37] you know this is one of the this is one [20:39] of these I mean I I donate to Wikipedia [20:44] and Internet Archive event and and oh he [20:48] is which is the which is the wonderful [20:51] thing okay now so so I fed in these [20:54] numbers this was in April and you know [20:58] and so it said this is the number of [21:01] tight 3 by n pavings Wow what's this [21:04] well it turned out I submitted this [21:06] entry right I I you know but I typed it [21:15] in in April and nobody had done this [21:17] thing this yet before so I know it was [21:19] worth looking looking a little further [21:21] okay and so then it says and and there's [21:26] another sequence that that it got it is [21:32] a triangular array which which is the it [21:34] says you know for M by n rectangle for [21:37] all M&M it gives the number I submitted [21:40] that one too so so ok so here it says he [21:44] has a formula been invented to explain [21:49] these numbers and the answer is yes [21:50] there is a simple generating function a [21:52] simple closed form I will reveal it [21:54] after either the problem is rejected or [21:56] the solution is published because at [21:57] this time as I submitted this entry to [21:59] the online Cyclopaedia I also submitted [22:01] a problem for publication in the [22:02] American math monthly and and and so [22:05] then you give an example and then you [22:07] okay so so here was April 17th you know [22:10] I did I did the enumeration on Easter [22:12] day with April 16th in the April 17th I [22:14] submitted this and and the and not only [22:18] is this a great resource but the thing [22:21] is well curated I mean within within a [22:24] day I had seven people commenting on it [22:26] and and you're improving my presentation [22:28] X and checking everything up so Oh a is [22:33] is this fantastic and indeed that the [22:37] paper came out in the monthly [22:41] you know a couple months ago and here it [22:44] is tight Mboya and paving is the [22:49] decomposition etcetera etc etc one of [22:52] the 1071 possible 3x5 pavings is this [22:55] let a sub m and n denote the number of [23:00] tight m by n pavings determine a 3 n as [23:05] a function of n and show that when [23:08] you've got three or more that the limit [23:11] of a m n over m to the nth power exists [23:14] and compute the limit now actually I'll [23:19] say more about this because because I [23:22] didn't the way they publish me it sounds [23:27] as though I that I was able to solve [23:29] this problem [23:31] the fact is you know I knew it for M [23:35] equals 3 4 5 & 6 and there was this [23:38] beautiful pattern that had to be true [23:40] for M equals 7 8 and so on [23:43] but I'll talk more about that later so [23:46] so now I want to concentrate on the case [23:51] of 3 by n and you know later we talk [23:54] about 4 by n 5 and so all right now in [23:58] fact maybe we don't maybe warm up with [24:04] with 2 by n well however that's going to [24:22] take this I don't want to waste too much [24:24] time here so what so I so let me click [24:26] to me then we skip it but when you [24:31] really really working on on this of [24:33] course he eat at least if you do [24:35] anything like I do you don't jump quite [24:38] as fast as to the next step that I took [24:41] oh you first play around with a whole [24:42] bunch of things and make and make trial [24:44] and error and then you and you say oh [24:45] yeah this is what's going on and and and [24:48] so on but but but pretty soon [24:53] you come to a really thing in fact [24:58] there's one really great simplification [25:00] and that is that that the the problem is [25:03] equivalent that it turns out in all [25:06] these tight pavings there's exactly one [25:10] line in every in every row and exactly [25:14] one line in every column you don't have [25:17] a line over here and then another line [25:18] in the same row okay [25:20] and similarly vertically and furthermore [25:25] those lines don't cross each other they [25:29] can touch each other you know like [25:30] Japanese tatami mats aren't can touch [25:34] each other but they're not supposed to [25:35] be they're not supposed to come together [25:37] like four corners of the Tommy man it's [25:41] touching each other so you don't have a [25:43] line and another line crossing so in a [25:46] tight paving you never have a crossover [25:48] situation okay so now this is a tight [25:54] paving you can count it this is 5 by 15 [25:56] and and there are 19 rectangles there so [26:00] that's that's the right number of [26:02] rectangles and there's one there's one [26:05] line and everything and in this in this [26:08] solution I'm going to I'm just going to [26:11] examine the horizontal line well of [26:15] course we use that always the top and [26:19] bottom are all you go the full way but [26:21] then here then here's the lot the one at [26:25] at that height here's the one at this [26:27] site here's another one and here's [26:30] another one okay so here we have the [26:35] horizontal lines and and so you know [26:40] there's going to be M minus 1 of these [26:42] intermediate horizontal lines M plus 1 [26:46] line lines all together so for a 5 by [26:49] something that there are 4 of these [26:53] lines and if I look at the endpoints of [26:55] these things of course I'm not gonna use [26:59] all I'm not going to use all for 15 [27:02] points in the thing instead I've got [27:06] you know here here so so if I look at [27:13] the end points I got one two three four [27:15] five six six it's called zero one two [27:18] three four five six [27:20] for the end point three four five six [27:29] and so and so I'm going to classify all [27:34] of the five by end solutions by what I [27:40] call the type of the solution and this [27:43] is going to be I'm going to redraw this [27:47] and forget about all the all the other [27:50] cases and so I'm going to redraw this so [27:53] this could be five four three two one [27:59] zero [27:59] and then but I'm going to do this 0 1 2 [28:03] 3 4 5 6 and so on [28:07] so I redraw this and so this goes one [28:16] the 6 this goes to 2 3 this goes up 5 to [28:20] 6 and this goes to 2 4 okay and now the [28:27] vertical lines at these points are [28:31] predetermined because they can't cross [28:33] each other and so this is going to be a [28:37] sort of the narrowest example of this [28:42] type and so here is so so so this is a [29:01] type paving that has the same type where [29:05] I say two things are the same type is if [29:07] you only only look at the horizontal [29:09] lines and they're vertical and you don't [29:12] you ignore all of the ways of sticking [29:15] verticals in there now [29:18] the the key observation is that for [29:24] every type we can we can figure out we [29:28] can count how many things there are of [29:31] that type and so I'm going to exactly [29:35] I'm gonna illustrate that on a small [29:39] example so in fact that I had here these [29:51] which are all but these are all [29:57] reasonable types these are the types [30:00] what wait a minute [30:01] there are types of width so let's see [30:06] now I drew here all of the all of the [30:32] types that are possible for 3-bike by [30:39] two so why did I leave one of them out [30:40] let's see what's going on here this is [30:46] that one that one okay oh yeah [31:11] these eleven examples actually if I if I [31:21] look only at at at the horizontal lines [31:23] I have some cases like like this one [31:27] where I've never had a horizontal line [31:30] that started or stopped in the middle [31:33] and so this one would actually the type [31:37] of that one would be there because [31:40] because I say I ignore all the vertical [31:43] lines that that don't have a horse that [31:45] don't match your horizontal endpoint [31:47] okay so so now here's the thing if I [31:53] have a if I have a pattern that I can go [32:05] to well this time I'm going to show how [32:08] to make lots and lots of a five by [32:12] something from this pattern and and the [32:15] answer is well let me click let me draw [32:18] it a little bigger so I go five four [32:21] three two one zero and then here I'll go [32:24] zero one two three four five six [32:30] this is just so that I have space to the [32:40] room as I want this and this is going to [32:42] go across one two six this is going to [32:46] go to two three this is going to go [32:51] through four to five to six and this is [32:54] going to go to the floor and so I now [32:58] draw my vertical lines hope I do this [33:01] right okay here we go now so it so in [33:09] this region I can insert as many [33:13] vertical lines as I want [33:15] maybe maybe none or I can toss in [33:19] another one [33:20] in this region I can I can put a [33:26] vertical line above or below or above [33:31] but for each each time I insert [33:34] something I have a choice of putting it [33:35] up or down because I'm not allowed to [33:37] cross line so in this region I have I [33:42] can insert as many times as I want one [33:49] thing here sick so I have 1/2 the a [33:52] carry I can put 2 to the B of things in [33:56] here where a is some number of 0 under [34:00] zero or player here I have choices you [34:04] know in this region I have 4 choices in [34:07] this region for to the C ways to to put [34:12] in extra vertical lines still saying [34:15] with within the same type you know I [34:20] have 4 choices and and here I've got 3 [34:25] so here's 3 to the D and here I got to 2 [34:30] to the E and here I have 3 to the N and [34:33] and so I know for any choice of ABCDE F [34:39] of that at 0 or more I can make a I can [34:46] insert that and the resulting pattern is [34:48] going to be a tight paving it's also [34:50] it's also going to reduce to this guy [34:52] when I when I ignore all of the vertical [34:55] lines that don't that don't act that [34:57] don't match the endpoints of a [34:59] horizontal line and so the the number of [35:03] of tight pavings that reduce to this guy [35:07] is equal to the sum of 1 to the a times [35:11] 2 to the B times floor to the c3 to the [35:14] d2 to the e3 to the F overall a plus B [35:21] plus C plus D plus E Plus F is equal to [35:26] n minus 6 5 or 6 of C 1 it [35:32] if they're all zero I get one two three [35:34] I get so if n is 6 that would be zero so [35:39] so I not everybody gets it but the point [35:45] is every the point is every type failing [35:49] has a type and the number of types is [35:52] small and and and and and and once I [36:00] know the type I can comment exactly how [36:02] many for all n how many have that type [36:06] because you know because for example [36:10] let's let me show you all the types now [36:15] for things of size 3 so we have 3 by [36:20] here here's the type that has on only [36:23] one thing long and so I can insert it in [36:26] order to be in this type I I can leave [36:29] it as is that gives me 3 by 1 or I or I [36:33] can I think I can go from that at and I [36:38] can and I can change it and I can make [36:42] it I'm sorry this is a 3-way ok so so I [36:52] have to make a 3 by 3 I can choose one [36:56] of these three guys and then I could [36:58] choose one of these two guys and so in [37:01] order to make that this it you know so [37:04] the neck so so I got 3 by 3 there's [37:07] going to be nine ways to do it [37:09] I'm three choices for here and three [37:12] toys for here but three by four there's [37:15] gonna be twenty seven ways to do it and [37:17] so on all of those all of those reduced [37:20] reduce to this type however this one if [37:26] I make a three by n pattern that reduces [37:29] to this type I have three to the a ways [37:32] to do this for some number a and 2 to [37:35] the B ways for this and for it so if I [37:40] want the total to come out to be five a [37:42] plus B has to be five so that means I [37:45] either have [37:46] I'm sorry a plus B has to be three [37:49] because I've already accounted for two [37:51] so so I either have three three here and [37:56] no here or one here and two here and so [37:57] on so that would be three cubed times 2 [38:02] to the 0 or 3 squared times 2 to the 1 [38:04] or 3 to the 1 times 2 squared 3 is 0 so [38:08] that tells me number of 3 by 5 that [38:10] corresponds to this parent so this is [38:14] the this is the the point and and and [38:19] what when you're counting when you're [38:22] counting sums of this kind I it it's [38:27] beautiful because because the method of [38:30] generating functions is exactly exactly [38:34] the solution for this so if I look at a [38:38] at a power series for example Z over Z [38:43] minus 3 I'm sorry ok [39:19] Z over Z over 1 minus 3 Z for example is [39:25] equal to if I expand this a power series [39:28] its Z plus 3 Z squared plus 9z scoob + [39:34] 27 z forth and so on [39:36] this is this is a sum of a geometric [39:39] series and it's in a 0 for 1 minus 3 Z [39:42] now if I and so if I if I look at the [39:47] the number of 3 by n patterns that [39:55] satis number three by n patterns that [40:01] have this type it I said it was it was [40:04] it was one pattern of 4 3 by 1 3 4 2 by [40:10] 2 9 4 3 by 3 and so on 6 so so the [40:14] coefficients of Z Z square and so on [40:16] tell you how many there are of this type [40:19] now what about this type look well here [40:22] we had to choose threes and then twos [40:24] and so that turns out to be exactly what [40:28] 3 minus Z times Z over 1 minus 2 Z you [40:32] multiply these two power series together [40:34] and you get Z squared plus something [40:37] runner and I have a series that shows [40:42] all these numbers come in here so so ff3 [40:57] is this is a Z over 1 minus 3z and the [41:01] coefficient until you get Z plus 3z [41:03] squared xx or then F 2 squared that's [41:08] that's for this pattern and and so [41:12] that's Z squared for Z cube so it turns [41:16] out that with this pattern we're going [41:17] to get 1 3 by 2 we're gonna get 4 3 by 3 [41:22] we're gonna get 12 Z by 4 and so on and [41:25] and so so in other words I say that F K [41:33] is equal to Z over 1 minus K Z and and [41:42] in order to evaluate that this [41:44] particular sum this this is equal to if [41:51] I take this and I multiply it by Z to [41:54] the N I get F 1 F 2 F 4 F 3 F 2 F 3 [42:06] so I have I have an actual formula in [42:10] terms of Z's you know and I look at the [42:13] coefficients in their formula and that [42:15] tells me exactly how many exactly how [42:18] many five by n things are going to [42:21] reduce to that particular type okay so [42:23] this this means I have a way to count [42:26] all the three by hands particularly cuz [42:28] there are there are these 52 patterns [42:32] and and the in the patterns of width - [42:38] there's two of them that come out to F 2 [42:40] squared two of them come out to f1 f3 [42:42] four of them come out to be f2 f3 and [42:46] then they're these are patterns of size [42:48] 3 and music play and it was it was it it [42:50] was easy to grind out all these patterns [42:53] and and enter them I could feed that to [42:59] algebra system and it ground out the [43:01] numbers for the solution okay so in that [43:07] way I was able to I have to find the [43:12] formula now however I showed you that [43:16] this is a problem that's published in [43:18] the math monthly from October right and [43:21] it says here proposed solutions to the [43:27] problem should be submitted by February [43:29] 28 2018 and so I better not tell you the [43:33] answer right that you know I can just [43:39] tell you that you know if you work a [43:41] little harder you will get the answer [43:42] but I don't want to give away the ya [43:45] know the spoiler alert here's I can't [43:48] tell you that [43:49] too much more okay but look but but [43:52] anyway I but but I can I can tell you [43:57] that my answer I tell you at least part [44:03] of the answer that you thought you can [44:04] check your own work and and and so I [44:09] tell you the leading term of the answer [44:15] which I had here okay so in fact I okay [44:23] so my answer actually I'm gonna actually [44:31] reveal more than I should put by three I [44:33] can't read this okay a three and is [44:35] equal to one-fourth times 3 to the n [44:39] plus three [44:42] [Music] [44:44] well I'll give you just a little more 5 [44:47] times 2 to the N plus 4 and then plus [44:52] you know history terms okay so in other [44:58] words 8th a 3n you know according to [45:02] this it turns out then that a 3n is [45:05] going to be equal to 256 over 9 times [45:12] times 3 to the n plus terms that only [45:20] grow in order to to the end okay so okay [45:23] so this is the coefficient here 256 over [45:26] 9 it is the rate of growth you know what [45:30] that times the power 3 what for all the [45:32] tight pavings is that my three rows and [45:35] column all right now so I have my [45:39] program answer and so naturally I [45:44] couldn't resist looking at a 4 so my [45:47] head I had 52 patterns for 52 types for [45:51] 3 rows so I went to 4 rows and it turned [45:55] out that well there were 1464 different [46:04] types from the 4 rows for each of those [46:07] in a formula like f1 f3 f4 something [46:11] rather and and and the types that [46:14] involve f4 are the ones that are going [46:16] to have a 4 to the N in the answer and [46:19] it turned out that 576 of those types [46:22] made a small contribution to this too [46:25] a leading term for a four so a 4 n was [46:30] equal to something times 4 to the n plus [46:33] Big O 3 3 to the N well n times 3 there [46:38] but now and what's this [46:43] what was this magic coefficient well I'm [46:46] sorry [46:48] this was 256 overnight this one was 20 [46:57] 27 over 4 okay so okay so I got 27 over [47:07] 4 and then I got 256 over 9 and that was [47:09] too simple to beat you know this is the [47:12] sum of 576 individual fractions each of [47:16] which was pretty awful but it all [47:19] canceled out at the end to be 256 over 9 [47:21] okay so I didn't go to sleep that night [47:25] I went I went to a 5 in and it was 7 8 1 [47:34] 2 5 over 256 times 5 to the N plus plus [47:40] smaller term and this is power 5 250 it [47:46] looks pretty ok and the next one was 1 7 [47:50] 4 9 6 over 25 and so anyway the constant [47:55] in every case turned out to be M to the [47:57] 2m minus 3 over m minus 1 factorial [48:03] squared have you got the oh you took a [48:11] picture of it on that format okay so [48:13] this was now this this was a conjecture [48:16] then it worked for M 3 4 5 & 6 and this [48:21] was actually this was the sum of more [48:24] than but this was full there were 4 [48:27] million valid types and and it took it [48:31] took about 6 hours to do the case M [48:34] equals 6 to do the calculation and then [48:36] I feel it the Mathematica and get the [48:38] grind out all the coefficients and all [48:40] and there it was again checking it out [48:44] okay so clearly something's going on [48:45] here at that point I it to the math [48:49] monthly it's a demand explanation okay [48:52] all right now well so there was a happy [48:56] ending to the to the story because [48:58] Walter strum Quist [49:01] was the who was the referee of this [49:04] problem and the editor liked it so much [49:06] that he even told me the referees name [49:08] and got me in correspondence with [49:10] Wallace drunkest and and so so Walter [49:13] found to prove that this is indeed the [49:15] correct the correct answer and and well [49:19] it showed the problem to Richard Stanley [49:23] and I were guest with many other people [49:24] and and they said they hadn't any and [49:27] any ideas why they thought there might [49:29] be some connection with spanning trees [49:31] or something like this but but but [49:33] anyways from quiz was the guy who the [49:36] guy who solved it and and and so that [49:39] next year that that solution is going to [49:41] be published so so but but when I said [49:44] the conjecture had to be true you know I [49:46] couldn't imagine a world in which in [49:50] which these formulas you know would work [49:53] for anything there was there was a great [49:55] comet or mathematician in 19th century [49:57] named Thomas Paine Kirkman and and he [50:01] he's known mostly now for what's called [50:04] Kirtland schoolgirl problem but he was [50:06] but he was he was a pastor of an English [50:11] church and he in part-time mathematician [50:14] he ain't he he did all kind of [50:16] recreations and one of his papers which [50:18] which invented what later became known [50:21] as Steiner crippled systems although [50:22] kerkini was way ahead of Steiner one of [50:26] his papers a generalized the Steiner [50:28] systems to another thing and and [50:31] he has farmers in there which he which [50:34] he claims are true but but but when I [50:36] when I looked at at what his reasoning [50:38] was why it was true it was basically [50:40] that God wouldn't want it the formula to [50:42] be any more complicated than mine so [50:45] here he hadn't really proved his his [50:47] formulas but he just sort of said that [50:50] it had to be true [50:52] because it was too it was too hard to [50:54] believe that it could be false okay now [50:58] of course strong christop give a [51:04] rigorous proof this occurs all the time [51:08] in research when you when you see an [51:11] unusual a unexpected pattern then then [51:16] all of a sudden you jump to a conjecture [51:17] then you try it on it on another couple [51:19] of cases and then maybe you're confirmed [51:21] and and then and then you got okay now [51:26] the demands explanation and sometimes [51:31] then you then you could find the answer [51:33] sometimes you can't it in many cases in [51:38] my own life I had a conjecture was based [51:41] on on some numerical thing that I had [51:44] computed the most memorable was when I [51:46] was working on on analyzing factoring [51:49] algorithms and I and I was able to was [51:57] able to determine two to 20 decimal [52:03] places the the average size of the [52:06] second largest factor I think of a [52:08] random and bit number and and and the [52:16] third largest and so on and I and I [52:21] looked at this number and I said this [52:23] number looks a bit familiar and and so I [52:29] and and I saw in a book where they had [52:34] given the first five digits and --ml to [52:39] the five edges I Drive empirically and [52:41] the author of that article called the [52:44] number e to the minus gamma where gamma [52:46] is Euler's constant and so I said oh my [52:49] gosh either the minus gamma must be the [52:52] answer to my problem so I ran to this [52:56] was in the 70s and and we didn't have [52:58] any powerful symbolic systems on our [53:01] computers [53:02] now but I could login to two Maxima at [53:05] MIT and I remember I was so I was so [53:09] nervous I you know I I forgot the phone [53:12] number how to log in at MIT and so on [53:14] but finally I did and I typed in yeah I [53:19] went to my book to look up the decimal [53:21] expansion of gamma so that I could tell [53:23] max my raise e to minus this power and [53:26] and see if it agrees to 20 did decimals [53:29] with the number I just computed and and [53:33] and but then I looked at the number I [53:36] just computed then I and I and I found [53:39] out that was also in my book I had also [53:41] e to the minus gamma in my own book so I [53:44] didn't have to use Mathematica but a [53:46] maximum but but it disagreed in the 16th [53:50] decimal and so here I had here I had a [53:54] very natural mathematical problem and it [53:56] and it agreed with a very natural [53:58] mathematical expression but this up to [54:01] 16 decimals and then failed and so how [54:04] could this be true and for the next week [54:07] I tried get a better but I done the [54:09] numerical integration with my own [54:11] software so I know naturally I suspect [54:14] is above but I couldn't find a single [54:16] error in it well finally it turned out [54:18] that that my my program was right but I [54:21] had used a formula for numerical [54:25] integration that's only that's only [54:27] correct if the fourth derivative of the [54:29] function you're integrating is [54:30] continuous and this particular function [54:33] work has a discontinuous fourth [54:35] derivative so so so so go the answer oh [54:39] so the discrepancy turned out in the [54:41] 16th decimal place ok now another time I [54:43] was I was analyzing the the binary you [54:46] euclidean algorithm [54:47] it wasn't my analysis it it was Richard [54:50] Brennan and and he came up with an [54:51] analysis and and another ballet and in [54:55] France came up with another analysis and [54:58] they had [54:58] analysis of the binary algorithm for [55:01] getting GCD and they agreed to 11 [55:05] decimals but then there was a [55:06] discrepancy [55:07] well it turned out that this was a real [55:09] discrepancy that there's a little bit of [55:11] there was a little bit of wobble going [55:13] on when [55:14] looked at the complex of function that [55:15] was involved in and it has a very small [55:18] amplitude but a DAC actually would would [55:20] show up if you did the exact calculation [55:23] there was a there was a small you know [55:25] Lord login type of periodicity in in [55:30] their average value zero that actually [55:32] affected these integral so you can't you [55:35] know just because you have a have [55:37] agreement to long plays it doesn't [55:39] doesn't mean that the conjecture has to [55:41] be true I've seen it go both ways now [55:44] just last month bit of bill gossipers [55:47] sent me a conjecture bill are you here [55:50] okay well and and in this one I think [55:57] almost it's almost certainly going to be [56:01] true and somebody who is finding the [56:04] answer next EUR and Ike and involves the [56:06] golden ratio people know what the golden [56:08] ratio is that this is the big the the [56:13] famous the famous number that's supposed [56:19] to represent the ratio the most [56:21] beautiful proportion between two things [56:23] and and and they and they call it Phi or [56:27] tower depending on how sophisticated a [56:29] mathematician you are and and so and so [56:34] so bill sent me whoops let's zoom in on [56:39] this on this number here two to the two [56:42] fifth power times the square root of [56:45] five times [56:46] the gamma function at 1/5 to the fourth [56:49] power and divide that by the gamma [56:51] one-tenth squared and gamma 3 10 squared [56:54] and it note okay now evaluate that to a [56:57] thousand decimal okay and so well the [57:00] the running time was which was a third [57:03] of a second and it comes out 1.618 oh [57:07] three three nine nine so it's is exactly [57:09] the golden ratio to a thousand decimal [57:12] okay so so this has to be true and and [57:18] and there are a bunch of forms of this [57:21] kind that have [57:23] have resisted proof for a while and but [57:27] then if somebody cracks them and then [57:28] and and we move on and get to another [57:30] class I want to end with something that [57:34] that's that's unsolved and I have a [57:36] feeling nope I'm feeling that if that on [57:40] the one hand it has to be true God [57:44] wouldn't want it to be any other way but [57:46] I also have a feeling that maybe nobody [57:51] will ever find a proof there might not [57:52] even be a a finite proof of the result [57:55] and and this this is related to one of [57:59] the most classical comet oral problems [58:02] of of all time the N Queens problem the [58:09] problem of placing Queens on a chess [58:11] board so that they don't attack each [58:13] other now consider the infinite Queens [58:16] problem so here we have I'll take the [58:20] entire first quadrant of the plane and I [58:25] and I imagine that I want to place [58:28] Queens on this us so that they don't [58:31] attack each other I'm going to let's [58:33] zoom in on the very beginning here so [58:35] well if the five by five works out [58:39] beautifully you've got but what I'm [58:42] saying is what's the the the smallest [58:44] possible solution the lexicographically [58:48] first solution to the infinite queens [58:51] problem so people also say greedy Queens [58:55] because because you put each Queen in [58:58] the as far to the left as you can [59:01] without attacking the ones there [59:03] previously so you start out there and [59:05] you put the first Queen right there then [59:07] the second Queen can't go next to it but [59:10] then you can make a nice move away and [59:11] in the third Queen there okay but now [59:14] the fourth Queen finally you can stick [59:17] it you can stick it here in the second [59:19] column and and the fifth Queen you can [59:22] get into the fourth column okay now look [59:23] now the sixth Queen these are all [59:27] everything is attacked now except up to [59:30] here and so the six screen goes there in [59:33] position nine and then position 11 and [59:36] then four [59:36] 13 and 15 but then all of a sudden we [59:39] can fill position six with the with the [59:45] next Queen and so on so so we get this [59:47] pattern and this is a sequence that you [59:53] can look up in the online encyclopedia [59:55] of integer sequences and you'll see that [59:58] that it Neal Sloan who's the founder of [60:02] that website I entered this sequence [60:06] about a year and a half ago and and [60:09] noticed this incredibly remarkable [60:11] pattern and that is that that is that [60:15] these positions of the Queen lie almost [60:19] exactly on two lines there's dock that [60:23] there's the ones that are you know where [60:26] X is greater than Y and those that are X [60:28] is less than Y and and and what's the [60:34] slope of this line the golden ratio and [60:39] and what's the slope of this line went [60:42] over the golden ratio okay so now the [60:50] agreement is incredibly good and I I [60:59] wrote a program to calculate the numbers [61:02] and it's a sine line you can look it up [61:04] it's a literate program and it has a lot [61:06] of interesting little hacks in it [61:08] infinitely many queens and it it needs [61:12] only on the average something like nine [61:15] memory references per value of n and so [61:18] you can you can quickly go up to several [61:21] hundred billion in the sequence and and [61:26] when you and when you check it out you [61:31] know like suppose like when I go up to a [61:35] billion okay well then almost all of [61:37] those numbers are either one six one [61:39] eight oh three or or six one eight oh [61:43] three in the neighborhood of a billion [61:46] plus plus or minus you know one two [61:51] three four five all those numbers are [61:53] very close to are to either five times a [61:55] million or a billion or a billion over [61:58] five and and the patterns are reared [62:04] they there are a few screen points but [62:06] the outliers seem to stop at about at [62:08] about 4,000 or so and and and and [62:13] there's a very tight balance so that [62:15] seemed to be true on the other hand it [62:18] might be like Goldbach's conjecture we [62:19] might not ever find a proof of it we [62:21] just know that that it has to be true [62:23] because it's overwhelmingly probable [62:24] probably true so so that's a technique [62:28] so now to recapitulate I I showed you [62:32] the problem that I that I ran across in [62:35] April that got me hooked when I saw I [62:40] saw this strange pattern involving [62:42] powers and factorials and and I checked [62:46] it and I said oh yeah this has to be [62:48] true then I submitted it to the monthly [62:52] and another mathematician saw it he [62:54] actually found a way to prove it so [62:56] great then I gave a couple of other [63:00] examples of cases where where things did [63:03] turn out to be true that they don't and [63:05] and here's one that brand new brand new [63:08] open how many mathematicians are gonna [63:10] are gonna work on it it's quite [63:13] intriguing because you know yeah [63:15] absolutely no economic payoff whatsoever [63:17] that's completely you do it just purely [63:20] for love and beauty and so so that so [63:26] this it this is the way research goes [63:29] and and when you do find the proof then [63:31] you're really happy for a couple of days [63:33] and of course then the next day you find [63:36] another problem and and again you have [63:38] to have to solve that one okay thanks [63:42] very much for this [63:44] [Applause] [63:49] [Music] [63:57] questions I'm sorry I didn't hear [64:04] conjecture in with the camera functions [64:07] the conjecture about the demo function [64:08] yes it's two kids so there are a lot of [64:27] identities that involve the gamma [64:30] function [64:35] you know gamma x times gamma 1 minus X [64:38] and various things like this the [64:39] triplication formulas and things like [64:41] this and this seems to to be related to [64:43] the critter placation formula but but i [64:47] think i think i've used it in some new [64:50] ways and you brought up your brought in [64:52] some other stuff in here so yeah so as [64:56] far as I know he hasn't solved it yet [64:58] but what he posted this beginning about [65:02] totally the reason I read the reason I [65:12] think this was going to be solved is [65:13] because I know that there's a lot of [65:17] mathematics of this kind machinery [65:21] that's that's there but the other one [65:23] the Queen's problem it's it's look like [65:28] nobody even knows that all the integers [65:31] are going to occur somewhere in the [65:32] sequence you're there Mike there might [65:36] be some some coordinate that that's [65:37] always ruled out it Neil said he he [65:42] thought he had a proof of it but but but [65:46] when he got to writing up the paper it [65:48] all it all collapsed so it it depends on [65:54] random from sort of random phenomenon [65:56] that just oh yeah one of these queens is [65:59] probably gonna it's probably going to be [66:02] there and since we're all on these on [66:04] these lines and then but you know [66:06] they're so [66:08] there's a lot of structure to it that's [66:11] why I was able to write this tricky [66:12] program that that needs so fix a few [66:15] operations to calculate it like [66:18] attribute the brute-force program would [66:20] would be more like an Ncube time instead [66:23] of instead of linear with a very very [66:26] small coefficient the boat the program [66:33] needs it needs memory a portion of the [66:36] end but it's very cache friendly okay no [66:44] more questions thank you Merry Christmas [66:46] [Applause] [66:59] you