埃尔德什难题：最简单的问题为何可以难倒数学家

password

AI summary

type

status

date

summary

埃尔德什长期没有固定住所，带着行李在世界各地数学家家中工作。他发表了上千篇论文，合作者多达数百人，由此产生了著名的“埃尔德什数”：与他直接合作的人为1，与这些人合作的人为2，依此类推。

他最特别的能力，并不只是解题，而是判断什么问题值得被问。他会为一些问题设置奖金，金额从几十美元到数千美元不等。奖金不是市场价格，而更像他对问题难度与重要性的私人标记。

在平面上放置个点，如果两点之间距离恰好为1，就把它们连起来。问题是：最多可以有多少对单位距离？

三点摆成等边三角形时，有三条单位距离。点数增加后，局部上看似优良的排列不一定能扩展成整体最优结构。

这个问题的典型困难是：条件非常局部——只问两点距离；目标却非常整体——问所有点对中最多能出现多少。计算机能寻找大型构造，却很难替代一般性证明。

考虑一个只由和组成的无限序列：

沿任意固定步长取出：

埃尔德什猜测，无论怎样排列正负号，总能找到某些，使部分和的绝对值任意大：

这道题表面只涉及正负号，却需要同时控制所有步长。它最终在2015年由陶哲轩证明。

对每个，是否总能找到正整数，使：

例如：

大量整数已经被计算机验证，许多特殊类别也已获得证明，但一般证明仍然缺失。它提醒我们：验证再多案例，也不等于证明一个无限命题。

埃尔德什推广的概率法改变了组合数学。要证明某种对象存在，不一定要直接把它构造出来。可以随机生成对象，再证明它满足目标性质的概率大于零。只要概率不是零，就说明至少存在一个符合条件的对象。

这种思想后来广泛进入图论、编码理论、随机算法和理论计算机科学。

埃尔德什难题真正吸引人的地方，是它们揭示了一个事实：数学的深度与题目的表述复杂度并不成正比。最难的问题，有时恰好像游戏规则一样简单。