讨论题：关于100囚犯

新用户 · 发表于 2005-1-13 00:45:21

100个死囚，关在100个单人牢房，牢房排成一个圆圈。国王的特赦令是：每个囚犯早上必须在后窗挂起红旗或者黄旗。如果有连续100天，第k天只有第k间牢房挂起红旗，其他全是黄旗，就释放所有死囚。如果三年后还没完成，所有人全部拉出去砍了。

囚犯可以先开一个会，会后所有人会被随机分到一间牢房，而且不知道自己的房间号。为了阻止囚犯们得到特赦，囚犯们并不是同一天被关进自己的牢房，而是先被麻醉，又关进不见天日的小黑屋一段日子，所以每个囚犯都不知道自己到底是哪一天被送进自己的单人牢房。

每个囚犯进自己牢房的第一天会得到一个数,范围在0-100之间（可能有人得到相同的数）。囚犯相互之间唯一的交流方法是每天晚饭时每人可以报一个数，这个数与他上一次得到的或者报的数差距不能超过10----（数是循环的，0和100的差距是1），由看守在熄灯时给他的左边邻居，如果某间牢房里暂时没有犯人，看守会编一个数传下去，由于囚犯开会是被监视的，所以看守可以利用这个机会进行破坏。请问囚犯们怎么办？注：三年的期限是从所有囚犯都进入自己的牢房开始算。

呵呵 · 发表于 2005-1-13 02:14:39

囚犯开会时选出一个囚长，他的作用是：

从进自己牢房的第一天起，每隔100天给他的左边邻居一个偶数，其余时间都给奇数。

其它囚犯都在传给自己偶数的时候挂起红旗，奇数则挂起黄旗。同时把传给自己的数传下去。（当然要修改到自己可以报的范围内）。

www.ddhw.com

husonghu · 发表于 2005-1-13 10:07:42

1.那开始时从其他所有人传出的数也必须是奇数？
2.如何防止看守的破坏？

新用户 · 发表于 2005-1-13 18:53:05

我开始也认为呵呵的解法行不通，疑问和你的一样，但是如果你仔细想想，就会发现，看守破坏不是问题。

他破坏就让他去破坏，总有一天，犯人到齐了，看守就破坏不了了。也就是说，持续这样下去，我们总会遇到一个连续的100天，会满足要求。

现在的问题是，呵呵的解答很简单（不是很容易想到，但是看了答案觉得不难）。我想也许题目本身有误，应该做些修改，让它难些。

原贴：

文章来源: husonghu® 于 2005-1-13 2:7:42
标题：没时间细想；可能没正确理解呵呵的意思。

1.那开始时从其他所有人传出的数也必须是奇数？
2.如何防止看守的破坏？

呵呵 · 发表于 2005-1-13 18:56:34

1、其他所有人传出的数也必须是奇数？
不必，其他所有人只需把传给自己的数不改变奇偶性传下去就行了。同时根据传给自己的数的奇偶性挂起红旗或黄旗。囚长则从第一天起，每隔100天传偶数（同时挂起红旗），其余时间都传奇数（同时挂起黄旗）。
2、如何防止看守的破坏？

看守的破坏只在所有囚犯都进入自己的牢房之前起作用，之后便无法破坏了（如果所有囚犯都进入自己的牢房之后，看守能任意改变所传的数，传数就没有意义了）。

基本思路是这样的：

把偶数看作令牌，得到令牌的挂起红旗，否则挂起黄旗。囚长的作用是产生自己的令牌并过滤掉别人的令牌（包括看守假传的）。所有囚犯都进入自己的牢房那天起，尽管此时可能有很多令牌，但此时看守已不能改变令牌的数量和状态，只有囚长可以。最多100天后，囚长可以保证只有一个自己发出的令牌在传递（其他的都被囚长过滤掉了），此时每天只有一个得到令牌的囚犯挂起红旗，其余都挂起黄旗。再过最多200天后，就可以保证有连续100天，第k天只有第k间牢房挂起红旗，其他全是黄旗。所以最多300天就可以了。

不知对题目的理解对不对。

呵呵 · 发表于 2005-1-13 19:46:54

修改难些很简单。只要规定第K间牢房的右边是第K+1间就可以了。只是不知是否有解。

		自动登录	找回密码
密码			立即注册

动态微博

讨论题：关于100囚犯

回复：讨论题：关于100囚犯

没时间细想；可能没正确理解呵呵的意思。

回复：没时间细想；可能没正确理解呵呵的意思。

回复：没时间细想；可能没正确理解呵呵的意思。

回复：回复：没时间细想；可能没正确理解呵呵的意思。