姚思雨听到这里,终于全部明白过来。
立刻拿起笔,在自己的草稿纸上迅速补上了两行关键的图论转化。
叹道:“所以我们之前的枚举,就象是拿着相机,在给所有可能的雕塑疯狂拍照,试图找出一张看起来最高大的。”
江临点点头,放下马克笔,说:“数学不需要我们拍完所有照片,只需要我们证明,最高的那张照片,它的天花板在哪里,然后证明有人能摸到那个天花板就行了。”
尹航看着白板,沉默了足足有半分钟。
最后,他拿起黑板擦,果断擦掉自己原先画的十二种构型和旁边那长长的距离表。
然后在江临画出的连接图旁边打了一个勾。
“行。”
尹航的语气里的那种烦躁一扫而空。
“这个上界,闭合了。”
一直坐在窗边没参与进来的孟澈,此时默默地调整了一下坐姿。
他没参赛,也不打算过度参与这道题的计算细节。
但他从这段对话里,听出了熟悉的味道。
江临刚才做的第一件事,是剥离。
把型状,三维,磁性这些具有极强视觉干扰的物理外壳从问题里剥掉,然后换成图结构,节点和上界。
这种处理问题的方式,太成熟了。
象什么呢?
孟澈看着江临削瘦的背影。
它更象一个老练的实验物理学家,在面对极其复杂的系统误差时,先不急着调仪器,而是先建误差模型,把仪器误差、读数涨落和真实物理量一层一层地切分开。
……
第二张题面,是拆盲盒。
姚思雨叹了口气,把自己的草稿纸推了过来。
上面密密麻麻写了半页纸的公式。
“这题我一开始按具体的集合状态写了递推。”
并没有错,只是太重了。
盲盒里有若干种不同卡片。
每拿到一种新卡,拥有的集合状态就发生改变。
如果按已经拥有的具体集合去写状态空间,状态数量会呈指数级增长,很快就会变成一个灾难性的马尔可夫链转移矩阵,根本没法算,更没法手写证明。
“我也卡在这了。”
尹航在旁边插话道。
“我明明知道它在宏观上能压缩,因为全收集的期望最终肯定收敛,但就是找不到最干净的压法。把每一步抽到什么卡的历史都背在身上走,实在太蠢了。”
江临看了一眼姚思雨的草稿纸,没有去改她的公式。
直接在空白处写下一行字。
还缺几种。
姚思雨看着那四个字,怔了一下:“你一点都不关心当前手里具体缺的是哪几种卡?”
“不关心。”
江临回答得很干脆。
“题目的设置里,每一种盲盒被抽到的概率是均匀分布的,这意味着卡片本身是高度对称的。”
江临用笔在盲盒两个字底下画了条线。
“题目让你求的是集齐所有卡片所需时间的期望值,不是让你描绘收集过程中每一个具体集合长什么样。A,B,C和B,C,D在本质上是等价的。”
尹航的眼睛瞬间亮起,猛地一拍大腿,叫道:“我靠,所以不用管具体卡,直接按数量阶段来分解?从缺k种卡,转移到缺k-1种卡?”
“恩。”江临点头。
姚思雨低头,在纸上飞快地算了两步,之前的复杂矩阵被瞬间降维。
“既然概率均匀,那在缺k。所以在。而它的期望……”
“几何分布的期望是概率的倒数。”江临接上
江临说到这里,看了一眼姚思雨因为激动而写得越来越快的笔尖,适时地浇了一盆。
“不过在提交的时候还是不能直接从原题跳到这一步。”
姚思雨停下笔,有些不明所以地抬头看他。
“先花半页纸。否则阅卷教授会觉得你在偷换概念,用一个简单的模型套一个复杂的题。”
姚思雨认真地点头,准备继续往下写。
写到一半,象是想到了什么反例,眉头皱了起来。
“等等,如果不同盲盒的抽取概率不均匀呢?
“是的,所以你要在证明的开头,先浓墨重彩地写明对称性条件。题目给定的均匀抽取不是一句为了让题面好看的装饰语,我们进行状态压缩,真正要算的是N个阶段期望。”
尹航听到这里,忍不住吐槽了一句:“你做题的时候,脑子里还一直想着阅卷人啊?”
“想着复核。”江临认为自己应该纠正他的用词。