晚上六点四十,林一在第一行写下:
`取满足条件的最小下标j。`
章闻从他身后走过,没有停。
许竞川停了。
“哪个集合里的最小?”
“所有满足三项约束、且还没覆盖的状态。”
“集合非空?”
林一指向黄色方框:“正在证。”
许竞川没有继续问,把那一行抄到“未证”页,回自己座位。
十分钟后,林一写了三种尝试。
按第一坐标最小取点,不能保证第二坐标下降。
按第二坐标最大取点,可能超过总差阈值`m`。
按两坐标差的字典序取极值,极值存在,却仍可能不在当前状态`x_i`的可选集合`F(x_i)`里。
极值法只能保证“从未覆盖集合里挑得出一个点”。
它没有保证当前点连得到。
七点零五,林一回读题面。
题面真正给出的全局条件是:对任何包含初始状态、但尚未覆盖全部状态的集合`A`,都存在`x∈A`与`y?A`,使`y∈F(x)`。
这是一个割条件。
它保证已覆盖集合有边跨出去。
却没有保证跨出边的起点恰好是他刚走到的`x_i`。
三点小例子很快画出来。
初始点`a`可到`b`和`c`,`b`没有通向未覆盖点的合法边,`c`却能到`d`。若第一步选`b`,当前点路线立即卡住;此时已覆盖集合`{a,b}`仍有`a→c`跨出去,题设没有被违反。
`U_i>0`。
`F(b)nw_i=?`。
黄色方框里的命题是假的。
林一盯着那两个式子。
不是证明太难。
是他要证明的东西根本不成立。
“找到了?”唐予宁问。
“找到反例。”
“给我看。”
她走过来,先检查四个点满足题面割条件,再沿林一选择顺序走到`b`。第三步无路。
红笔直接落在正式解答第一行。
“从这里退。”
“后面的`U`下降是对的。”林一说。
“条件成立时对。”
“停止上界也是对的。”
“建立在每一步走得下去。”
“三项约束定义没错。”
“可你选错了维护对象。”
唐予宁每说一句,红线就往下延一段。
当前状态、当前后继、连续路线、每步从`F(x_i)`选点,全部依赖那条假的非空命题。最后只剩集合定义和一个条件式下降引理可以拆出来另存。
整份解答,不能在第一行旁边补一句话继续用。
七点十二,章闻走回桌边。
唐予宁把反例递过去。
章闻看完,只问林一:“题目要你构造什么?”
“覆盖顺序。每个新状态只需有一个此前状态作为合法前驱。”
“要求相邻两项之间都有边吗?”
“没有。”
“那你为什么维护当前点?”
林一张了张嘴。
因为接力故事。
一棒接一棒,天然把注意力锁在刚接到棒的人身上。即使“接力区”三个字已经从正式稿删除,故事留下的对象选择仍藏在证明骨架里。
“我把覆盖顺序误写成一条路径。”
章闻在整页右上角写:
`退回重写。`
不是“补存在性”。
不是“第一行扣分”。
是整份退回。
教室里几个人抬头。许竞川从“未证”页撕下一张空白纸,放到林一右手边。
“已证页要不要留?”他问。
“留两个定义和条件下降引理。”
“其他?”
“作废。”
“那就重写。”
林一把三页稿纸从订书钉里取出来。
纸没有撕。
他用一条从右上到左下的斜线贯穿三页,每页写同一句:
`错误对象:当前点。`
第一条斜线落下时,胸口发闷。
第二条落下时,后排有人倒吸气。
第三条落下,唐予宁狠狠干拍了一下桌子。
“重来!”
许竞川也把拳头砸进掌心:“换对象!”
叶峥从另一组抬头:“到点也得停!”
教室里先笑,随后十几个人一起喊:
“换对象!到点停!”
林一的笔在空白纸上落下。
新对象不是当前状态,而是已覆盖集合`A_i`。
初始时`A_0={s}`。
若`A_i`尚未覆盖全部状态,题设割条件保证存在`x∈A_i`、`y?A_i`且`y∈F(x)`。
选择任意一条这样的前沿边,把`y`加入:
`A_{i+1}=A_iu{y}`。
同时记录`x`为`y`的前驱。
每次集合大小增加一,未覆盖数减少一。有限步后`A`覆盖全部状态;按加入次序排列,每个新状态都有一个更早加入的合法前驱,正好满足题目,而无需相邻两项彼此可达。
林一又把“任意一条”圈住。
旧证明里,选择`b`会把当前点送进死路;新证明允许第一步仍选`b`,因为下一步的跨边可以从整个`A_i`中任意一点发出。选择不再要求预测未来哪一个点能继续走。
他给每个新点`y`记录加入时的父点`p(y)=x`。由于`x∈A_i`而`y?A_i`,父点的加入时刻严格早于子点;割条件又保证`y∈F(x)`,所以每个非初始点都有一个符合三项约束的更早前驱。
若题目只要求这样的覆盖顺序,父点不必正好是序列前一项。林一在“前驱”和“前一项”之间画了第二条竖线。
接力故事曾把这两个词焊成一个。
现在它们终于分开。
许竞川从对面问:“不同选择会不会得到不同顺序?”
“会。”
“题目要求唯一吗?”
“不要求。”
“那就别再证明唯一。”
林一删掉草稿边缘刚写出的“取字典序最小前沿边”。那条规则可以让输出确定,却不是存在性所需,继续保留只会增加一座无用的桥。
唐予宁看见他删,红笔在桌面敲了两下:“这次删得对。能任选,就别为了好看强造唯一。”
七点二十九,存在性、推进与终止第一次落在同一个对象上。
林一没有喊完成。
他先用刚才的`a,b,c,d`反例回放。
第一步若加入`b`,集合为`{a,b}`;下一步仍可用前沿边`a→c`加入`c`,再由`c→d`加入`d`。不会因当前点停在`b`而卡死。
反例从杀死旧证明,变成验证新对象。
七点三十五,S14被再次请来复述。
他没有说跑道,也没有说“顺着”。
“维护已覆盖集合。只要没覆盖完,割条件就给出一条从集合内到集合外的合法边。加入外点并记录前驱。集合每次增一,所以有限步覆盖全部。”
“缺口?”章闻问。
S14看了两遍:“需说明加入次序确实满足题目要求。已经记录前驱,且前驱更早进入,所以满足。”
章闻点头。
林一这才狠狠干握拳。
教室里桌面又响起来。
这次的爽点不是把三页补回。
是承认三页不能救,再从错误对象下面抽出一张真正能站住的新骨架。
八点,第一轮重写归档。
章闻给林一的记录不是满分。
`旧稿退回;新稿主链成立;边界与表达待次日复核。`
九点二十,全班按时停笔。
林一把三页作废稿放进许竞川的“未证”侧,没有塞进垃圾桶。
“不是我的活页。”许竞川说。
“借放一晚。”
“明早还你。”
“别替我整理。”
“不会。”
宿舍熄灯前,第二阶段第一次正式测试通知送达。
次日上午八点,四题六十分。
两道几何。
课堂重写、表达记录与第一阶段195分,都不带入这张正式卷。
林一把通知放到桌面中央。
新证明成立。
明天的图,仍要从第一条线开始。