[今天我们思考5]

[陈怀兴]

今天我们思考，我们来接着做题与思考。

1. 简单而但是有意思的一个题：

   有一根1米长的木棒漂流在海上，突然从天空中降下100只蚂蚁，幸运的是它们都降在了在这根木棒上，（它们降落在木棒上的位置是随机的）。然而不幸的事发生了，所有蚂蚁从降落的时刻起就随机朝着木棒的一个方向以1cm/s的速度行走，而当发生两只蚂蚁相碰的时候，它们就各自立即进行反方向行走。一旦有蚂蚁走到了木棒的如何一段，这只蚂蚁就会落入大海。现在，问最少经历多少时间就可以保证所有的蚂蚁都在海里游泳了？


2.如果要做出最佳答案，中等难度的一个题：

 现在有10个人被一个魔鬼逮住了。魔鬼对于直接把人杀掉的方法不感兴趣了。于是，他就想了一个杀人的新花样。是这样的，一天晚上，魔鬼向这十个人宣布了游戏规则，即明早他要把他们10个人排成一排，然后从一堆既有无限多的白帽子混会着无限多的黑帽子的帽子堆里为每个人随机抽取一顶帽子，给他们10个人都戴上帽子。因为10个人是排成一排的，所以排在第10个的人可以看到前面9个人帽子的颜色，排在第9个人可以看到前面8个人的帽子的颜色，...以此类推。然后，魔鬼会从排在第10个人开始，问他，你头上的帽子的颜色是白色还是黑色，如果答对了，就放他走；如果答错了，就被杀掉。然后同样问排在第9位的人，然后问同样问排在第8位的人，...以此类推。在这其中，10个人所能做的只有当他被魔鬼问到的时候，答白色或者黑色。不能有超越此范围的任何行动，不然，魔鬼会把他们10个人全都杀死。
现在，魔鬼给他们10个人一个晚上的时间去商量一个对策，使得他们中能存活下来的人越多越好。请问，你会有什么样的对策，请计算出按照你的对策执行时最坏的情况下，他们中能有多少人能100%够活下来？期望能活下来的人数又是多少？

[xxmplus]

第二题我是这样想的，既然帽子的颜色是随机的，那只有靠别人告诉你了，所以第10个人应该把第9个人头上帽子的颜色作为答案，这样第9个人就知道自己头上的帽子是什么颜色了，如此除了第10个人，其他人都能活下来，第10个人就50%，赌一把吧。。。

2008/4/16 陈怀兴 <sil...@gmail.com>:

--
Any complex technology which doesn't come with documentation must be the best
available.

[xxmplus]

第一题我捕捉到了一些东西，不过还没想透彻。。。。似乎应该是100秒吧。。。我在想想。。。。

2008/4/16 xxmplus <xxm...@gmail.com>:

[陈怀兴]

你的直觉很准。And the next is to Prove it :-)

ＢＴＷ：算全部蚂蚁落水的期望时间也是个很好问题。

2008/4/16 xxmplus <xxm...@gmail.com>:

[陈怀兴]

接着再好好想想。
你现在的答案的改进余地非常的大噢:-)

2008/4/16 xxmplus <xxm...@gmail.com>:

[王小康]

我是这样卡频率第二个问题的:
第10个人告诉第9个人他的帽子的颜色,然后第8个人告诉第7个人,等等,依此类推.

那么一共有5个人100%活下来,都是奇数的;5个人50%活下来,都是偶数的.
活下来的人数的期望是7.5个.
看看对不对.我的算法很简单.可能没找准路子.

在08-4-16，陈怀兴 <sil...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[陈怀兴]

这样做当然是一种可行的策略  :-)
但是仍然还有很大改进的余地。

2008/4/16 王小康 <egm...@gmail.com>:

[王小康]

我再想想啊.lol

在08-4-16，陈怀兴 <sil...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[hyifeng]

第一题我的结果也是100s
第二题必然生存的有70%，总共有85%的生存率，每3个人中的后一个人救前两个人，自己听天由命，不知道有没有更好的方法。

On 4月16日, 下午9时01分, "陈怀兴" <silw...@gmail.com> wrote:
> 接着再好好想想。
> 你现在的答案的改进余地非常的大噢:-)
>

> 2008/4/16 xxmplus <xxmp...@gmail.com>:

>
>
>
> > 第二题我是这样想的，既然帽子的颜色是随机的，那只有靠别人告诉你了，所以第10个人应该把第9个人头上帽子的颜色作为答案，这样第9个人就知道自己头上的帽子是什么颜色了，如此除了第10个人，其他人都能活下来，第10个人就50%，赌一把吧。。。
>

> > 2008/4/16 陈怀兴 <silw...@gmail.com>:

[王小康]

...你还可以改进.....
我先问问,你的算法是怎么给的,我怎么看不懂啊????
你说第10个给第9个说了答案,那么8-1就全部获救了,那么就是9*100%+1*50%的概率咯.
但是,你说的是第10个给第9个说了,并没有给8-1的而说答案啊~~~而且,题目说明,人家问,你只能回答:白的或者黑的,除此之外,10个人全部被杀头.......
帮我解释一下!!

在08-4-16，hyifeng <hyi...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[陈怀兴]

