卡坦岛趣题

如图，房子只能放在交叉点上，交叉点一共54个，要求任意一条边上不能放两个房子。

答案：n最大为27，最小为15。

构造如图，三角形为放房子的点。

下证n最大为27。反证法：若n≥28，可将54个格点两两配对，使得每对格点都是一条边的两个顶点。则由抽屉原理知，必有两个房子位于一对格点上，从而相邻，与题设矛盾。因此n最大为27。

下证n最小为15。反证法：若n≤14，注意到每个房子最多只能带走四个格点（“带走A”指的是让格点A上不能再放房子。由于每个格点最多只有三个邻点，加上本身一共四个点。）因此n≤14时最多带走56个个点。而“不能再放房子”指的是每个格点必须都被带走。由于格点总数为54，因此最多只能“浪费”两个“带走”。观察图中每个方框内的结构，以上面那个方框为例，有5个度为2的点和2个度为3的点。若在某个度为2的点上放房子，则已经“浪费”了一个“带走”，若这5个点上都不放房子，则为了保证最上方三个度为2的点附近有房子，我们必须在方框中两个度为3的点上同时放房子。则它们控制一个公共点，即最上面一排正中的点，从而也浪费一个带走。由于三个方框结构完全一样，那么，我们论证了，在每个方框中，必定浪费一个“带走”，因此总共浪费三个，与最多只能浪费两个矛盾。因此n≥15，证毕。

顺便，n=15的构造是旋转对称的。

以及强烈安利卡坦岛这款桌游，特好玩