亲,欢迎光临读趣网!
错缺断章、加书:站内短信
后台有人,会尽快回复!
  • 主题模式:

  • 字体大小:

    -

    18

    +
  • 恢复默认

磁性几何魔方。

这题的题面非常漂亮,配图甚至颇有趣味。

描述了一种可以通过磁性节点随意拼接的多面体模块,要求求出在特定数量下,整个结构两端能达到的最大直线距离。

很容易就让人误以为自己是在做一款益智玩具的拼图游戏。

白板上,尹航已经画了十二种复杂的拼接形状。

每一种构型都充满了机械美感,计算出的极端点距离列在一旁,姚思雨还在下面补了几个奇异的边界情况。

很显然,两人已经在这道题里走得很深,走得很远,并不是不会做。

问题是,走得太远,也走得太散。

像是在一片没有尽头的森林里开了十二条路,却不知道哪一条才是生路。

“我们现在最大的问题是构型太多了,如果纯靠穷举,我能枚举出一堆,但没法证明,我不知道有没有漏掉一种比现在更极端的诡异拼法。”

尹航指着白板上那些密密麻麻的图形说,语气有些烦躁。

姚思雨在旁边心有戚戚地点头:“通过刚才的计算,我其实能猜到答案大概落在哪个范围。但我的证明写得不干净,总觉得如果阅卷人挑刺,随便给出一个我没考虑到的拓扑结构,我的逻辑链就断了。”

听两人解释罢,江临站到白板面前。

先看那些复杂的构型图,再看旁边列出的距离表,最后,他的视线停留在尹航划掉的那几行试图用对称群来分类的推导上。

尹航有一条路线,是想把旋转翻折之后等价的构型先并掉,用对称性减少枚举。

方向很敏锐,但等价类并不等于上界。

它只能减少要看的图,不能告诉你最远的端点一定在哪里。

姚思雨走的另一条路线,是按模块之间的连接面面积来分类。

也没有错。

但分类一多,证明过程就会变成一个充斥着无数分类讨论的泥潭,结果是自己也被绕进去了。

江临从白板槽里拿起一根蓝色的马克笔,在白板最上方的一大块空白处,写了两个字。

上界。

尹航皱了皱眉。

因为在他看来,这显然是一句废话。

“我们当然知道要求上界,问题是这个上界你怎么抓,你怎么能保证一个统一的公式能罩住所有乱七八糟的拼法?”

江临转过头,看着尹航,平静地说道:“你不知道怎么抓,是因为你们从一开始,就把这道题当成空间拼图在看。”

此话一出,姚思雨猛地抬头,盯着江临。

江临用手里的蓝色马克笔在白板上点了几个点,然后用线将它们连起来。

一个连接图+有效位移的模型,取代了之前那些繁复的立体构型图。

“几何不能丢。”他说,“但不能一开始就被几何图形牵着走。先把每个模块允许的连接位姿,压成有限几种有效位移,再把模块之间的连接关系抽成图。”

说着,他在其中一条路径上画了一个箭头。

“真正要抓的是任意合法拼接里,两个端点之间的欧氏距离,最多能从这些连接路径里榨出多少。”

尹航皱眉:“所以不是枚举形状,而是先证明任何构型都不可能超过某条简单链的展开长度?”

“对。”江临点头,“图给出路径结构,几何约束给出每一步最多能贡献的距离。两者合在一起,才是上界。”

姚思雨盯着那条链状结构,顺着说道:“如果上界被这条链卡死,那我们只需要再构造一个具体拼法,证明它刚好能达到这个上界。”

“对。”

江临在链的旁边画出一个近似拉直到极限的极端构型。

图画得瑞安潦草,但关键端点、连接面和相对朝向交代得一清二楚。

“先用连接图和几何约束证明上界,再用极端构型给出取等构造。一拉一推,这题就闭合了。”

“等一下。”

尹航皱着眉头走近白板,用黑色马克笔在江临的构型旁边补了一条旋转虚线。

“这里如果沿这条轴转一次,会不会利用空间对角线让端点更远?”

江临扫了一眼,摇头说:“不会。”

“为什么?”

“因为这一步旋转只改变方向,不增加有效位移的模长。端点距离的投影已经被前面的连接约束卡住了。你能换坐标系里的朝向,但不能凭空增加那一节贡献的长度。”

尹航还是有些心有不甘,又指向原来的海星状构型,说:“那这种非链状分支呢,两个分支端点之间会不会更长?”

“分支端点之间的距离,必须经过公共连接节点分解。三角不等式先给自然上界:d(A,b)≤d(A,c)+d(c,b)d(A,b)\le d(A,c)+d(c,b)d(A,b)≤d(A,c)+d(c,b)。关键是取等条件。在这道题的连接约束下,两条分支不能同时沿同一直线完全展开。你拉直一条,另一条的有效投影就会被折掉。”

江临用笔在公共连接节点上点了两下。

“所以分支结构最多逼近同等节数的链式上界,不可能超过它。”

姚思雨听到这里,终于全部明白过来。

立刻拿起笔,在自己的草稿纸上迅速补上了两行关键的图论转化。

叹道:“所以我们之前的枚举,就像是拿着相机,在给所有可能的雕塑疯狂拍照,试图找出一张看起来最高大的。”

江临点点头,放下马克笔,说:“数学不需要我们拍完所有照片,只需要我们证明,最高的那张照片,它的天花板在哪里,然后证明有人能摸到那个天花板就行了。”

尹航看着白板,沉默了足足有半分钟。

最后,他拿起黑板擦,果断擦掉自己原先画的十二种构型和旁边那长长的距离表。

然后在江临画出的连接图旁边打了一个勾。

“行。”

尹航的语气里的那种烦躁一扫而空。

“这个上界,闭合了。”

