首页 > 分享 > 病狗问题

病狗问题

萌宠菠菠乐园
2024-11-21 02:44

有50家人家，每家一条狗。有一天警察通知，50条狗当中有病狗，行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病，而不能看自己家的狗，如果判断出自己家的狗病了，就必须当天一枪打死自己家的狗。结果，第一天没有枪声，第二天没有枪声，第三天开始一阵枪响，问：一共死了几条狗？
我们先从一条病狗说起。
主人的集合为{A0,A1,…A50}
狗的集合为{a1,a2,…a50}
1.假设有一条病狗，不妨设为a1。那么经过在第一天，每个人都可以看到那条病狗，除了病狗的主人A1。
A1这样分析：哇，周围的狗竟然都是正常的，而这里一定有病狗，看来只有我家的旺财生病了，哎，杀它吧。于是，枪声会在第一天想起。注意此时，其它狗主人看到a1的狗生病，但是无法确定自己的狗是不是正常的，自己的狗也许是正常的，也许是生病的。但是如果自己的狗是病狗，那么A1就不会枪杀a1了，因为A1会看见自家的狗是病狗，A1无法确定自己的狗是病狗，当然不会在第一天杀死a1。但是现在a1死了，所所以证明自己家的狗是正常的，杀戮停止！

2.假设有两条病狗。不妨设为a1,a2。第一天，A1,A2分别看到病狗a2,a1。{A3,…A50}则看到病狗a1,a2。A1，A2知道至少有一条病狗，{A3,…A50}知道至少有2条病狗。所有的人都会在第一天等待，第一天并不会响起枪声，没人能证明自己的狗生病了。第二天到了，A1，A2第一天没有枪声，明白了，病狗不止一条：有2条，而自己只看到1条病狗，所以自己的狗是病狗，所以，枪声响起了：a1,a2被杀。而此时， {A3,…A50}松了口气，原来只有2条病狗，自己的狗是健康的。如果自己的狗是病狗，A1，A2就不会杀自家的狗了（分析类似于1中的红色字体）。
3.假设有3条病狗，不妨设为a1,a2,a3。第一天，A1,A2,A3分别看到病狗{a2,a3},{a1,a3},{a1,a2}。 {A4,…A50}则看到病狗a1,a2,a3。A1,A2,A3知道至少有2条病狗，{A4,…A50}知道至少有3条病狗。第一天并不会响起枪声，没人能证明自己的狗生病了。第二天并不会响起枪声，同样没人能证明自己的狗生病了。第三天终于来了。经过前两天，A1,A2,A3终于知道，原来至少有3条病狗（如果只有两条的话，第二天枪声就要响起）。而自己值看到2条病狗，所以剩下的那只病狗一定是自己的。所以，A1,A2,A3分别枪杀了自己的狗。而{A4,…A50}看到自己看到的病狗被杀后，就不会怀疑自己的狗是病狗：如果有自家的狗也是病狗，A1,A2,A3就不会枪杀他们家的狗。（分析类似于1中的红色字体）
照着这样分析下去，可以知道，第k天枪声响起，那么就有k条病狗