有限次操作的红点问题

石崇的BOSS

在一个圆周上只有2个蓝点。定义两种操作：
操作A：在圆周上加一个红点，并且改变相邻两个结点的颜色
操作B：在圆周上去掉一个红点，并且改变相邻两个结点的颜色。
问能否通过有限次操作，使得圆周上只有两个红点。

Cielo

红0，蓝1，考虑圆周上所有点的数字之和。
加一个红点的操作使得总数产生变化，变化总是模4余2；
减一个红点也是这样。

假设若干步操作之后，圆周上只有两个点，那么加红点的次数和减红点的次数相等。于是总数变化模4余0~
而初始时刻，总数=2，于是不可能出现只剩两个红点（总数=0）的情况。
————————————————————————————————————————————————
以上证明有误……

[ 本帖最后由 Cielo 于 2011-10-11 23:32 编辑 ]

钟七珍

似乎不可能。
证明的难点在“改变相邻两个结点的颜色”这个限制条件。没有这个限制条件则有解。

superacid

显然蓝点永远是偶数个。

找到一种分类方法，把所有有偶数个蓝点的圆周分成2类。

第一步：如果圆周上没有蓝点，我们可以在某两个红点之间加一个红点，于是这3个点变成蓝红蓝，就有蓝点

了。
第二步：计算圆周上任意相邻两个蓝点之间的红点个数，写成一个数列，该数列一定有偶数项。
    设有2n个蓝点，该数列为a1,b1,a2,b2,...,an,bn。
第三步：分别计算该数列奇数项之和s=a1+a2+...+an，偶数项之和t=b1+b2+...+bn。
    如果s-t是3的倍数，那么一定可以在有限步内化为只有两个蓝点，否则一定可以化为两个红点。
第四步：容易证明，如果奇数偶数项之和的差是3的倍数，那么对任意操作它都是3的倍数；否则对任意操作

它都不是3的倍数。

所以不可能在有限步内把两个蓝点变成两个红点。

rubik-fan

我的想法：
最初两个点，最后两个点。点数增减抵消。表明操作步数必须是偶数，而且a操作和b操作次数相同。
而两个蓝色的点变成红色，需要奇数次操作。即，不管第几次操作是a还是b，只要是偶数步，必然会有蓝色的点。
所以不可以用偶数次操作完成把蓝色的点变成红色。

superacid

不管第几次操作是a还是b，只要是偶数步，必然会有蓝色的点。

这点需要证明

===============================
edit:楼下已经举出反例

钟七珍

原帖由 superacid 于 2011-10-12 14:02 发表
不管第几次操作是a还是b，只要是偶数步，必然会有蓝色的点。

这点需要证明

　　连续4次操作A，可出现6个红点而没有蓝点。
　　大家讨论时，似乎都忽略了“相邻变色”这个限制条件。

rubik-fan

原帖由 钟七珍 于 2011-10-12 16:58 发表

　　连续4次操作A，可出现6个红点而没有蓝点。
　　大家讨论时，似乎都忽略了“相邻变色”这个限制条件。

看来我说的有漏洞。

[ 本帖最后由 rubik-fan 于 2011-10-13 09:59 编辑 ]