3.6　刷房子

敌友国政府颁布了一个新法案，要求所有公民为了城市的美观，必须把自家的房子刷成和所有邻居的房子不一样的颜色，无论邻里之间是敌是友。很多人表示抗议，说这是强制让民众白花钱、做苦工。后来政府同意用公共资金为居民刷房报销全款，但有一个条件：刷什么颜色要由政府来定。

由于要买的涂料数量巨大，政府职能机构想尽可能减少购买的涂料颜色的种类。少用一种颜色就能省下几百万美元。政府给敌友国理工学院拨了一笔钱，让他们找到最少需要几种颜色的涂料才能保证所有相邻的房子都有不同的颜色。

敌友国每家最多有12个邻居。所以最容易想到和实现的方案需要13种颜色：每个邻居刷一种不同的颜色，然后中间的房子刷第13种颜色。但敌友国的研究者觉得他们还能做得更好。

1852年，南非数学家弗朗西斯·格思里在为英国各郡的地图填色时，猜想是否只用四种颜色，就足够让所有地图上每两个接壤的地区有不同的颜色。当时很多数学家都考虑了格思里提出的问题，接着在1879年和1880年出现了两个四色问题的“证明”，分别由阿尔弗雷德·肯普以及彼得·泰特发表。11年后两个证明都被发现有致命错误，在之后几乎一个世纪的时间，这个问题都未能得到解决。

1976年，肯尼斯·阿佩尔和沃尔夫冈·哈肯终于给出了四色问题的证明，但他们使用了一种非常有争议的技术。证明过程需要用一个计算机穷举所有可能的情况来支持他们的论点。传统数学家不相信这样的证明，因为它不能完全用人的思维来检验。但是几十年过去了，人们没有找到阿佩尔-哈肯证明中有任何错误，如今大多数人都相信，四种颜色足够为所有的地图填色。

四就是极限了吗？三种颜色够不够填满所有地图？不够，来看内华达州和它接壤的州。

图3-14 内华达州

加利福尼亚州、俄勒冈州、爱达荷州、犹他州和亚利桑那州，这几个州在内华达州外面围成一圈。由于这个圈包含奇数个州（5个），需要至少三种颜色来填充它们；如果只有两种颜色，比如绿和蓝，加利福尼亚州涂绿色，与之接壤的俄勒冈州必然是蓝色，然后爱达荷州必须是绿色，犹他州是蓝色。现在，亚利桑那州分别与绿色的加利福尼亚州和蓝色的犹他州接壤，所以它既不可以是绿色，也不能是蓝色。所以我们至少需要三种颜色——蓝、绿和黄，来填充这五个州。

内华达州与五州分别接壤，那么它不能填蓝、绿或黄这三种颜色。所以我们需要第四种颜色——红，来为内华达州上色。

有了基于四色定理的证明的高效算法，就可以很快为任意地图涂上四种颜色。于是敌友国的研究者找到了用四种颜色给所有房子刷漆的方法，保证了相邻房子的颜色不同。政府又敦促学院找到只用三种颜色涂料的方法。恰巧敌友国没有邻居个数为奇数的房子，所以研究者没办法直接排除只用三种颜色的方法存在的可能性。

计算机科学家们几经尝试，最终放弃了。他们向政府报告找不到只用三种颜色的涂色方案。政府不得不使用四种颜色的方案粉刷所有房子。敌友国的计算机科学家们将来在申请政府津贴时会遇到更多困难。