lyg_wangyushi 发表于 2008-1-13 20:22:55

一道有趣但不难的题目

发表一个比较有趣但又不难得题目，如下：
将十个硬币放在一个园中，有头像的那一面向上，允许有以下两种运动：
1 相邻的四个金币翻一个面
2 五个金币形如 OOOOO 翻为 XXOXX
问能否经过有限次翻动，使所有的有头像的那一面向下

稍候给出答案，题目不难，相信这个论坛这么多牛人肯定有人能轻松解决。

lijeki 发表于 2008-1-13 22:14:24

答案是不能，两种运动都是翻转4个，即使没有排列顺序的10个金币随意翻转也不能通过每次翻转4个来完成

lyg_wangyushi 发表于 2008-1-14 08:06:26

楼上正解，那我就不用给出答案了。

lyg_wangyushi 发表于 2008-1-14 08:12:39

那，在出一道更难得题目，设有N(1<=N<=100000)行金币，每行有九个金币，正反面状态随机，现在要么每次改变一行的金币的正反面的状态，要么么次改变一列的金币的正反面的状态，问如何才能使经过金币正面向上的个数最多。

lijeki 发表于 2008-1-14 10:44:54

这题有点象魔方，我还是偷个懒，让了解魔方的牛人来吧:lol

mathe 发表于 2008-1-14 11:43:27

我倒是觉得同关灯游戏类似

lyg_wangyushi 发表于 2008-1-14 11:53:03

难道能经过有限次反动，使得所有的金币均正面向上吗?

mathe 发表于 2008-1-14 13:01:32

通常应该不行，但是对于某些情况应该可以

mathe 发表于 2008-1-14 13:24:25

你这个题目由于限定了列数目为9，所以可以穷举所有列变换的组合（总共最多2^9＝512种），
对于每种组合，计算正面最多的情况（只允许行变换了）就可以了

lyg_wangyushi 发表于 2008-1-14 14:47:17

问题是也可以变换列的状态阿
页: [1] 2 3
查看完整版本: 一道有趣但不难的题目