# 罗博深：数学、数学奥林匹克、组合数学与接触者追踪 > 数学家谈奥数训练与组合数学思维，以及如何用数学建模来做接触者追踪。 - 原标题：#183 – Po-Shen Loh: Mathematics, Math Olympiad, Combinatorics & Contact Tracing - 期数：第 183 期 - 发布日期：2021-05-14 - 嘉宾 / 主题：罗博深 - 网页版：https://lexfridman-cn.pages.dev/ep/po-shen-loh/ - 官方页面：https://lexfridman.com/po-shen-loh/ - 精读字数：约 7509 字（阅读约 17 分钟） > 本文为 lex.qiaomu.ai 基于原始访谈的 AI 改写中文精读，非官方翻译；引用请注明出处并链接网页版。 2020年3月，美国因新冠疫情进入停摆。一位卡内基梅隆大学的数学教授，带着一支以用户体验设计师为核心的团队，提出了一个当时几乎没人这样想过的问题：如果疾病真的来了，你希望手机告诉你什么？常见的做法是通知你"你昨天接触过病人，请隔离"。他想的却是另一件事：**这个病毒现在离你还有几层关系**。前者是事后追责，后者是事前预警。这个视角的切换，最后演化成了一个叫 Novid 的 App，也成了他眼中未来应对大流行的一条新路。 他叫罗博深（Po-Shen Loh），卡内基梅隆大学数学系教授，美国国际数学奥林匹克（IMO）国家队主教练，在线教育平台 Expii 的创始人。这期播客里，他跟 Lex Fridman 聊了数学、奥数、组合数学、接触者追踪，也聊了教育、自由，以及一个人该怎样衡量自己这一生的意义。 ## 数学的难，藏在"发明"里 很多人把"数学很难"当成一句抱怨。罗博深不这么看。 他区分了两种"难"。一种是记忆的难，你得把老师教过的方法一条条背下来，考试时再原样套用。另一种是发明的难，你面对一个从没见过的问题，不知道该从哪里下手，但经过一段时间的思考，你能自己找到一条路。前一种难让人痛苦，后一种难让人上瘾。 > 我从来不想直接告诉别人"你应该这样做"。我更喜欢说，这里有一个有趣的问题，我知道你还不太会做，你有什么想法吗？（罗博深） 这套方法在课堂上真刀真枪地跑过。他在卡内基梅隆的课，考试占总成绩的90%，而且考试全部开卷，学生可以把往年所有题目和笔记都带上。但他给了一个保证：这次考试的题目，和过去给过的任何一道题都不重叠，也和他课上讲过的任何内容都不重叠。整场考试就是一次发明。 第一次考试通常一片哀嚎，学生会想，这什么疯课，教授根本不教考试要考的东西。但到第二次、第三次，情况会变。学期结束时，学生学会的不再是某个方法，而是这个领域里的任意问题都能自己想办法解决的底气。 他说他上课像即兴喜剧。没有讲稿，走进教室，大家一起把一个证明"演"出来。他接住学生抛出的每个想法，再往前面推一步，跟即兴喜剧里的"yes, and"一个道理。所以每次教同一门课，每个证明都略有不同，因为那是学生现场想出来的。 ## 奥数的评分现场，像一场跨语言的陪审团 国际数学奥林匹克，是大学之前最顶级的数学竞赛。每个国家派6名选手，两天，每天4个半小时做3道题，一共6道题，每题7分，满分42分。 这些题目不是算数。题目通常是这样一句：请解释为什么下面这个奇怪的事实是对的。你从没见过它，但你要写出一篇论文式的解答。解出任意一道，就已经是天才级别，可以拿荣誉奖。 评分过程很有意思。主办国会派出大约50人参与阅卷。每个国家的领队和副领队，跟主办方的两三个人坐在桌子两边，对着一份试卷，按既定标准讨价还价。有趣的地方在于，很多国家的选手用母语作答。蒙古选手用蒙古语写，绝大多数阅卷人看不懂，只能靠蒙古队的教练现场翻译，说明学生到底写了什么。 罗博深说，这个过程有点像陪审团，只不过陪审员之间有时候语言不通。美国队的答卷一律用英文写，所以谁都能看，反过来也意味着他们没法做什么手脚。有时候美国队坐下来，会主动说：你们给的分太多了，按我们的标准，这道题不该拿这么多分。 > 我们不讨价还价去争取更高的分数。有时候我们会说，你给的太多了。（罗博深） ## 一道题有多难，取决于它藏了几个"洞察的跳跃" 罗博深给难题下过一个定义：数一数从题目到答案，中间需要几次视角的切换。他管这叫"洞察的跳跃"（leap of insight）。 每一次跳跃，都意味着搜索空间的一次大分叉。所以一道需要三次跳跃的题，难度会远远超过一道需要一次跳跃的题的三倍，它是指数级的差距。因为每次跳跃之后，你都不能确定这一步是不是对的方向。 他用这个思路读数学教科书。大学时他发现自己读数学书效率极低，一页纸上全是正确的话，读完却完全不知道自己读了什么。后来他换了方法：看一眼定理的陈述，看一眼证明有多长，然后合上书，自己尝试重新证明一遍。 证明的长度，大致正比于洞察的数量。一段两页长的证明，意味着里面藏了好几个跳跃，是真正的硬骨头。一段五行就结束的证明，说明只有一个洞察，可以自己先试试。 这个经验法则不精确，但在他自己的书里、同一主题的范围内，相当管用。他甚至把同样的思路用在竞赛里：看一眼题目是第1题、第2题还是第3题，就大致知道要跳几次。 这背后是一种更深的认知。人类发明东西的时候，最折磨人的地方在于方向的未知：答案在哪里固然不知道，更让人不安的是，你连自己此刻站的方向对不对都无从判断。安德鲁·怀尔斯（Andrew Wiles）花了七年攻费马大定理，七年里大部分时间都在承受这种不确定。罗博深说，专业研究者之所以愿意忍受这种折磨，是因为当那些洞察终于串起来的那一刻，感觉实在太好了。 ## 数学是发现的，还是发明的？ Lex 抛出了这个老问题。罗博深的立场是"发现"。 他的理由来自他选题的偏好。他总被那些看起来简单、却异常困难的问题吸引，比如费马大定理。为什么一个小孩都能读懂的命题，会难倒人类三百多年？如果数学是我们凭空发明的一套语言，这种"简单的表述、深邃的结构"就不该反复出现。 他还想象了一种场景：如果人类在宇宙中遇到另一个智慧物种，双方对比笔记，大概会发现彼此都意识到了圆周率很重要。你可以说人类偏爱圆形是因为我们的感知方式，但恒星也偏爱圆形，行星也偏爱圆形。圆这个概念，就是"一个点，等距"，再没有比它更简单的东西了。 当然，对方物种的认知结构可能完全不同，它们可能看到的是我们根本看不到的东西。所以真正的难题在于：两套心智要花多少功夫，才能磨出一套共同的语言。Lex 提到电影《降临》，讲的就是这个：如何与外星文明建立沟通。数学看似是最有希望的桥梁，但即便在数学里，也得靠可视化的证明、靠来回比划、靠"我这里有个想法，你看这样能不能理解"，一步一步磨出一套共同语言。 ## 投票树：一个关于选举的数学问题 罗博深研究过一个有意思的课题：能不能把选举设计成一棵电路树。 两个候选人竞选很简单，直接比票数就行。但候选人一多，问题就来了，谁赢了其实很难说清。他设想的场景是：所有候选人两两之间的强弱关系是已知的，现在要设计一张"电路板"，让候选人在上面两两对决，胜者晋级，像一棵二叉树一样往上爬，最后走出一个冠军。 这里有个很自然的要求：冠军最好赢过很多人，光赢过一路上遇到的那几个对手远远不够。他先讲了一个漂亮的事实。 如果有1024个候选人，其中必然存在一个人，至少赢过其他512个人。 这个结论第一眼不显然，但证明很巧妙。想象每一场对决，双方各记1分（先别管真实规则里只给胜者记分）。这样一来，每个人的总分都一样，等于"其他候选人的数量"。现在改成只给胜者记1分，等于砍掉了一半的总分。总分减半，那么必然有人高于平均值，也就是至少赢过一半的人。这是期望值的基本性质：一个随机变量的取值里，总有一个不小于它的期望。 接下来是设计电路。传统的平衡二叉树有个漏洞：可能有一个候选人，一路上只赢过十来个对手，却因为签运好，最后爬到了顶上。这样的电路，你不能放心地用在所有选举里。 罗博深和合作者设计出了一种新的电路结构，把"冠军至少赢过多少人"的保证，从原来的对数级别（大约 log₂N）提升到了平方根级别（√N）。对1024个候选人来说，这意味着冠军的"含金量"门槛高了一大截。 他描述了一个核心部件：让候选人7分别和 A、B、C、D 单独对决，然后这些胜者再两两对决，层层往上。这样设计的好处是，如果你看到7最终从顶上冒出来，你就知道7是真的打败了这一大群对手；如果顶上冒出的是别人，比如 F，那至少 F 在某个环节赢过7。这个结构保证了一件事：无论谁赢，他击败的对手数量都有一个下界。 罗博深补了一句：这套东西跟改进现实中的选举制度是两回事。好想法能不能被采纳，是机制设计问题，是要在承认人性弱点的情况下，设计出让人愿意接受的激励结构。那是另一场仗。 ## 分布式求和：一枚硬币和一次"招聘" 罗博深在微软研究院待过一个夏天，研究过随机聚合（stochastic coalescence）。 问题是这样：假设有一大群人，每个人知道自己昨晚睡了几个小时，现在要算出所有人的总睡眠时间。线性做法是一个一个问，一个一个加。但有个更聪明的办法：既然每个人都会加法，那就让他们自己并行地加起来。 1024个人，1号和2号把各自的数相加，2号消失，1号记住结果；3号和4号相加，3号记住结果。然后1号和3号再相加。这样一层层往上，形成一棵树。因为所有操作并行进行，总耗时只有树的层数，也就是10步，是对数时间。 问题来了：你怎么决定谁和谁配对？如果你站在市中心喊"你们俩一组、你们俩一组"，那还是线性时间，等于作弊。 于是有人提出了一个优雅的分布式方案。每个人一开始都是自己的"代表"，指向自己，手里攥着自己那份数字。每一轮，每个人抛一次硬币，决定自己是主动出去"找人合并"，还是待在原地等别人来。主动的人随机挑一个人，如果对方已经归别人管，就顺着指针往上走，找到真正的代表。代表之间有带宽限制，一次只能吸收一个人，多余的请求被拒，下一轮再来。被吸收的人把数字加进去，更新自己的指针。 这个方案的美妙之处在于，整个过程不需要任何人知道全局结构，完全是自组织。但罗博深发现了一个隐藏的陷阱：代表去接触别的代表时，命中的概率正比于对方这个"块"的大小。块越大越容易被找到。极端情况下，会出现一个巨大的块和一大堆还没合并的单人块，那个大块每轮只能吞一个人，于是耗时退化成 √N。 他证明了这种不平衡确实会自然发生，所以纯对数时间不成立。但他也找到了一个极小的修补：当代表收到多个请求时，不要随机选，而是接受最小的那个块。就这么一点改动，就能把块的大小重新拉匀，把整个系统的效率救回来。 他由此联想到代表制民主。未来也许会出现一种新的投票方式：你信任某个朋友在某件事上的判断，就把票委托给他，他再委托给更懂的人，一层层长出一张自下而上的代表网络。一人一票直接选总统这种形式，或许只是众多可能中的一种，而且未必是信息传递效率最高的那一种。这种网络结构，在互联网时代第一次变得可行。图论这门学科大部分理论在上世纪就做完了，但它的应用要等到21世纪，这是让人兴奋的地方。 ## Novid：让病毒"显形"的那一层关系 回到疫情。 传统的接触者追踪，逻辑是这样：查出谁病了，查出他接触过谁，然后把这些可能被感染的人从社会里隔离出去。罗博深说，这个反馈回路的根本问题是"违背当事人意愿"。你试图控制几十亿人去做他们并不想做的事，这个回路方向错了，所以越控制越失控。 他换了个问题：假设你是普通人，疫情期间你最想要什么？你想要的是能继续正常生活，同时尽量别被传染。那就该换一件事做：帮你避开病毒。等接触了病人再把你隔离，那是另一条路。 可这个病有个特点，症状出现前两天就已经能传染，你根本看不出谁病了。这时候网络理论派上用场：你身上的病毒是从某个人那里来的。换个度量方式呢？不去算病毒离你多少米、多少秒，改算病毒离你隔着几层人际关系，情况就完全不同了。 这个度量，像 LinkedIn 上的"几度人脉"一样，是一个很自然的想法。但罗博深说，正是这个简单的切换，解锁了一整套全新的行为反馈回路。 他举了一个极端的例子来说明它的威力。假设有一种病，致死率极高，患者七窍流血，空气传播。这种病一旦爆发，有多少人愿意装一个 App，来知道自己离这种病还有几层关系？几乎所有人。 也就是说，疾病越可怕、传播越强，人们安装这个 App 的动机就越强。危险程度越高，系统普及越快，防控越有力，一条正反馈就这么转起来了。罗博深说这个观察不是他先想到的，是另一位朋友提醒他的，但他认为这是整个系统最值得骄傲的性质之一。 更妙的是行为的对称性。过去所有防控方案都在盯"A组"（可能已经生病的人），想办法让他们别出门。而 Novid 盯的是"B组"（目前还健康的人）。当 B 组里的人发现病毒一层层逼近，他们会自己选择收缩社交、减少接触。于是 A 组和 B 组之间自然拉开距离，而这一切都出于自愿，出于每个人的自利动机。 > 这就像自由市场经济和中央计划经济的区别。你只需要把激励结构摆对，让每个人在纯粹自利的行为里，恰好优化了全局函数。（罗博深） ## 技术上怎么做到不碰隐私 Novid 的一个硬约束是：绝不要求用户提供个人信息。 做到这一点靠的是蓝牙。两台装了 App 的手机靠近时，通过蓝牙感知彼此的相对距离，不需要 GPS，不需要精确坐标，只需要"我们当时大概离得这么近"这个相对关系。这些关系拼起来，就是那张物理接触网络。 距离的测量是概率式的。手机每隔五到八分钟扫描一次周边，像拍电影一样一帧一帧地记录。偶尔在超市里跟陌生人擦肩十分钟，这种关系会在统计上被冲淡。Novid 问的是未来：你接下来可能遇到什么风险。它不追问过去：你之前可能被谁传染过。只有那些反复出现、持续时间长的关系，才会在算法里浮现为一条真正的边。 整个系统的算法要求是线性的。全球也就七八十亿人，服务器一小时重算一次，用 C++ 写的后端，一台四核云服务器就能扛住一个几十万到上百万人的社区。罗博深说，这个"先用信封背面算清楚复杂度"的习惯，直接来自他高中时代的编程竞赛。如果算法不够快，你还没等到规模做大，就已经被服务器账单拖垮了。 他特别提到，iOS 系统对后台运行非常苛刻，蓝牙常驻扫描很耗电，很多团队（包括英国的一些尝试）都卡在这里。Novid 团队花了很多力气把功耗压下去，甚至比苹果自家的方案还省电。 App 还会给每个人展示一组图表：你有多少直接接触者，两度关系有多少人，三度关系有多少人。很多人看到自己在系统里间接连着成百上千人时会兴奋，然后主动拉更多人下载。罗博深说，他们的 App 在高校试点时，平均每个人只要有两三个直接连接，就会触发传播。他们是在用一款 App 去"传染"，去对抗同一张网络上传播的病毒。 当然，为了防作弊，需要验证机制。谁都能声称自己阳性，高中生的恶作剧会是"决赛周宣布大爆发，取消考试"。所以系统借鉴了 Google 和 Apple 的思路：如果当地卫生部门接入，阳性者可以拿到一个短期有效的验证码，输入后就是"已验证阳性"。没有验证码也可以自报，但那只是"未验证"。 ## 为什么说这套思路不只对新冠有用 Lex 说，2020年整年他最失望的，是除了做疫苗的生物学家，几乎所有机构都表现得一团糟。而更让他担心的是：如果下一次来的是致死率高得多的病毒，我们怎么办？ 罗博深的判断是，无论病毒多凶、有没有疫苗，这套"按关系层数预警"的信息机制都有用。因为现实很可能是每年都要补打新疫苗，而对世界上负担不起疫苗的地区来说，其他手段就更重要。 他举了一个更细的例子。假设有一种病，R0（基本传染数）刚好在1附近徘徊，一部分人因为生活所迫必须出门，另一部分人可以选择躲起来。只要让能躲的人自愿躲起来，把总体 R0 压到1以下，疫情就不会爆发。关键就在于给每个人足够的信息，让他自己决定风险偏好，强迫谁反而是下策。有人愿意冒险，有人愿意保守，加总起来的结果，可能恰好把病毒摁住。 这也解释了为什么 Novid 和过去的接触追踪 App 在用户价值上有本质区别。装一个传统的接触追踪 App，对你自己的感染概率几乎没有影响，它只在你暴露之后才通知你，好让你保护别人。这是纯粹的利他，动机很弱。Novid 提供的是对你自己有用的信息，动机很强。 > Novid 从不想要求你去隔离。它的原则是：如果有危险在靠近，告诉你，让你自己决定要不要保护自己。（罗博深） 他说现在最重要的工作，是和各地的公共卫生研究者建立合作，做真实的试点部署。因为一个数学家不该跳出来说"这套东西一定管用"。他带来的是网络理论和技术，缺的是流行病学和公共卫生的专业知识。他特别提到，菲律宾的国情和美国不同，这种事必须和当地研究者一起做。有意愿的研究者可以通过 novid.org 联系他们。 ## 如果数学不是答案，那什么才是？ 聊到最后，Lex 问了一个更大的问题：你觉得生命的意义是什么？ 他的回答有点奇怪，但很诚实。他说他给自己设过一个分数：在我不在了以后，我做过的事，还能影响多少"人年"。不要求署他的名字，只问这件事有没有继续起作用。 后来他调整过这个指标。因为他发现了一个更简单的解一元二次方程的方法，比所有教科书上的都容易。这个方法有可能被写进课本，一旦写进去，被替换的概率就很小。所以那个分数可能已经不是有限的了。 但他也说，这个指标本身没那么重要，重要的是背后的态度：他想做的是能比自己活得更久的事。就像人们今天还在谈牛顿，原因在于他发现了那些东西，跟牛顿这个人本身的关系其实不大。 > 人类可能只是肉做的载体，短暂地携带一些想法。真正长久的是那些想法本身。我们借来一堆想法，偶尔发明一个新的，那个新的可能就自己活下去了。（罗博深） 这和他给年轻人的建议是一体的。第一，把发明当成核心技能，别停留在模仿上。很多人学一件事的方式是看别人做一遍，然后换不同输入重复很多遍，这里面没有发明。第二，想清楚你做的事情够不够大。他提到自己的博士导师 Benny Sudakov 教给他的一件事：选那些"万一做成了会真正重要"的问题。他的另一位朋友 Jacob Fox 则总在问：就算你证出来了，我们从中学到了什么可以拿到别处用的东西？ 罗博深说，他做事不按"成功还是失败"来判断。如果 Novid 整个项目失败了，他会觉得难受吗？不会，那是个极难的问题。但如果不跳进去试，他会后悔。这就是他的行事方式：不怕失败，只怕没给自己那个机会。 ## 你能带走的东西 读完这期访谈，如果想做点什么，可以从下面几条开始。 - 找一道真正不会做的题，中学生的数学竞赛题就行（MathCounts、mathleague.org、AMC 8/10/12 都能搜到往届题目），给自己留出至少十分钟，不许翻答案，只许自己想。重点在于体验一次"从不会到会"的过程，做不做得出来反而是次要的。 - 每天留出一段固定的思考时间，十分钟到半小时都行，挑一个和你工作无关的问题，不看任何资料，纯粹用自己的常识和逻辑推一遍。罗博深管这叫"锻炼思考的肌肉"，和数学能力一样，它是练出来的。 - 如果你在学某个东西，别只看别人怎么做，试着自己从零推一遍。读教科书时先看定理陈述和证明长度，然后合上书自己重证一次，这是罗博深亲测有效的读数学书的方法。 - 如果你是公共卫生领域的研究者，或者你认识当地卫生部门的人，可以了解一下 novid.org。这套方法的验证、试点和推广，正缺流行病学和公共卫生的合作伙伴。 - 做长期选择时，问自己两个问题：这件事要求我发明，还是只要求我模仿？如果它做成了，会不会真的重要？两个都是"是"，就值得投入，哪怕要打一场持续好几年的仗。