A nice progress!
还有更好的。从这个策略到下一个策略，需要一个突破。如果你跨越了这一部，请你讲讲你是怎样跨越的。这个是最重要的。就如pongba在今天我们思考系列里始终强调的那样。

2008/4/16 hyifeng <hyi...@gmail.com>:

[陈怀兴]

对于第一题，几乎我问过的所有人都能给出100s这个答案，但只有1/10的人能够非常清楚的解释为什么是100s。

2008/4/16 hyifeng <hyi...@gmail.com>:

[Googol Lee]

1 100s

最大情况，肯定是所有蚂蚁掉在一条线上，所以就把木棍考虑成一个一维的线。

想象掉在最两端的蚂蚁头上各有一只不动的蚂蚁，这只蚂蚁在下面的蚂蚁相撞时就转移到另一只的头上，相当于这两只骑着的蚂蚁方向一直不变。而且，被这两只骑着的蚂蚁骑过的蚂蚁都不会再发生碰撞，且方向一致，背向骑着的蚂蚁向水里英勇的走去……

那么，当这两只骑着的蚂蚁相遇时，应该是所有蚂蚁最后一次碰撞。（恩……我不是很会描述这个的证明，但是这个情况应该是对的）而且，其余所有蚂蚁方向都一致且速度一致，因此这两只骑着的蚂蚁必定骑在在最后落水的蚂蚁上。

因此，最长时间就是这两只骑着的蚂蚁掉水的最大时间，自然就是从木头一头走到另一头。而平均期望也就很容易算了。

在 08-4-16，陈怀兴<sil...@gmail.com> 写道：

--
新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。

My blog: http://googollee.blog.163.com

[hyifeng]

不分彼此的，碰撞可视作穿越。

第二题改进的只是期望，只是方法复杂一些而已。 谁有好方法？

On 4月16日, 下午10时37分, "陈怀兴" <silw...@gmail.com> wrote:
> 对于第一题，几乎我问过的所有人都能给出100s这个答案，但只有1/10的人能够非常清楚的解释为什么是100s。
>

> 2008/4/16 hyifeng <hyif...@gmail.com>:

[王小康]

第一道题目我想出来了lol,大家看看对不对!!!

这个问题的那点就在于碰撞!!!很容易搞混的.
这样考虑,A和B碰撞,完后,A和B朝着相反的方向继续前进.其实可以等价于,A和B朝着各自的方向继续前进.只是A和B还了一个个而已.都是蚂蚁.
那么就是说经历时间最长的那个肯定是从一端到另一端的.
不要被换方向给迷惑了.

大家看对不对?

在08-4-16，Googol Lee <goog...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[陈怀兴]

A Big Hint:
  9个人可以保证活下来
:-)

2008/4/16 hyifeng <hyi...@gmail.com>:

[王小康]

那么那就是说第10个给前面9个人说了答案????
可是人家说的只能回答:白的或者黑的.
你说了9个人的答案貌似要被杀头的吧??lol

在08-4-16，陈怀兴 <sil...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[陈怀兴]

思考，思考，思考。
按照pongba的分类法，这是个好题目:-)
&& 中等难度。

2008/4/16 王小康 <egm...@gmail.com>:

[alai]

我的思路：从只能回答白或黑，也就是只能2中选1，从而联想到二进制和奇偶性。二进制一下子没想出什么好方法，奇偶性有一些提示，所以从奇偶性入手。第10个人以他所见到的9个帽子中白帽的数量的奇偶性作答，例如大家约定白代表偶，黑代表奇，则第10个人的回答是前9个帽子中白帽的数量的奇偶。他自己有50%的机会。第9个人听到他的回答后，结合他看到的8顶帽子中白帽的奇偶，可以知道自己的帽子的颜色，如实作答。第8个人知道9顶帽子中白帽的奇偶，加上听到第9顶帽子的颜色，就可以知道前8顶帽子中白帽的奇偶(如果第9个人答白，则前8顶中的白帽奇偶性与第第10个人所说的相反；如果第9个人答黑，则相同)，再结合所看到前7顶帽子中的白帽数量，也可以推出自己的帽子颜色，也如实作答。依此类推，前9个人都可以活下来，第10个人有一半机会。

在 08-4-16，王小康<egm...@gmail.com> 写道：

[陈怀兴]

orz!

2008/4/16 alai <ala...@gmail.com>:

[陈怀兴]

好。接下来我们把这个题泛化一下，如果现在帽子的颜色的种数不是两种，而是三种，是不是仍然可以使得保证9个人活下来？四种呢？n种 呢？
Enjoy！
:-)

2008/4/16 alai <ala...@gmail.com>:

[hyifeng]

提示太大了，想出来的快感大打折扣。

On 4月16日, 下午10时49分, "陈怀兴" <silw...@gmail.com> wrote:
> A Big Hint:
> 9个人可以保证活下来
> :-)
>

> 2008/4/16 hyifeng <hyif...@gmail.com>:

[alai]

用信息论来推论，理论上来说，应该是可以保证前9个人活下来，而第10个人的机会则是1/n。不过，这个方案的设计应该比较妙，我一下子还没想出来。

在 08-4-16，陈怀兴<sil...@gmail.com> 写道：

