RT,同学口胡的问题。
A 画地图,B 染色。A 的目标是尽快使地图上出现 nnn 种颜色,B 的目标则是尽量延长这个时间。A 每次可以画一条简单曲线,并围出一个封闭图形(可能不太严格,没学过这方面内容)。B 则负责给这个图形染色,要求不能与相邻的图形颜色相同。在 A 与 B 都采用最优策略时,最少几步可以达到 A 的目标?
如果给每个颜色都编号,目前看来 B 染相邻图形颜色的 mex 一定是最优的,但是我不会证……而且看起来即使证明/证伪了也离解决原问题很远。
n=5n=5n=5 的情况: