线性代数在组合数学中的应用-技术圈

数学算法俱乐部

日期：2020年07月29日

正文共：1438字4图

预计阅读时间：4分钟

来源：算法与数学之美-姜子麟

我的研究方向是组合数学 Combinatorics，又称具体数学。这个学科里绝大多数的问题都能用简单的语言描述，但解答又不显然。

在卡内基梅隆大学读研究生的第二年暑假，导师推荐给了我一本书 Thirty‑three Miniatures，作者是 Jiří Matoušek。乍一看书名，可能会猜测是一本包含 33 个小故事的故事集（突然想起了桂纶镁主演的第 36 个故事），但实际上这个猜测也八九不离十了。书的副标题是 Mathematical and Algorithmic Applications of Linear Algebra —— 这本书包含了 33 个线性代数的数学和算法应用。

比如书中回答了以下组合数学问题：

在 Oddtown 里面住着 n 个居民，他们的主要工作是组建各种各样的俱乐部。为了限制俱乐部的个数，市政府决定颁布如下条例：每个俱乐部只能有奇数个会员并且任何两个俱乐部只能有偶数个公共会员。证明：不可能组建超过 n 个俱乐部。（取自 Miniature 3）
平面上不存在四个点，两两之间距离均为奇数。（取自 Miniature 6）
一个长宽比为无理数的长方形无法用有限个正方形铺砌（正方形内部不相交且覆盖长方形）。（取自 Miniature 12）
一个网店正在处理订单，突然所有小于 1 元的硬币都被作废了！所有商品的价格都要取整（可以选择向上或向下取整）。如果每种商品卖了至多 t 个，并且每个订单中每种商品至多包含 1 个，那么有一种取整的办法使得每个订单的总价变化不超过 t 元（有趣是总价的变化和订单数、商品数均无关）。（取自 Miniature 19）

令人惊讶的是，理解这些问题的解答只需要明白大学本科的线性代数知识！好吧，其实还需要知道有限域上的线性代数。在此，我补充一个在这本书里面没有的组合数学问题。

问题：平面上 n 条一般位置的直线（没有三线共点或两线平行）至少会产生 n - 2 个小三角形。

解释一下小三角形的意思：

如图所示，5 条直线把平面划分后，形成的区域中为三角形的部分就是所谓的小三角形。

现在，就是见证线性代数的奇迹的时刻了！

证明：反证法，假设产生了 m < n - 2 个小三角形。固定 L1, L2 两条直线，再让其他直线平移起来！也就是说，对 L1, L2 外的每条直线的法向量制定一个速率（可正可负）。附加条件是：每个小三角形大小保持不变。如下图，如果斜的两条直线决定以那样的速度移动，为了保持小三角形大小不变，水平的直线必须以某个规定的速度移动。

换句话说，决定小三角形的三条直线的平移速率必须满足某个约束条件。可以证明每个约束条件关于平移速率是线性的（请读者自己思考）。那么现在我们有 m 个小三角形，即 m 个线性方程，以及 n - 2 个直线平移速率作为未知元，由于 m < n - 2，线性代数告诉我们存在非零解！也就是说，确实可以在保持每个小三角形大小不变的情况下，让 L1, L2 外的一部分直线平移起来！在整个平移的过程中，考虑第一次某三条直线交汇于一点的前一个刹那，如下图。

ちょっと待って，说好小三角形大小保持不变呢！下一刻，这个小三角形都要消失了！矛盾 ╮(╯_╰)╭

这里有一个需要补充的细节，为什么一定会有三条线在运动后交于一点呢？一方面，L1, L2 两条直线固定，考虑第三条直线 L 正在移动，那必定有一个时刻 t 直线 L 会穿过 L1 和 L2 的交点。如果这个时刻 t 为负数，那我们转而考虑反转所有速度后的运动。

证毕。

文初提到的作者无私地将初稿放在他的主页上。如果想阅读，可以直接以书名作为关键词搜索。我个人非常得益于 Jiří Matoušek 的写作，但很不幸，他于 2015 年 3 月 9 日去世了。谨以此纪念他。

后记：在 2017 年于 Akko 举行的以色列数学大会上，有幸遇到了文中描述证明的发现者 Alexei Kanel。这篇文章 Taking on triangles: in search of answers between the lines (https://www.researchgate.net/publication/301276231_Taking_on_triangles_in_search_of_answers_between_the_lines) 中详细描述了发现这个证明的过程。

— THE END —

☞北大读博手记：怎样完成自己的博士生涯？非常具有指导性！

☞他把400个流氓送进哈佛耶鲁！寒门与贵族之间，只差一个数学老师！