[陈怀兴]

.......

2008/4/16 hyifeng <hyi...@gmail.com>:

[王小康]

这个算法很妙~~~~
加十分.lol.我没想到.

在08-4-16，alai <ala...@gmail.com> 写道：

--
http://egmkang.cnblogs.com/

[陈怀兴]

当时我做这个题目的时候，是看了这个提示后才做出来的。
不过我觉得从2种颜色泛化到n中颜色这一步比只有两种颜色的时候从7个人活下来到9个人活下来这一步简单一点。

2008/4/16 hyifeng <hyi...@gmail.com>:

[SlackCode]

很有启发性的帖子，哈。

[njin]

第一题问的有问题，100s是最长时间不是最短时间。忘记哪位大大告诉过我，可以把蚂蚁想像成幽灵蚂蚁，及当两个蚂蚁相遇时会直接相互穿过继续行走。这样最长时间就是一只蚂蚁掉落到木棍的一端，往另一端行走，用时100s。
最短时间没法计算，既然是随机的，蚂蚁都掉落到木棍的一端，并且都往靠海的这一端走呐？

在 08-4-16，陈怀兴<sil...@gmail.com> 写道：

> 今天我们思考，我们来接着做题与思考。
>
> 1. 简单而但是有意思的一个题：
>
>
> 有一根1米长的木棒漂流在海上，突然从天空中降下100只蚂蚁，幸运的是它们都降在了在这根木棒上，（它们降落在木棒上的位置是随机的）。然而不幸的事发生了，所有蚂蚁从降落的时刻起就随机朝着木棒的一个方向以1cm/s的速度行走，而当发生两只蚂蚁相碰的时候，它们就各自立即进行反方向行走。一旦有蚂蚁走到了木棒的如何一段，这只蚂蚁就会落入大海。现在，问最少经历多少时间就可以保证所有的蚂蚁都在海里游泳了？
>
>
> 2.如果要做出最佳答案，中等难度的一个题：
>
> 现在有10个人被一个魔鬼逮住了。魔鬼对于直接把人杀掉的方法不感兴趣了。于是，他就想了一个杀人的新花样。是这样的，一天晚上，魔鬼向这十个人宣布了游戏规则，即明早他要把他们10个人排成一排，然后从一堆既有无限多的白帽子混会着无限多的黑帽子的帽子堆里为每个人随机抽取一顶帽子，给他们10个人都戴上帽子。因为10个人是排成一排的，所以排在第10个的人可以看到前面9个人帽子的颜色，排在第9个人可以看到前面8个人的帽子的颜色，...以此类推。然后，魔鬼会从排在第10个人开始，问他，你头上的帽子的颜色是白色还是黑色，如果答对了，就放他走；如果答错了，就被杀掉。然后同样问排在第9位的人，然后问同样问排在第8位的人，...以此类推。在这其中，10个人所能做的只有当他被魔鬼问到的时候，答白色或者黑色。不能有超越此范围的任何行动，不然，魔鬼会把他们10个人全都杀死。
> 现在，魔鬼给他们10个人一个晚上的时间去商量一个对策，使得他们中能存活下来的人越多越好。请问，你会有什么样的对策，请计算出按照你的对策执行时最坏的情况下，他们中能有多少人能100%够活下来？期望能活下来的人数又是多少？
>
>
>
> >
>

--
Best Regards,
Niu Jin

[陈怀兴]

actually, 就是最短的时间。看清题目。
"问最少经历多少时间就可以保证所有的蚂蚁都在海里游泳了？"

2008/4/17 njin <njin...@gmail.com>:

[xxmplus]

恩，题目没问题，我想的办法和上面各位的不一样，不过我语言还没组织好，不知道要怎么描述清楚-__-

2008/4/17 陈怀兴 <sil...@gmail.com>:

--

[njin]

sorry，明白了～～～～

在 08-4-17，陈怀兴<sil...@gmail.com> 写道：

[hyifeng]

经常性犯同一个毛病，就是没有把条件用尽。
我想像pongba把条件列出来，会有助于警告自己，自己在掌握着什么。

On 4月16日, 下午11时46分, "陈怀兴" <silw...@gmail.com> wrote:
> 当时我做这个题目的时候，是看了这个提示后才做出来的。
> 不过我觉得从2种颜色泛化到n中颜色这一步比只有两种颜色的时候从7个人活下来到9个人活下来这一步简单一点。
>

> 2008/4/16 hyifeng <hyif...@gmail.com>:

[njin]

第二题，我的思考的过程如下（我坦白我受到了提示：1、9个人是一定可以活下去的；2、这个题目按pongba的分类是个好题目）：
1、9个人都可以活下来的话，那么这9个人只能回答自己帽子的颜色，只有第十人豁出去了，他的答案要包含9个人帽子颜色的信息；
2、用极限法，假设只有两人，那么第二个人只要回答第一个人帽子的颜色；如果是3个人呐？第三个人可以这样回答，如果前面两人帽子的颜色一样，那么回答黑色，反之，答白色。这样第二个人可以根据他看到的第一个人帽子的颜色作答；
3、再加一个人，4个人。这时想了很久，后来想到，既然每个人都可以听到第十个人的回答，实际上他们可以听到所有人的回答。那么前九个人可用的信息实际上是除了自己之外，前九个人帽子的颜色以及第十个人回答的key。这个key只有两个值，然后联想到了奇偶数。将白色表示0，黑色为1，第十个人将前九个人的代码加起来，如果值是偶数回答白色，反之答黑。前九个人根据其他8个人帽子的颜色，和9个人之和是奇数还是偶数来判断自己帽子的颜色。

