关于一道图论题&组合数学中的证

· · 算法·理论

题目描述

将 n 枚硬币任意摆放在图中的点上（每个点的硬币个数不限，可以为 0），对于图定义一次操作：从一个至少有 2 枚硬币的点取走 2 枚硬币，并分别在与此点相邻的点上各放置 1 枚硬币。对每种摆法，若点 E 处无硬币，则总能经过若干次该操作使点 E 处有硬币，求 n 的最小值。

解法

定义环上两点的最短距离为在环上到达两点最少需要的步数，如 C,E 两点的最短距离为 \min(2,3)=2，A,B 两点的最短距离为 \min(1,4)=1。

定义环上两点的最长距离为在环上到达两点次少需要的步数，如 C,E 两点的最长距离为 \max(2,3)=3，A,B 两点的最长距离为 \max(1,4)=4。

定义合法为对于每种摆法，若点 E 处无硬币，则总能经过若干次该操作使点 E 处有硬币。

下述对于位置的描述默认不包括 E。

首先，对于 n < 5 的情况，显然根据鸽巢原理，在最坏摆法下，所有的位置最多都只有一个硬币。故 n < 5 的情况不能满足对于每种摆法，能经过若干次该“操作”后使 E 处有硬币。

对于 n=5 的情况，对于每一种摆法，初始时都至少有一个位置的硬币数量大于等于 2，至多有两个位置的硬币数量大于等于 2，由于需要证明 n=5 对于所有摆法都成立，所以根据有几个位置硬币的数量大于等于 2 进行分类讨论。

  1. 初始时有一个位置的硬币数量大于等于 2。将这个位置记为 \alpha。

    显然地，若 \alpha 与 E 相邻，那么对 \alpha 进行一次操作后，点 E 上就有了 1 枚硬币。所以下面的讨论都不包括 \alpha 与 E 相邻的情况。

    根据前置可知，若 \alpha 上的硬币数量大于等于 4 的时候，对 \alpha 进行 2 次操作，之后与其相邻的、在与 E 的最短距离的路径上的点上的硬币数量至少为 2，可以对其进行 1 次操作，又因为前置性质，所以与此点相邻的点中必然有一个点为 E。即操作结束后，E 点必然有硬币。

    若 \alpha 上的硬币数量等于 3 时，显然地，除了 \alpha 外的其他位置上有且只有两个位置的硬币数量为 1。若在 \alpha 与 E 的最短距离的路径上的、与 \alpha 相邻的点上有硬币（硬币数量为 1），那么对 \alpha 进行 1 次操作后，此点上有 2 枚硬币，对其进行 1 次操作后，由于前置性质，所以与此点相邻的点中必然有一个点为 E。即操作结束后，E 点必然有硬币；若在 \alpha 与 E 的最短距离的路径上的、与其相邻的点上没有有硬币（硬币数量为 0），即在 \alpha 与 E 的最短距离的路径上的点上有且仅有 1 枚硬币（不包括点 E 与点 \alpha），这种情况和上面的情况相似，显然经过操作后 E 点会出现硬币。

    若 \alpha 上的硬币数量等于 2 时，显然地，除了点 E,\alpha，其余的位置上有且仅有一枚硬币，对 \alpha 进行一次操作，此时在 \alpha 与 E 的最短距离的路径上的、与 \alpha 相邻的点上有 1+1=2 枚硬币，再将其进行一次操作，由于前置性质，所以与此点相邻的点中必然有一个点为 E。即操作结束后，E 点必然有硬币。

    综上所述，在初始时有一个位置的硬币数量大于等于 2 的情况下，是合法的。

  2. 初始时有两个位置的硬币数量大于等于 2。将两个位置分别记为 \alpha,\beta。

    显然地，若 \alpha 或 \beta 与 E 相邻，那么对 \alpha 进行一次操作后，点 E 上就有了 1 枚硬币。所以下面的讨论不包括 \alpha 与 E 相邻的情况。

    去除掉 \alpha 或 \beta 与 E 相邻的情况后，只剩下 \alpha,\beta 与 E 的最短距离都为 2 的情况了，由于圆的对称性，所以对于 \alpha,\beta 上硬币枚数颠倒的情况其实是和原来的情况一样的，故我们钦定 \alpha 上的硬币数量小于等于 \beta 上的硬币数量。

    对于 \alpha,\beta 与 E 的最短距离都为 2 的情况，显然地，\alpha,\beta 相邻。若 \alpha,\beta 上的硬币数量都为 2，那么对于除了 \alpha,\beta,E 三点之外的两点中有 1 个位置上的硬币数量为 1，易证 \alpha 或 \beta 与这个位置与相邻，记与这个位置相邻的 \alpha 或 \beta 为 \gamma，那么对 \gamma 进行一次操作后，这个位置有 2 枚硬币，对这个位置进行操作，根据前置性质，所以与此点相邻的点中必然有一个点为 E。即操作结束后，E 点必然有硬币；若 \alpha 上的硬币数量为 2，\beta 上的硬币数量为 3，可以先对 \alpha 进行一次操作，操作后 \beta 上的硬币数量为 4，之后对 \beta 进行两次操作后，在 \alpha 与 E 的最短距离的路径上的、与 \alpha 相邻的点上有 2 枚硬币，最后将其进行 1 次操作，根据前置性质，所以与此点相邻的点中必然有一个点为 E。即操作结束后，E 点必然有硬币。

    综上所述，在初始时有两个位置的硬币数量大于等于 2 的情况下，是合法的。

由于对于两种可行可能都是合法的，所以当 n=5 时，对于每种摆法，若点 E 处无硬币，则总能经过若干次该操作使点 E 处有硬币。

原命题得证，证毕。

进一步的推广

我们不难发现，对于一个有 m 个点的环，都有一个最小值 n=m（1 < m ），且证法都形如上述证明。