倒计时四天,林一先把草稿上的“起跑、加速、途中跑、冲线”全部划掉。
四个方框还在,箭头也在。没有跑道词语后,它们立刻变得空洞:为什么要分四段,哪个对象进哪一段,段与段之间凭什么不重叠,纸上一个字都没证明。
罗建国在视频里说:“现在念你的结论。”
“像百米一样,每个对象经过唯一阶段——”
“跑道删干净。”
林一停了停:“把所有对象按特征分层,每个对象进入唯一一层。”
“特征是什么?”
“还没定义。”
“那你只有一句愿望。”
题目把`n`个顶点按顺时针排在一个圆周上,研究这些顶点之间的无向边。目标是按循环距离把全部边分层,并说明每层满足给定的局部度数限制:一般距离层中,每个顶点与顺、逆两个方向的对应点相连;偶数`n`的半圈距离层则只能形成一组对边匹配。
跑道分段让林一想到“每条边应该有自己的归属”,可归属不能写成感觉。
他先给顶点编号:
`0,1,...,n-1`,下标按模`n`计算。
对一条无向边`{i,j}`,两个方向的循环差分别是:
`(j-i) mod n`与`(i-j) mod n`。
两者相加为`n`。林一取其中较小者,定义最短循环距离:
`d({i,j}) = min((j-i) mod n, (i-j) mod n)`。
距离取值落在`1`到`?n/2?`之间。于是第`d`层暂定为所有最短循环距离等于`d`的无向边。
“覆盖呢?”罗建国问。
“任意两点不同,所以两个方向差都不为零;取较小者,一定落在这个范围,每条边至少进入一层。”
“唯一呢?”
“最小值唯一。”
话刚出口,罗建国就让他取`n=8`,看边`{1,5}`。
顺时针从1到5,距离4;从5到1,距离也是4。两个方向差相等。
林一盯着那个`min`:“最小值的数值唯一,但实现方向不唯一。”
“你要分的是无向边,还是带方向的走法?”
“无向边。”
“那数值归属可以唯一,生成方式未必。继续。”
林一原先打算把第`d`层写成:
`E_d = {{i,i+d}: i=0,1,...,n-1}`。
当`d<n/2`时,这个写法没有问题。若同一条无向边被`i`和`k`两次生成,就要有`{i,i+d}={k,k+d}`。除了`i=k`,另一种可能是`i=k+d`且`i+d=k (mod n)`,从而`2d≡0 (mod n)`。在`0<d<n/2`时不可能成立。
所以一般距离层中,每条边只生成一次。每个顶点分别连向`i+d`和`i-d`,局部度数为2。
可当`n`为偶数、`d=n/2`时,`2d≡0 (mod n)`成立。
`{i,i+n/2}`与`{i+n/2,i}`是同一条无向边。若`i`仍从0取到`n-1`,每条半圈边会被生成两次。
小规模样例里那次重复终于有了来源。
不是第三阶段和第四阶段“接得不好”,而是他没有处理最短距离两个方向相等的边界。
林一把半圈层单独定义:
`E_{n/2} = {{i,i+n/2}: i=0,1,...,n/2-1}`。
只取前一半编号,每条对边出现一次,每个顶点恰好出现于一条边,形成匹配。奇数`n`没有这个距离层,自然不需要特判。
林一把`n=8`完整列了一遍。
距离1层是`{0,1},{1,2},...,{7,0}`,八条边围成一个圈;距离4层若让起点取遍0到7,就会同时出现`{0,4}`和`{4,0}`、`{1,5}`和`{5,1}`。限制起点为0到3后,只剩四条互不重复的对边。
他原本还准备写“一般距离层都形成一个大圈”,列到距离2时又停住。`n=8、d=2`得到的是`0-2-4-6-0`和`1-3-5-7-1`两个圈,不是一个圈。若`gcd(n,d)>1`,距离层会分解成若干个循环;题目只要求每个顶点在该层度数为2,并不要求整层连通。
又一个看上去顺手的漂亮结论被删掉。严格证明不仅要补缺口,也要拒绝声称题目没有要求、自己也没有证明的性质。
“现在再说覆盖和唯一。”罗建国说。
林一从头写。
对任意无向边,最短循环距离给出一个层编号,因此覆盖全部边;不同距离层不可能共享同一条边,因为同一无向边的最短循环距离是确定数值。固定层内,`d<n/2`时有`n`不整除`2d`,即`2d?0 (mod n)`,因此排除反向双计;偶数半圈层限制起点范围,单独消除重复。
最后再核局部限制:一般层每个顶点度数2,半圈层每个顶点度数1。
覆盖、跨层唯一、层内唯一、偶数边界,四项终于都在纸上。
林一又用总边数做了一次核验。
当顶点数为奇数时,最短距离一共有二分之“顶点数减一”层,每一层都含有与顶点数相同数量的边,合计正好等于完全图的边数。当顶点数为偶数时,前面各个一般距离层仍各含同样多的边,最后的半圈层只有一半数量;两部分相加,也正好等于全部无向边的总数。
数目对上,至少说明没有哪一大批边凭空消失。
“能不能靠这个直接证明不重不漏?”罗建国问。
林一想了想:“不能。总数一样,也可能一边重复、一边遗漏,刚好抵消。”
“所以计数放最后。”
先用映射证明每条边都有归属,再证明不同层和同一层内部都不重复,最后才用总数做交叉检查。若把总边数相等放在前面,它只能给出一个看上去完整的结果,不能替代逐对象证明。
林一把“边数相等,所以恰好覆盖”从草稿里划掉,改成“边数核验与前述覆盖、唯一结论一致”。组合卡上又多了一个以后能复用的警告:全局计数正确,不保证局部映射正确。
林一回头看最初那四个跑道方框。它们帮他想到“对象要有唯一阶段”,却没有告诉他循环距离该怎么定义,更没有提醒`n/2`会让两个方向重合。
他把四个方框也划掉,只留一句来源说明:
类比只用于找到“归属映射”入口;证明从模`n`差值开始。
“这句可以留?”他问。
“可以放错因卡,别放正式证明。”罗建国说。
“为什么?”
“阅卷老师不需要知道你在哪条跑道上想出来的,只需要知道每条边为什么只出现一次。”
沈砚这时在线上共享里看完草稿,发来一句:“半圈层刚才漏了?”
“漏了。”
“那你还敢说分段。”
“入口对了。”
“入口不计分。”
“补完计。”
沈砚没有反驳,只把`2d≡0 (mod n)`那一行圈了出来。他熟悉这种错误:分类标准看似完整,边界处两个类别却撞在一起。过去他会因为被追赶而中途换标准,现在反而最先盯住标准有没有重叠。
“你刚才还想说每层都是一个圈。”沈砚又指出。
“题目只要局部度数。”
“那就别送阅卷老师一个可以扣你的额外错误。”
林一把“连成一个大圈”彻底删掉。证明里少一句未经证明的漂亮性质,不会让答案变弱;反而让真正需要的覆盖、唯一和度数限制更清楚。
组合卡翻到背面。
上面最终只写四行:
对象:圆周顶点间的无向边。
映射:最短循环距离。
证明:覆盖、跨层唯一、层内唯一。
边界:偶数`n`的半圈层单列。
卡片完成时,倒计时还剩三天。林一没有打开考后文件夹里的冲刺拓展包,也没有再找一题相似的循环构造。他把正式证明誊清,原来的跑道草图夹在错因卡后面,作为“入口曾经有用、结论仍需重做”的证据。
下午,李志明通知重点备赛组最后一套模拟卷已经到校。
这一次仍统一计时、统一收卷,但学校不在结束后立即公开内部排名。只回传个人卷面、时间分配和四张地基卡对应的错因,避免最后三天再用名次刺激临时加量。
林一问:“分数呢?”
“会给。”
“排名呢?”
“封存到正式联赛后。”
“那能不能只告诉我跟上次差多少?”
“个人分数和错因会给,别人的不横向比较。”李志明说,“你要是拿上次十八人的分数自己估位,排名封存就只剩形式。”
林一确实已经在想:上次第五落在哪个分数段,这次多拿几分大概能到哪里。李志明把这条路也堵上后,他在最后模拟任务纸顶端写了一句:只与四张卡核对,不自行换算名次。
个人分数出来以后,他也只能比较自己的旧卷:哪道题用时变长,哪张卡对应的错误没有再犯,哪一步仍需在正式考试前停止扩张。即使比上次多分,也不能拿别人的旧分数线拼出一个“可能第四”;即使少分,也不能据此临时拆封拓展包。
这比直接不公布分数更难。分数还在,估算排名的材料也大半在,真正被封存的是他用名次改变计划的权限。
内部第五不会在最后一卷里立刻升成第四,也不会掉成第八。最后一次模拟只回答一个问题:那些已经写到卡片上的错误,会不会在三小时压力下重新出现。
牛皮纸袋再次进了文件柜。
跑道类比已经从证明里删掉。
明天的卷面,没有任何比喻可以替他多拿一行分。