在 08-4-16，陈怀兴<sil...@gmail.com> 写道：

> 今天我们思考，我们来接着做题与思考。
>
> 1. 简单而但是有意思的一个题：
>
>
> 有一根1米长的木棒漂流在海上，突然从天空中降下100只蚂蚁，幸运的是它们都降在了在这根木棒上，（它们降落在木棒上的位置是随机的）。然而不幸的事发生了，所有蚂蚁从降落的时刻起就随机朝着木棒的一个方向以1cm/s的速度行走，而当发生两只蚂蚁相碰的时候，它们就各自立即进行反方向行走。一旦有蚂蚁走到了木棒的如何一段，这只蚂蚁就会落入大海。现在，问最少经历多少时间就可以保证所有的蚂蚁都在海里游泳了？
>
>
> 2.如果要做出最佳答案，中等难度的一个题：
>
> 现在有10个人被一个魔鬼逮住了。魔鬼对于直接把人杀掉的方法不感兴趣了。于是，他就想了一个杀人的新花样。是这样的，一天晚上，魔鬼向这十个人宣布了游戏规则，即明早他要把他们10个人排成一排，然后从一堆既有无限多的白帽子混会着无限多的黑帽子的帽子堆里为每个人随机抽取一顶帽子，给他们10个人都戴上帽子。因为10个人是排成一排的，所以排在第10个的人可以看到前面9个人帽子的颜色，排在第9个人可以看到前面8个人的帽子的颜色，...以此类推。然后，魔鬼会从排在第10个人开始，问他，你头上的帽子的颜色是白色还是黑色，如果答对了，就放他走；如果答错了，就被杀掉。然后同样问排在第9位的人，然后问同样问排在第8位的人，...以此类推。在这其中，10个人所能做的只有当他被魔鬼问到的时候，答白色或者黑色。不能有超越此范围的任何行动，不然，魔鬼会把他们10个人全都杀死。
> 现在，魔鬼给他们10个人一个晚上的时间去商量一个对策，使得他们中能存活下来的人越多越好。请问，你会有什么样的对策，请计算出按照你的对策执行时最坏的情况下，他们中能有多少人能100%够活下来？期望能活下来的人数又是多少？
>
>
>
> >
>

--
Best Regards,
Niu Jin

[alai]

断断续续想了一天，解法想出来了，其实很简单，就是用模运算。
思路是这样的，当然是从2种颜色开始，前面提到用奇偶性来解决，但是奇偶性到了3种以上颜色就没法用了。目标是要找到一种相类似的运算；我想到在2种颜色时，奇偶性可以用二进制的异或运算来实现，即白帽子记为0，黑帽子记为1，第10个人计算前9顶帽子的异或值，将结果作为回答，让前面9个人听到；第9个人可以根据这个值和前8顶帽的异或值推出自己的帽子颜色；依次类推。
异或运算只能应用于二进制，所以我想到对于n为2的整数幂(如2^m)的情况，可以把每一种颜色记为m位的二进制，采用前面的方法即可。
那么对于不是2的整数幂的n呢？异或运算又行不通了，要找到新的运算。
这时，我开始思考对于这种运算，需要具备哪些特性？我想主要有几点：
1.运算是二元的，可交换的；
2.运算的自变域和值域都是0..n-1；
3.二个自变量的组合有n^2种，通过运算后映射到n个值中，这种映射应该是均匀的，即每n个组合映射到1个值，且这n个二元组中的每个维度应该都有n个不同值；(这说得很啰嗦，我的表达能力不好)
还是举例吧，以n=4的异或运算为例，该运算可以用以下二维表表示：
0 1 2 3
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0
可以看到，结果为0的4个二元组(0,0) (1,1) (2,2) (3,3)，分别取两个维度中的一个来看，每个维度分别是(0,1,2,3)
(0,1,2,3)；同样结果为1的4个二元组(0,1) (1,0) (2,3) (3,2)也同样满足这个条件，结果为2和3的也是这样。
把这些条件想清楚了，这个运算就很明显了，它就是模运算。
对于普通的n，解法如下：以0..n-1表示n种颜色，第10个人计算前9顶帽子的总和模n的值，将结果作为回答，让前面9个人听到；第9个人可以根据这个值和前8顶帽的总和模n的值一起推出自己的帽子颜色；依次类推。

在 08-4-16，alai<ala...@gmail.com> 写道：

[陈怀兴]

......
很棒。

2008/4/17 alai <ala...@gmail.com>:

[Googol Lee]

很清晰的想法，赞一个

在 08-4-17，alai<ala...@gmail.com> 写道：

[googlechen]

受alai的启发，现在给出问题二的推广情形的完整解法，是用抽象代数中的群论给出的：

设有n种颜色的帽子，记为：x(1),x(2),x(3),...,x(n)。
有m个人，从头到尾每个人帽子的颜色依次为：y(1),y(2),...y(m)。

