IBM Ponder This #063 · 2003 年 7 月

这是 Roy Adler、Wayne Goodwyn 和 Benjamin Weiss 提出的道路染色问题。原题发表于 2003 年，当时将其列为尚未解决的问题。

有 N 座城市和 2N 条单行道路。每座城市恰有两条出路，至少一条入路；道路可以通回自身。沿合法方向可以从任意城市到达任意其他城市。

再假设：对每个质数 p，都存在一个长度不被 p 整除的有向圈。圈沿道路从某城出发并返回，途中不重复城市，长度为经过的道路数。

给每条道路染成红色或绿色，使每座城市的两条出路颜色不同。希望存在“通用导航指令”：无论出发点是哪座城市，按某个固定的颜色序列走，最终都准确到达指定目标城。仅保证途中经过目标城还不够，必须在全部指令执行完时停在那里。

证明满足条件的道路系统总能这样染色，或者给出符合条件但不存在这种染色的反例。

例如，三城 A、B、C 的道路为 AB、AC、BA、BB、CB、CC。把 AC、BB、CB 染绿，其余染红。无论起点在哪，“绿、绿”都使人到达 B；“绿、绿、红、绿”则使人到达 C。

解答

认真尝试后再打开

待补充。