一直坐在窗边没参与进来的孟澈,此时默默地调整了一下坐姿。

他没参赛,也不打算过度参与这道题的计算细节。

但他从这段对话里,听出了熟悉的味道。

江临刚才做的第一件事,是剥离。

把形状,三维,磁性这些具有极强视觉干扰的物理外壳从问题里剥掉,然后换成图结构,节点和上界。

这种处理问题的方式,太成熟了。

像什么呢?

孟澈看着江临削瘦的背影。

它更像一个老练的实验物理学家,在面对极其复杂的系统误差时,先不急着调仪器,而是先建误差模型,把仪器误差、读数涨落和真实物理量一层一层地切分开。

……

第二张题面,是拆盲盒。

姚思雨叹了口气,把自己的草稿纸推了过来。

上面密密麻麻写了半页纸的公式。

“这题我一开始按具体的集合状态写了递推。”

并没有错,只是太重了。

盲盒里有若干种不同卡片。

每拿到一种新卡,拥有的集合状态就发生改变。

如果按已经拥有的具体集合去写状态空间,状态数量会呈指数级增长,很快就会变成一个灾难性的马尔可夫链转移矩阵,根本没法算,更没法手写证明。

“我也卡在这了。”

尹航在旁边插话道。

“我明明知道它在宏观上能压缩,因为全收集的期望最终肯定收敛,但就是找不到最干净的压法。把每一步抽到什么卡的历史都背在身上走,实在太蠢了。”

江临看了一眼姚思雨的草稿纸,没有去改她的公式。

直接在空白处写下一行字。

还缺几种。

姚思雨看着那四个字,怔了一下:“你一点都不关心当前手里具体缺的是哪几种卡?”

“不关心。”

江临回答得很干脆。

“题目的设定里,每一种盲盒被抽到的概率是均匀分布的,这意味着卡片本身是高度对称的。”

江临用笔在盲盒两个字底下画了条线。

“题目让你求的是集齐所有卡片所需时间的期望值,不是让你描绘收集过程中每一个具体集合长什么样。A,b,c和b,c,d在本质上是等价的。”

尹航的眼睛瞬间亮起,猛地一拍大腿,叫道:“我靠,所以不用管具体卡,直接按数量阶段来分解?从缺k种卡,转移到缺k-1种卡?”

“嗯。”江临点头。

姚思雨低头,在纸上飞快地算了两步,之前的复杂矩阵被瞬间降维。

“既然概率均匀,那在缺k种卡的状态下,抽到一张新卡的概率就是 p_k=k/N。所以在这个阶段停留的等待时间,就是一个参数为p_k的几何分布。而它的期望……”

“几何分布的期望是概率的倒数。”江临接上了她的话,“所以这一阶段的期望步数就是N/k。”

江临说到这里,看了一眼姚思雨因为激动而写得越来越快的笔尖,适时地浇了一盆。

“不过在提交的时候还是不能直接从原题跳到这一步。”

姚思雨停下笔,有些不明所以地抬头看他。

“先花半页纸,严格说明为什么你的马尔可夫状态可以从2^N压缩到 N,也就是所谓的等价类划分。否则阅卷教授会觉得你在偷换概念,用一个简单的模型套一个复杂的题。”

姚思雨认真地点头,准备继续往下写。

写到一半,像是想到了什么反例,眉头皱了起来。

“等等,如果不同盲盒的抽取概率不均匀呢?比如有隐藏款,概率只有1%,其他是10%,那这个数量状态压缩就不成立了,缺A和缺隐藏款的期望完全不一样。”

“是的,所以你要在证明的开头,先浓墨重彩地写明对称性条件。题目给定的均匀抽取不是一句为了让题面好看的装饰语,我们进行状态压缩,真正要算的是N个阶段期望。”

尹航听到这里,忍不住吐槽了一句:“你做题的时候,脑子里还一直想着阅卷人啊?”

“想着复核。”江临认为自己应该纠正他的用词。

“数学竞赛也叫复核?”

“只要是需要人去验证的逻辑链,就叫复核。”江临看着尹航,“证明写出来,就是给别人复核的。如果你的解答只有你自己懂,那不叫数学证明,那叫私人日记。”

一旁的孟澈听得是直点头。

复核这个词,他太熟了。

老板在组会上不知道骂过他们多少次类似的话。

“科研不是你自己觉得数据好看就行。你要把你的实验条件,你的误差分析,你的数据处理流程清清楚楚地写在paper里,让大洋彼岸另一个素不相识的同行,能在他自己的实验室里,在合理的时间内把你的结果复核出来。不能复核的东西,就是伪科学。”

数学竞赛显然也是一样的逻辑。

会做,只是第一步,最多算自己通过了。

能写成让挑剔的评审在有限时间内稳定复核的证明,才算真正完成。

已经想通透了的姚思雨,把草稿纸上那一大片旧的递推公式用力划掉,长舒了一口气,整个人都放松了下来。

“太好了,这样就干净多了。我之前的问题是历史包袱太重,跟背着一座山似的。”

江临点点头:“状态里当然只需保留影响未来的最小信息,因为多一丝都是累赘。”

“这不就是最小充分状态嘛。”尹航喃喃自语。

最小充分状态?

一旁笑眯眯的孟澈忽然捕捉到了关键词。

先找状态,再找边界。

最后判断,哪些信息是必须保留的承重墙,哪些信息只是花里胡哨的壁纸和噪声。

这是一种拆解世间一切复杂系统的底层方法论。

不是一个能在单纯的数学竞赛题集里学到的漂亮说法。

可比会做题的天才厉害多了。

联想到这位才读高三的小师弟,一出山就帮大家解决了数据漂移的问题。

孟澈脑子里冒出一个不太严肃的念头。

这不就是先天科研圣体吗?