{x(1),x(2),...,x(n)}构成一个集合，记为A，显然y(i)属于A，i=1, ..., m。

假设在A中定义了一个运算使得A构成一个群，我们把这个运算且称之为乘法，那么：
第m个人可以报出 y(1)y(2)...y(m-1) 运算的结果,记为K(m-1), K(m-1)当然也是A的一个元素，因为A是一个群。则他说
的正确的概率为1/n。
第m-1个人就看到了这样一个等式：K(m-2)y(m-1) = K(m-1)，其中
K(m-1)=y(1)y(2)...y(m-2)，K(m-2)显然是第m-1个人能够看到的，K(m-1)是他听到的。

他就可以从这个等式中计算出y(m-1),就是计算出他自己的帽子颜色。以此类推，其他人照样。

最后我们来说明集合A的确可以成群就可以了，这实际上是说：对于任何自然数n，是否存在一个群其元素个数恰好就是n。
而这是显然的，因为1的n个复数单位根，就构成一个群，运算是复数乘法。

上面的证明中象x(1)这样的记号，本来1应当写成下标，那才是习惯的数学写法，但是我不知道怎么能排版做到那样，就只好用括号（）代表下标了。

[googlechen]

上面解答中这一行写错了：
K(m-1)=y(1)y(2)...y(m-2)，K(m-2)显然是第m-1个人能够看到的，K(m-1)是他听到的。

正确的应当是：

K(m-2)=y(1)y(2)...y(m-2)，K(m-2)显然是第m-1个人能够看到的，K(m-1)是他听到的。

[googlechen]

上述解答说明，对于固定的n，有多少个不同构的n元群，此题目就有多少种不同的解法，每一种不同构的群对应一种算法。alai用的整数模n运算群显然是
和1的n次单位根群同构。

[silwile]

这么晚了，还都不睡啊:-)

抽象代数的解法，好强大。
:P

2008/4/20 googlechen <che...@sina.com>:

[pongba]

alai和googlechen是牛人，鉴定完毕！
alai的思路超级清晰！！
googlechen的进一步抽象很强大。对了，除了modn运算之外，还能举出其它可用于这个题的运算吗？

2008/4/20 googlechen <che...@sina.com>:

上述解答说明，对于固定的n，有多少个不同构的n元群，此题目就有多少种不同的解法，每一种不同构的群对应一种算法。alai用的整数模n运算群显然是
和1的n次单位根群同构。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[hayate]

re!

好强大 无限景仰

2008/4/20 pongba <pon...@gmail.com>:

[googlechen]

给出一个4元群的例子，与整数对4模运算群不同构：

A = {x0,x1,x2,x3}, 可以这样定义一个可交换运算：

(1) x0是单位元，就是说任何元素与x0运算的结果都是那个元素自己：x0x1=x1,x0x2=x2,...
(2) 任何元素的逆元是自己，也就是说：x1x1 = x2x2 = x3x3 = x0.
(3) 任何两个不同的非单位元素，运算结果是剩下的那个非单位元素，也就是：x1x2=x3,x1x3=x2,x2x3=x1.

On 4月20日, 下午12时24分, pongba <pon...@gmail.com> wrote:
> alai和googlechen是牛人，鉴定完毕！
> alai的思路超级清晰！！
> googlechen的进一步抽象很强大。对了，除了modn运算之外，还能举出其它可用于这个题的运算吗？
>

> 2008/4/20 googlechen <cher...@sina.com>:

[pongba]

2008/4/21 googlechen <che...@sina.com>:

给出一个4元群的例子，与整数对4模运算群不同构：

A = {x0,x1,x2,x3}, 可以这样定义一个可交换运算：

(1) x0是单位元，就是说任何元素与x0运算的结果都是那个元素自己：x0x1=x1,x0x2=x2,...
(2) 任何元素的逆元是自己，也就是说：x1x1 = x2x2 = x3x3 = x0.
(3) 任何两个不同的非单位元素，运算结果是剩下的那个非单位元素，也就是：x1x2=x3,x1x3=x2,x2x3=x1.

嗯嗯，这个能行！:-)
如果推广到n元的话定义(3)应该怎么修改呢？

[TeEmo]

对于不是2的整数幂的n，异或运算也还是行得通的！
模运算也是都可以行得通。

On 4月17日, 下午10时28分, alai <ala...@gmail.com> wrote:
> 断断续续想了一天，解法想出来了，其实很简单，就是用模运算。

> 思路是这样的，当然是从2种颜色开始，前面提到用奇偶性来解决，但是奇偶性到了3种以上颜色就没法用了。目标是要找到一种相类似的运算；我想到在2种颜色时，奇-偶性可以用二进制的异或运算来实现，即白帽子记为0，黑帽子记为1，第10个人计算前9顶帽子的异或值，将结果作为回答，让前面9个人听到；第9个人可以根据这-个值和前8顶帽的异或值推出自己的帽子颜色；依次类推。

> 异或运算只能应用于二进制，所以我想到对于n为2的整数幂(如2^m)的情况，可以把每一种颜色记为m位的二进制，采用前面的方法即可。
> 那么对于不是2的整数幂的n呢？异或运算又行不通了，要找到新的运算。
> 这时，我开始思考对于这种运算，需要具备哪些特性？我想主要有几点：
> 1.运算是二元的，可交换的；
> 2.运算的自变域和值域都是0..n-1；

