第15章 省赛第一场（1 / 2）
请关闭浏览器的阅读/畅读/小说模式并且关闭广告屏蔽过滤功能，避免出现内容无法显示或者段落错乱。
此时的徐辰，确实遇到了麻烦。
【这个问题，有点棘手。】
他把陈老师给的竞赛资料在脑子里过了一遍，很确定，没有讲过这类问题的解题技巧。
陈老师的资料也是托关系从别的学校要来的，都是些常规的竞赛知识点。对于安城三中大部分学生来说，已经完全够用了，再深的东西，教了也学不会。
所以，徐辰现在只有一个大概的方向，但缺少趁手的数学工具。
他停下笔，开始思考。
【要证明存在一种“好”的着色方案，可以反过来想，证明“所有方案都不好”的概率小于1。】
【一个“不好”的方案，就是指至少有一条边的两个端点颜色相同。】
他想到了概率论里最基础的工具——联合界。
【假设A_i是第i条边颜色相同的事件，那么P(A_i)=1
k。如果图里有条边，所有坏事件的概率加起来就是
k。】
笔尖在草稿纸上划了几行，徐辰又停下了。
【不行。的最大值能到Nd
2，这样算出来的概率和很可能会大于1。联合界这个方法太粗糙了，行不通。】
他轻轻划掉了刚写的几行字。
徐辰闭上眼睛，屏蔽了周围的杂音，脑子里只剩下那张由点和线构成的抽象的图。
【这些“坏事件”A_i之间，不是完全独立的。一条边出问题，会影响到和它共用一个顶点的其他边……但是，这种影响是局部的。】
“局部”！
这个词像钥匙一样，打开了他脑中的一扇门。
徐辰猛地睁开眼，目光里透着一股专注。
【对，一个事件A_i，只和少数跟它“相邻”的事件有关。一条边，最多只和2(d-1)条其他边共用顶点。它的影响范围是有限的。】
【如果能找到一个方法，精确地描述这种“有限影响”，是不是就能把那个大于1的概率和给降下来？】
他没学过什么洛瓦兹局部引理。
他的世界里，没有现成的公式可以套。
他要做的，是从最基本的概率公理出发，自已动手，搭一座通往答案的桥。
他的笔又动了。
这一次，不再是试探，而是带着明确的方向进行推演。
他开始尝试构建一个更精细的概率不等式。
【假设，给每个坏事件A_i，都分配一个在(0，1)之间的权重x_i。如果能证明，每个事件A_i发生的概率，都小于一个由它自已和它所有“邻居”的权重共同决定的数值……】
这个想法很大胆，推导过程也极其复杂。
P(A_i)≤x_i*Π_{j与i相关}(1-x_j)
当这个不等式被他写在草稿纸上时，他感觉自已抓住了问题的关键。
接下来，就是海量的计算和放缩。草稿纸一张接一张地被写满，上面的符号和逻辑箭头，密密麻麻。
【计算量太大了，脑子有点跟不上了。】
徐辰看了看时间，还剩30分钟，时间有点紧。
【对了，专注胶囊！】
他想起了系统新手任务奖励的5颗专注胶囊。
他快速权衡了一下利弊。这道题如果卡在这里，省一大概率就悬了。而一旦失去省一这个敲门砖，通往CMO的资格就会断送，靠竞赛成绩提前保送顶尖大学的计划也将不得不推迟整整一年。
一年的时间，这无疑是巨大的时间成本浪费。
想通了这一点，徐辰没有丝毫犹豫。
【系统，使用专注胶囊。】
一瞬间，徐辰感觉大脑变得异常清晰和冷静，外界的一切干扰都消失了，全部的注意力都集中在了眼前的题目上。
他的计算速度和思维效率，陡然提升。
5分钟……
10分钟……
15分钟……
汗水从额头渗出，滑过脸颊，他却毫无察觉。
当第五张草稿纸写满时，那组复杂的不等式，终于被他整理成了一个简洁而清晰的形态。
若存在x_i∈(0，1)，使得对所有i，都有P(A_i)≤x_i*Π_{j∈Γ(i)}(1-x_j)成立，则P(∩A_i^c)＞0。
他利用题目给的条件e(d+1)≤k，巧妙地构造出了一个统一的权重x=1
↑返回顶部↑