著名的四色定理(four color theorem)告诉我们，如果一个地图由若干个连通区域构成（没有飞地），那么在给每个区域染色时，为了让相邻区域的颜色不同，最多只需要四种颜色就足够了。不过，这个结论成立有一个条件：整个地图已经事先确定了。如果我们每次只增加一个区域的话呢？具体地说，如果每次你给一个区域染色之后，我再画出下一个区域，并且之前已经染好颜色的区域不能再修改了，那么四种颜色还足够吗？这里，我们假设，在染色时，你总是遵循一个非常朴素的贪心策略：用第一个合法的颜色给每个新的区域染色。下面这个例子告诉我们，在这些假设下，四种颜色就不够了，有时五种颜色是必需的。
图1
我们的问题就是，在这些假设下，五种颜色就一定够吗？有没有可能构造出某个情况，使得六种颜色是必需的？有没有可能构造出某个情况，使得七种颜色是必需的？
事实上，对于任意的正整数 n ，我们都能构造出某个情况，使得 n 种颜色是必需的。下图显示的是 n = 6 的情况，我们很容易把它扩展到任意大的正整数 n 。
图2
你可以在这里看到更多有关于这个问题的讨论： http://www.iread.it/map_colors.php
声明：文章转自Matrix67博客，版权归原作者所有，转载仅供学习使用，不用于任何商业用途，如有侵权请联系删除，谢谢。