> 3.二个自变量的组合有n^2种，通过运算后映射到n个值中，这种映射应该是均匀的，即每n个组合映射到1个值，且这n个二元组中的每个维度应该都有n个不同值-；(这说得很啰嗦，我的表达能力不好)

> 还是举例吧，以n=4的异或运算为例，该运算可以用以下二维表表示：
> 0 1 2 3
> 0 0 1 2 3
> 1 1 0 3 2
> 2 2 3 0 1
> 3 3 2 1 0
> 可以看到，结果为0的4个二元组(0,0) (1,1) (2,2) (3,3)，分别取两个维度中的一个来看，每个维度分别是(0,1,2,3)
> (0,1,2,3)；同样结果为1的4个二元组(0,1) (1,0) (2,3) (3,2)也同样满足这个条件，结果为2和3的也是这样。
> 把这些条件想清楚了，这个运算就很明显了，它就是模运算。

> 对于普通的n，解法如下：以0..n-1表示n种颜色，第10个人计算前9顶帽子的总和模n的值，将结果作为回答，让前面9个人听到；第9个人可以根据这个值和-前8顶帽的总和模n的值一起推出自己的帽子颜色；依次类推。

>
> 在 08-4-16，alai<ala...@gmail.com> 写道：
>
>
>
> > 用信息论来推论，理论上来说，应该是可以保证前9个人活下来，而第10个人的机会则是1/n。不过，这个方案的设计应该比较妙，我一下子还没想出来。
>

> > 在 08-4-16，陈怀兴<silw...@gmail.com> 写道：

> > > 好。接下来我们把这个题泛化一下，如果现在帽子的颜色的种数不是两种，而是三种，是不是仍然可以使得保证9个人活下来？四种呢？n种
> > > 呢？
> > > Enjoy！
> > > :-)
>
> > > 2008/4/16 alai <ala...@gmail.com>:
>

> > > 我的思路：从只能回答白或黑，也就是只能2中选1，从而联想到二进制和奇偶性。二进制一下子没想出什么好方法，奇偶性有一些提示，所以从奇偶性入手。第10个人-以他所见到的9个帽子中白帽的数量的奇偶性作答，例如大家约定白代表偶，黑代表奇，则第10个人的回答是前9个帽子中白帽的数量的奇偶。他自己有50%的机会。-第9个人听到他的回答后，结合他看到的8顶帽子中白帽的奇偶，可以知道自己的帽子的颜色，如实作答。第8个人知道9顶帽子中白帽的奇偶，加上听到第9顶帽子的颜-色，就可以知道前8顶帽子中白帽的奇偶(如果第9个人答白，则前8顶中的白帽奇偶性与第第10个人所说的相反；如果第9个人答黑，则相同)，再结合所看到前7顶-帽子中的白帽数量，也可以推出自己的帽子颜色，也如实作答。依此类推，前9个人都可以活下来，第10个人有一半机会。
>
> > > > 在 08-4-16，王小康<egmk...@gmail.com> 写道：
>
> > > > > 那么那就是说第10个给前面9个人说了答案????
> > > > > 可是人家说的只能回答:白的或者黑的.
> > > > > 你说了9个人的答案貌似要被杀头的吧??lol
>
> > > > > 在08-4-16，陈怀兴 <silw...@gmail.com> 写道：

> > > > > > A Big Hint:
> > > > > > 9个人可以保证活下来
> > > > > > :-)
>

> > > > > > 2008/4/16 hyifeng <hyif...@gmail.com>:

>
> > > > > > > 不分彼此的，碰撞可视作穿越。
>
> > > > > > > 第二题改进的只是期望，只是方法复杂一些而已。 谁有好方法？
>
> > > > > > > On 4月16日, 下午10时37分, "陈怀兴" <silw...@gmail.com> wrote:
>
> > > > > 对于第一题，几乎我问过的所有人都能给出100s这个答案，但只有1/10的人能够非常清楚的解释为什么是100s。
>
> > > > > > > > 2008/4/16 hyifeng <hyif...@gmail.com>:
>
> > > > > > > > > 第一题我的结果也是100s
>
> > > 第二题必然生存的有70%，总共有85%的生存率，每3个人中的后一个人救前两个人，自己听天由命，不知道有没有更好的方法。
>
> > > > > > > > > On 4月16日, 下午9时01分, "陈怀兴" <silw...@gmail.com> wrote:
> > > > > > > > > > 接着再好好想想。
> > > > > > > > > > 你现在的答案的改进余地非常的大噢:-)
>
> > > > > > > > > > 2008/4/16 xxmplus <xxmp...@gmail.com>:
>

> > > 第二题我是这样想的，既然帽子的颜色是随机的，那只有靠别人告诉你了，所以第10个人应该把第9个人头上帽子的颜色作为答案，这样第9个人就知道自己头上的帽子-是什么颜色了，如此除了第10个人，其他人都能活下来，第10个人就50%，赌一把吧。。。

