下面题的条件的充分性

来源: 康MM 于 2006-12-19 08:36:42 [档案] [旧帖] [给我悄悄话] 本文已被阅读：次 (1346 bytes)

5×5＝25个格子里随机分布25个棋子，只有两种颜色，黑色和白色。

可以通过点任何一个棋子，让包括棋子本身和棋子相邻的棋子变换颜色（黑变白，白变黑）

比如棋盘中央的，点一次变5个，棋盘边缘，点一次变4个，棋盘角落，点一次变3个。

请问，有没有办法通过点击，使棋盘中的所有棋子都变成同一颜色，黑色

解答

把棋盘标为

1 2 3 2 1
3 0 3 0 3
2 2 0 2 2
3 0 3 0 3
1 2 3 2 1

一个棋盘的值为白棋子的值的二进制不进位加法的和（XOR）。容易看出变色时整个棋盘的值不变。因此可以都变成黑色的必要条件是值为0。

Iamslow 问到条件的充分性，可以这样证明：任意一个棋盘分布，都可以把白子慢慢地赶到一条边上，因此只需对一条边上有白子的情况证明。这是白子的位置一定是{1，5}，{2，4}，{1，2，3}或他们的组合。而这三种情况都是有解的：设白棋子都在上边。大圆圈是要点击变色的地方。

{1，5}

。。。〇〇
〇。〇。〇
〇。〇〇。
。。〇。。
〇〇。。。

{2，4}

。。〇〇〇
。。。。。
。。〇〇〇
。〇。〇。
〇〇〇。。

{1，2，3}

。。。〇。
〇〇。〇〇
。。。〇。
〇〇〇。。
。〇。。。

最后再多说几句。这个题本身是很好的题，也很难。作出难题来肯定是很高兴的，有时就会说一些不太得体的话。如果冒犯了任何人，我在此致歉。也对Iamslow表示感谢及歉意。另外我的一贯原则是，对于评论，不论好坏，除了直接问问题的，一律不回答。这不是因为清高，而是为了避免纠纷。希望大家理解。