戴帽子问题的数学证明

戴帽子问的数学 戴帽子问题的数学证明(充分体现数学归纳法的强大) 教室里有100个孩子,每人头上都顶着一个小帽子,大多数都是白色的帽子,有12顶是红色的帽子. 孩子们不知道教室里共有多少人头上是红帽子,也不知道自己头上的帽子颜色.但她能看到其她99人头上的帽子颜色. 首先假设这些孩子都拥有完美的逻辑推断能力. 这时候,一个老师走进来,他先说了句废话: "你们当中至少有一个人头上带的是红帽子"(孩子都能看到别人头上的帽子颜色,显然是废话...) 然后对大家说: "知道自己头上的帽子是红帽子的同学请举手~ 第一遍问了后没人举手,第二遍还是没有人举手 请问很多遍后,会有人举手么? 如果会,请问是第几遍?(其实也就100,11,12,13,87,88,89,100.101112,99,160等等这么些个可能). 为什么? 情况二: 如果老师没说那句废话,那么会是第几遍才有人举手,几个人举?(其实也就100,11,12,13,87,88,89,112,101,100,99,160等等这么些个可能). 为什么? ===========华丽的分割线============== 首先说一个事情，由于学生们都是逻辑完美，所以白帽众是不会出错，所以他们会从头到尾没有任何反应，所以对于红帽君可以观察的对象，就只有他能看到的红帽。 下面只考虑戴红帽子的人数。 先假设老师说了那句“废话”:至少有一个人戴帽子 现在来证明:在一个人看到k顶红帽子的时候，最迟在第k+1轮的时候会知道(回答)自己头上的是红帽或者白帽。 现在用数学归纳法 1.k=0，由于全场至少一定红帽，但某人又看不到，所以只可能在自己头上，所以这个人会在第1轮问的时候回答。 k=1，一个人看见只有另一个人带着红帽，那么问题就是:自己带着什么,假如自己带着 白色的话，那么第一轮问的时候，眼前那个带红帽的就会回答自己是红色;反之，如果没有回答，那么就可以推断自己头上也是红色。所以最迟在2轮问的时候就会回答自己戴红帽。 2.假设对于所有k<=n，命题都成立，现在考察当一个人看到n+1顶红帽时候的情况。 这个人可以假设自己是带白色，如果这样的话，他面前任意一个带红帽的人都只能看到n顶红帽，根据归纳的假设，这个红帽君会在n+1轮说出自己是红帽。所以这个人就耐心等待n+1轮，如果红帽众在n+1轮纷纷恍然大悟，那么就说明他们只看到n顶红帽，于是自己就是戴白色。反之，如果这堆人n+1轮都没有反应，那么就说明他们也看到n+1顶红帽，也就说自己也带着红帽。于是，他会在n+2轮问的时候回答自己戴红帽。 3.因此，对于任意自然数k，命题成立。 这就是我们的第一个结论:在一个人看到k顶红帽子的时候，最迟在第k+1轮的时候会知道(回答)自己头上的是红帽或者白帽。 具体点说，一个戴红帽的看见k顶红帽，他最迟会在k+1轮回答自己戴红帽。 看到这里可能会有人问，你怎么知道别人是怎么想的，你又如何知道这个思路是最快的方法, 这就是为什么我在加了“最迟”两个字，因为我没有证明k+1轮是最优解。 现在来证明k+1轮是最优。 也就是:一个戴红帽的看见k顶红帽，他最快，并且会在k+1轮回答自己戴红帽。 再次运用归纳法证明:一个带着红帽的并看见k顶红帽的人，不可能在k+1轮之前回答/知道自己头上的帽子颜色。 1.k=0 -_-好吧，0轮是不存在的东西，虽然也算证了...不过还是从1开始证吧 k=1 假如一个人看到1顶红帽，那么他可以在第k(=1)就知道自己带什么颜色吗, 是否定的。反证法，假如红帽A君在看见一顶红帽的情况下，不用考察其他人的回答，直接第一次问的时候就知道自己戴红帽。那么在另一个情况:全场只有一顶红帽的情况。任意一个白帽君都和之前的红帽A君接收到完全一样的信息，那么他们理应作出同 样的判断，但这是矛盾的，因为他们实际上戴的是不同颜色的帽子。所以戴红帽的人不可能在第一轮就知道自己戴红帽。同理，带白帽的人也一样。 2.假设命题在k<=n的时候成立。 现在考察一个看到n+1顶红帽的人。 反证法证明这个人不可能在前n+1轮内知道自己带什么颜色的帽子。 假设有某种思考方法可以让看到n+1个红帽的红帽君 m轮的时候知道自己的颜色(m<=n+1 反证法假设) 要注意的一点是，红帽众“恍然大悟”的时间都是一样的，所以他们会在同一轮一起自爆，在此之前，全场都是一直沉默。 这意味着，一个人可以通过看到n+1个红帽沉默m-1轮得出自己是红色的结论。(m-1<=n) 考察全场上只有n+1红帽的情况，对于其中的红帽众，他们只能看到n顶红帽，根据归纳假设，他们在前n轮式一直沉默。 而对于其中的白帽，他们会看到n+1个红帽，沉默了n轮。(n>=m-1) 根据上面的假设，他们会在m-1轮后得出自己是红色这一结论。矛盾～ 所以没有一种思考方式可以让一个戴红帽的在看到n+1顶红帽后n轮之内知道自己的颜色。 3.所以对于任意自然数k，命题成立。 这样我们就得到第二个结论:一个戴红帽的看见k顶红帽，他最快能在k+1轮回答自己戴红帽。 由于我们已经证明了(结论1)一个戴红帽的看见k顶红帽，他最迟会在k+1轮回答自己戴红帽。 所以我们得出:一个戴红帽的看见k顶红帽，他最快，并且会在k+1轮回答自己戴红帽 推论:假如老师一开始那句话为“至少有m个人带着红帽”，那么一个戴红帽的看见k顶红帽的情况下，他最快，会在k+2-m轮回答自己带着红帽。 类似的做法，同样运用归纳法，这里不详述。 接下来是部分人比较关心的问题，老师一开始那句“至少一个人带着红帽”是不是废话, 下面来证明，如果没有老师这句话，所有人会一直沉默下去。 同样运用归纳法，证明，看见k顶红帽的人永远无法确定自己带着什么颜色的帽子 1.k=0 一个人看到的全是白帽，由于他们都是逻辑完美，这堆白帽众永远都是沉默。 反证法，考察全场都是白帽中的一人 和全场只有一个红帽时的那个红帽君，他们接收到信息是一样的----四周全白，全沉默。所以他们要么能做出相同的判断(不可能)，要么都不能判断) 2.假设命题在k<=n的时候成立 反证法，假设某个看到n+1顶红帽的红帽君会在x轮发现自己是带红帽的。 之前说过，红帽众都是团体行动，在他们自爆之前，全场都是一直沉默。 这意味着，一个人在看到n+1顶红帽 沉默 x-1 轮之后得出 自己是红色的结论。 类似方法，我们设一个新场景，全场只有n+1顶红帽，对于其中的某个红帽君，他只看到n顶红帽，根据归纳假设，他永远都无法判断自己的颜色，所以他会保持沉默。那对于其中的白帽君，他们看到了n+1顶红帽，并沉默了x-1轮，他们因此会在x轮得出自己是红帽的结论。 矛盾～ 所以看到n+1顶红帽的红帽君永远都无法判断自己的颜色。 3.对于任意自然数k,看见k顶红帽的红帽君永远都无法判断自己的颜色。 至于看见n顶红帽的白帽君，证明方法类似:归纳，反证法，转换场景。 我们得出结论:对于任意自然数k,看见k顶红帽的人永远都无法判断自己的颜色