>
> > > > > > > > > > > 2008/4/16 陈怀兴 <silw...@gmail.com>:
> > > > > > > > > > > > 今天我们思考，我们来接着做题与思考。
>
> > > > > > > > > > > > 1. 简单而但是有意思的一个题：
>

> > > 有一根1米长的木棒漂流在海上，突然从天空中降下100只蚂蚁，幸运的是它们都降在了在这根木棒上，（它们降落在木棒上的位置是随机的）。然而不幸的事发生了，-所有蚂蚁从降落的时刻起就随机朝着木棒的一个方向以1cm/s的速度行走，而当发生两只蚂蚁相碰的时候，它们就各自立即进行反方向行走。一旦有蚂蚁走到了木棒的-如何一段，这只蚂蚁就会落入大海。现在，问最少经历多少时间就可以保证所有的蚂蚁都在海里游泳了？
>
> > > > > > > > > > > > 2.如果要做出最佳答案，中等难度的一个题：
>
> > > 现在有10个人被一个魔鬼逮住了。魔鬼对于直接把人杀掉的方法不感兴趣了。于是，他就想了一个杀人的新花样。是这样的，一天晚上，魔鬼向这十个人宣布了游戏规则-，即明早他要把他们10个人排成一排，然后从一堆既有无限多的白帽子混会着无限多的黑帽子的帽子堆里为每个人随机抽取一顶帽子，给他们10个人都戴上帽子。因为-10个人是排成一排的，所以排在第10个的人可以看到前面9个人帽子的颜色，排在第9个人可以看到前面8个人的帽子的颜色，...以此类推。然后，魔鬼会从排在-第10个人开始，问他，你头上的帽子的颜色是白色还是黑色，如果答对了，就放他走；如果答错了，就被杀掉。然后同样问排在第9位的人，然后问同样问排在第8位的-人，...以此类推。在这其中，10个人所能做的只有当他被魔鬼问到的时候，答白色或者黑色。不能有超越此范围的任何行动，不然，魔鬼会把他们10个人全都杀死-。
>
> > > 现在，魔鬼给他们10个人一个晚上的时间去商量一个对策，使得他们中能存活下来的人越多越好。请问，你会有什么样的对策，请计算出按照你的对策执行时最坏的情况-下，他们中能有多少人能100%够活下来？期望能活下来的人数又是多少？

>
> > > > > > > > > > > --
> > > > > > > > > > > Any complex technology which doesn't come with documentation
> > > > > must be
> > > > > > > > > the
> > > > > > > > > > > best
> > > > > > > > > > > available.
>
> > > > > --

> > > > >http://egmkang.cnblogs.com/- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[TeEmo]

将这里的下标0、1、2、3转为二进制，其实就是异或运算了。
所以，推广到n的时候，定义（3）就直接用异或运算进行定义就OK了！

On 4月21日, 下午1时24分, pongba <pon...@gmail.com> wrote:
> 2008/4/21 googlechen <cher...@sina.com>:

[bipe...@gmail.com]

第十个人的黑白可以表示他前面两个人帽子的颜色是不是一直， 第九个个人可以根据第十个人回答， 和第八个人帽子的颜色推断。 第八根据第十和九来推
断。 一次类推。 9个人必然活下来。 第十个人50%

On 4月16日, 下午1时45分, "陈怀兴" <silw...@gmail.com> wrote:
> 今天我们思考，我们来接着做题与思考。
>

>
> 2.如果要做出最佳答案，中等难度的一个题：
>
> 现在有10个人被一个魔鬼逮住了。魔鬼对于直接把人杀掉的方法不感兴趣了。于是，他就想了一个杀人的新花样。是这样的，一天晚上，魔鬼向这十个人宣布了游戏规则，即明早他要把他们10个人排成一排，然后从一堆既有无限多的白帽子混会着无限多的黑帽子的帽子堆里为每个人随机抽取一顶帽子，给他们10个人都戴上帽子。因为10个人是排成一排的，所以排在第10个的人可以看到前面9个人帽子的颜色，排在第9个人可以看到前面8个人的帽子的颜色，...以此类推。然后，魔鬼会从排在第10个人开始，问他，你头上的帽子的颜色是白色还是黑色，如果答对了，就放他走；如果答错了，就被杀掉。然后同样问排在第9位的人，然后问同样问排在第8位的人，...以此类推。在这其中，10个人所能做的只有当他被魔鬼问到的时候，答白色或者黑色。不能有超越此范围的任何行动，不然，魔鬼会把他们10个人全都杀死。
> 现在，魔鬼给他们10个人一个晚上的时间去商量一个对策，使得他们中能存活下来的人越多越好。请问，你会有什么样的对策，请计算出按照你的对策执行时最坏的情况下，他们中能有多少人能100%够活下来？期望能活下来的人数又是多少？

[Googol Lee]

第七个人咋办？

2008/4/24 bipe...@gmail.com <bipe...@gmail.com>:

--

[hayate]

帽子这题我最大的收获，不是知道了某个方法或者思路，而是发现在更高抽象下面，具体的思路反而不那么重要了，从而把握了更本质的东西。

[bipe...@gmail.com]

写错了，第十个人应该表前面那种颜色更多。然后，下一个人可以根据前面的，和他看到的推断。

