一人画地图,一人染色,最少几步能使地图上至少存在 n 种颜色?
  • 板块学术版
  • 楼主derta
  • 当前回复13
  • 已保存回复13
  • 发布时间2022/7/19 19:45
  • 上次更新2023/10/27 19:28:34
查看原帖
一人画地图,一人染色,最少几步能使地图上至少存在 n 种颜色?
225734
derta楼主2022/7/19 19:45

RT,同学口胡的问题。

A 画地图,B 染色。A 的目标是尽快使地图上出现 nn 种颜色,B 的目标则是尽量延长这个时间。A 每次可以画一条简单曲线,并围出一个封闭图形(可能不太严格,没学过这方面内容)。B 则负责给这个图形染色,要求不能与相邻的图形颜色相同。在 A 与 B 都采用最优策略时,最少几步可以达到 A 的目标?

如果给每个颜色都编号,目前看来 B 染相邻图形颜色的 mex 一定是最优的,但是我不会证……而且看起来即使证明/证伪了也离解决原问题很远。

n=5n=5 的情况:

2022/7/19 19:45
加载中...