下面题的条件的充分性

来源: 康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表示感谢及歉意。另外我的一贯原则是,对于评论,不论好坏,除了直接问问题的,一律不回答。这不是因为清高,而是为了避免纠纷。希望大家理解。

所有跟帖: 

-haha2000- 给 haha2000 发送悄悄话 (0 bytes) () 12/19/2006 postreply 08:41:11

妙!! ... 怎么还是觉得必要性更妙! -乱弹- 给 乱弹 发送悄悄话 乱弹 的博客首页 (0 bytes) () 12/19/2006 postreply 08:50:26

呵呵,侠骨柔肠,师傅啊,偶爱您!:) -idiot94- 给 idiot94 发送悄悄话 (0 bytes) () 12/19/2006 postreply 08:54:13

PF! -IamSlow- 给 IamSlow 发送悄悄话 (29 bytes) () 12/19/2006 postreply 09:18:33

请您先登陆,再发跟帖!

发现Adblock插件

如要继续浏览
请支持本站 请务必在本站关闭/移除任何Adblock

关闭Adblock后 请点击

请参考如何关闭Adblock/Adblock plus

安装Adblock plus用户请点击浏览器图标
选择“Disable on www.wenxuecity.com”

安装Adblock用户请点击图标
选择“don't run on pages on this domain”