On 4月24日, 下午4时28分, "Googol Lee" <googol...@gmail.com> wrote:
> 第七个人咋办？
>
> 2008/4/24 bipeng...@gmail.com <bipeng...@gmail.com>:

[TeEmo]

YES！不断的进行层次上的抽象，我们就越来越接近于事物的本质，以后对于同类问题就会触类旁通了！

[怀宇范]

orz。。。

2008/4/21 googlechen <che...@sina.com>:

--
bool ContactMe(person you)
{
if(you.GoTo("14#344, Tsinghua") && you.Find("Fan Huaiyu"))return true;
if(you.MailTo(" dugu...@gmail.com ") || you.MailTo(" fan...@mails.tsinghua.edu.cn "))return true;
if(you.PhoneTo("13488810330") || you.PhoneTo("01062778689"))return true;
if(you.QQTo("120628812") || you.MSNTo("dugu...@hotmail.com"))return true;
if(you.NetTo(" www.cnblogs.com/duguguiyu "))return true;
return false;
}

[蹦虾]

1、应该是100s；
2、如果第10、8、6、4、2人说前面一个人的帽子颜色，那么只有1、3、5、7、9的100%能活下来，其他的只有33%左右的概率能活下来，期望
能活下来的只能是7个，因为连续两个相同颜色的概率只有1/3。
不知道是不是该怎么理解。

[蹦虾]

看了你的分析我才明白果真没那么简单。第10个人不仅应该将信息告诉第9个，而是前9个，这才是最充分的。
模运算，好方法！

[jadedrip]

用奇偶校验的思路，10个人里面最后一个50% 100%

[唐蔚]

第一道题是100s,两只蚂蚁相撞后掉头以相同速度前进可以理解为两只蚂蚁相互穿了过去，这时只要计算刚开始的时候某只蚂蚁落下去的最长时间就可以了。
假设刚开始时一直蚂蚁落在最右边的头上且向左边前进，故为100/1=100s.

On Apr 16, 1:52 pm, hyifeng <hyif...@gmail.com> wrote:
> 笨了，是可以改进的。

>
> On 4月16日, 下午9时49分, hyifeng <hyif...@gmail.com> wrote:
>
> > 第一题我的结果也是100s
> > 第二题必然生存的有70%，总共有85%的生存率，每3个人中的后一个人救前两个人，自己听天由命，不知道有没有更好的方法。
>
> > On 4月16日, 下午9时01分, "陈怀兴" <silw...@gmail.com> wrote:
>
> > > 接着再好好想想。
> > > 你现在的答案的改进余地非常的大噢:-)
>
> > > 2008/4/16 xxmplus <xxmp...@gmail.com>:
>

> > > > 第二题我是这样想的，既然帽子的颜色是随机的，那只有靠别人告诉你了，所以第10个人应该把第9个人头上帽子的颜色作为答案，这样第9个人就知道自己头上的帽子是什么颜色了，如此除了第10个人，其他人都能活下来，第10个人就50%，赌一把吧。。。

>
> > > > 2008/4/16 陈怀兴 <silw...@gmail.com>:
> > > > > 今天我们思考，我们来接着做题与思考。
>
> > > > > 1. 简单而但是有意思的一个题：
>

> > > > 有一根1米长的木棒漂流在海上，突然从天空中降下100只蚂蚁，幸运的是它们都降在了在这根木棒上，（它们降落在木棒上的位置是随机的）。然而不幸的事发生了，所有蚂蚁从降落的时刻起就随机朝着木棒的一个方向以1cm/s的速度行走，而当发生两只蚂蚁相碰的时候，它们就各自立即进行反方向行走。一旦有蚂蚁走到了木棒的如何一段，这只蚂蚁就会落入大海。现在，问最少经历多少时间就可以保证所有的蚂蚁都在海里游泳了？
>

> > > > > 2.如果要做出最佳答案，中等难度的一个题：
>
> > > > 现在有10个人被一个魔鬼逮住了。魔鬼对于直接把人杀掉的方法不感兴趣了。于是，他就想了一个杀人的新花样。是这样的，一天晚上，魔鬼向这十个人宣布了游戏规则，即明早他要把他们10个人排成一排，然后从一堆既有无限多的白帽子混会着无限多的黑帽子的帽子堆里为每个人随机抽取一顶帽子，给他们10个人都戴上帽子。因为10个人是排成一排的，所以排在第10个的人可以看到前面9个人帽子的颜色，排在第9个人可以看到前面8个人的帽子的颜色，...以此类推。然后，魔鬼会从排在第10个人开始，问他，你头上的帽子的颜色是白色还是黑色，如果答对了，就放他走；如果答错了，就被杀掉。然后同样问排在第9位的人，然后问同样问排在第8位的人，...以此类推。在这其中，10个人所能做的只有当他被魔鬼问到的时候，答白色或者黑色。不能有超越此范围的任何行动，不然，魔鬼会把他们10个人全都杀死。
>
> > > > 现在，魔鬼给他们10个人一个晚上的时间去商量一个对策，使得他们中能存活下来的人越多越好。请问，你会有什么样的对策，请计算出按照你的对策执行时最坏的情况下，他们中能有多少人能100%够活下来？期望能活下来的人数又是多少？
>
> > > > --