叶思源译《圣彼得堡数学奥林匹克试题集》
哈尔滨工业大学出版社，2015
《圣彼得堡数学奥林匹克试题集》为圣彼得堡数学奥林匹克试题集，全书收录了1994～1999年的奥林匹克试题，并附有试题参考答案，由于涉及各种层次的竞赛题，因此书中题目难度波动较大，有相对简单的问题，也有相当令人费解的难题，读者不妨依个人情况自选习题解读。
2018年全俄数学奥林匹克
一道组合题的思路分析
徐州 赵力
题目 在圆周上标记出99个点, 将该圆周等分为99段弧.Petya和Vasya轮流玩以下的染色游戏. 由Petya首先开始, 在第一步, 他可以任选一个标记的点, 将其染为红色或蓝色. 此后, 每轮的玩家可以选择任意一个与已染色点相邻但还未被染色的标记点, 将其染为红色或蓝色. 如果在所有标记点都染过色后, 存在一个三顶点同色的等边三角形, 则判Vasya胜. 问Petya是否能够阻止Vasya获胜? (9年级第5题)
分析及解答 答案是Petya不能阻止Vasya获胜.
通过题目的条件, 可以获得以下一些信息及规则:
i) 确定性: 在此圆周上的99个点中, 能构成正三角形的点, 相互间距离是固定的, 均为每隔33个点选一个点.
ii) 灵活性: 染色的过程是从最初点开始, 逐渐沿两侧伸展, 最终完成对所有点的染色. 但是向两侧中的哪一侧伸展, 染什么色, 则可以由玩家自己决定.
首先, 前33个点的染色可以随意染.
对第34个点的染色成为至关重要的一步, 因为从这一步开始, 就开始处理可以和前33个点之一构成正三角形一条边的点了.
幸运的是, 这一步正好轮到Vasya染色, 这就给了他机会进行布局. 为了能获得同色正三角形, 他的策略当然是将该点(设为A)染为与之间隔33位的点(设为B)同色(不妨设为红色), 从而抢先建立正三角形一条同色的边(见图1).
图1
经过这一步后, 能够与A, B构成正三角形的第三个点X的位置也就随之确定, 恰好与A, B等距离.
Vasya的目标当然是利用ii), 尽可能地使X与A, B之间的未染色点数目(为简单叙述计, 称之为X到A, B的'距离')接近, 并且争取自己能够支配X点染色, 从而达到目的.
但是, 接下来第35步轮到Petya,他完全可能破坏Vasya的计划. Petya可以通过选择在圆周的不同方向上选点, 破坏X距A, B等'距离'的要求, 但是这一点还不算太致命,Vasya可以采用关于X对称选点染色的策略, 尽可能减少X到A, B'距离'的差别. 而最致命的是, 总共有99个点, 最后一步是Petya走, 最终染什么颜色的'核心技术'支配权不在Vasya那儿, 怎么办?
看来, 必须要有X的备胎, 建立自己的'芯'!这就需要Vasya展示自己的聪明才智了.
Vasya需要针对Petya的第35步, 选择相应的第36步, 获得一个与X有相同作用的点Y. 这个点Y需要和X相邻, 这样的话, 倒数第二步时, 至少X, Y之一还在, 并且轮到Vasya走, 完全可以我的地盘我做主, 不被釜底抽薪, 从而完成目标.
下面就来针对Petya的第35步染色, 看看Vasya如何选择相应的第36步.
Petya接下来第35步的选点(设为C)无非就是两种选择:
a) C与A相邻.
为了使X与A, B接近于等'距离',Vasya必然需要在与B相邻的位置选点(设为D), 所选的颜色应该是和与A相邻但与C不同侧的点(设为E)同色(为了醒目, 这里用蓝色表示). 这时候由D, E所确定的正三角形的第三个顶点Y也唯一确定了(图2). 而且, 令人兴奋的是, Y确实与X相邻!
图2
b) C与B相邻.
类似地, Vasya需要在与A相邻的位置选点D, 所选的颜色应该是和与B相邻但与C不同侧的点E同色. 这时候也唯一确定了与X相邻的Y, 只不过这一回, Y处于X的另一侧(图3).
图3
其实, 情况a)和b)没有本质区别. 在情况b)下, 可以认为是Vasya第34步选的点是B, 与之间隔33位的点为A, 就化归为情况a)了.
这样,Vasya就牢牢地把握住了自己的命运. 接下来的策略仅仅就是'对称'. 在XY的两侧, 与Petya对称地选点及染色, 染什么颜色无所谓.
这样, 咬牙坚持, 最坏的情况就是熬到倒数第二步Petya还没犯错, 但这时点X, Y中至少还有一个没被染色, 这就是Vasya的Game Point!
抓住机会, 搞定!
联系客服
