信息压缩
信息压缩一种技术是否应用于逻辑谜题这就要求人们压缩信息来有效沟通。这类问题的典型例子包括使用天平和最小数量的称重来找到奇怪重量的硬币,以及人们把帽子戴在头上排成一排,其中一些人或所有人都必须猜对帽子的颜色才能生存。
计数-称重谜题
在解决逻辑难题时,组合思考通常是有用的:考虑可能结果的空间大小,然后考虑如何在给定的问题工具下区分这些结果。这种分析通常会对可能的解决方案给出一些限制,但通常也会为成功的解决方案指明方向。
有八枚看起来一模一样的硬币;其中一枚硬币是奇数,已知比其他硬币重。用没有称量的双锅秤来鉴别假硬币最少需要称量多少次?
从给定的硬币中选择两组,每组三枚硬币,并将它们放在天平的相对杯子上。如果它们的重量相同,那么假硬币就在剩下的两枚硬币中,称量这两枚硬币就可以确定较重的假硬币。如果第一次称量没有平衡,较重的假硬币就在三个较重的硬币中。取其中任意两个,分别放在秤的两个杯子上。如果它们的重量相同,那么较重的那一组中的第三枚硬币就是假的;如果重量不一样,重的那个就是假的。因此,答案是最多 .但 也是最小数量:称重只有在每一边的硬币数量是平衡的情况下才提供有意义的信息,并且很容易检查两组1、2、3或4个硬币的称重并不总是会找到较重的硬币。
请注意,第一次称重将八种可能的结果分为三组:如果它们的重量相同,则有两种可能性,如果其中一种更重,则两侧各有三种可能性。
解决问题的想法:
1.计算总结果。
2.考虑一个过程中的步骤是如何将结果分组的。
3.限制步数。
4.构造一个尽可能接近边界的过程。
下面这个比较难的问题就是这些思想在实践中的一个例子。
有十二枚看起来一模一样的硬币;其中一枚硬币是奇数,已知比其他硬币更重或更轻。如果使用没有砝码的双盘天平,要鉴别硬币的重量和重量,最少需要称量多少次?
与其深入研究多个案例,不如先考虑流程。每一步我们都挑选一些硬币并称量。有三种情况:左边更重,右边更重,或者它们平衡。问题一开始有多少种不同的结果?解空间有 不同的结果:12枚硬币中的任何一枚都可以是奇数,它可以更重或更轻。(这是第一步。)
这些 结果根据三种情况分为三组。这个问题的目标是根据加权结果将结果分成组,直到每个组只包含一个结果。不同组的数量最多 ,在那里 是称量的数量,这样吗 ,所以 .这表明至少要称重三次才能识别硬币。(这是第二步和第三步。)
这一分析也为最佳程序(步骤4)提供了线索。在每个阶段,尝试安排权重,以便三种情况将可能的结果分成大致相同大小的组。
为了简单起见,给硬币贴上标签 通过 .现在来称重 对集团 这三个案例将结果分为三组,每组八人。如果 是比较重的,那么这八个结果是四个中的哪一个呢 是重的,而这四个在哪一个呢 就是光。八种情况下的结果 打火机是相似但相反的吗,当它们平衡时的八个结果是四个硬币中的一个吗 不是重就是轻。
如果硬币在第一次称量时平衡,第二次称量时应平衡 vs。 .如果它们平衡,那么 是奇数的硬币,并权衡它对吗 决定它是重还是轻。如果 也更重 或 是重的还是 就是光。要确定这三者中哪一个是正确的,权衡一下 vs。 .同样的事情也适用于“heavy”和“light”的颠倒if 是打火机。
注意,第二次称量将 结果分为 而且 ,即最优分割。
如果(不失一般性) 更重,更重 反对 下一个。如果它们平衡,那么两者都可以 是轻还是 是轻的,而第三重的呢 vs。 将决定哪一个。如果 也更重 很重, 是重的,还是 是轻的,我们可以称吗 vs。 来确定哪个。类似的想法也适用于 是重的。同样,权衡将八个结果分成 而且 .
这里描述的程序将用三种加权来解决问题,这已被证明是可能的最小值;所以答案是
你有一个独特的三盘天平,用来测量硬币的重量。顾名思义,这个天平有三个平底锅。每个平底锅可以装任意数量的硬币,然后你可以按一个按钮打开天平。如果三个平底锅的重量不同,秤会告诉你哪个平底锅的重量是2 最重的重量(即既不是最重也不是最轻的平底锅)。但是,如果任意两个平底锅的重量相同,则称将显示“ERROR”(因为没有唯一的2 最重的重量)。在此之后,天平关闭,你可以卸载和重新装载平底锅以备下次使用。
在一堆64枚硬币中,除了一枚之外,其他硬币的重量都相同;奇数重一些。你想把这个较重的硬币按键次数少(余额的使用)尽可能多。在最佳策略下,在最坏的情况下你需要按多少个按钮?
边界和极限-帽子问题
总结上一节中解决问题的想法的一种方法是,给出解决方案“难度”的下限可以使最佳解决方案更清晰。下面是一个不同语境下的类似例子。
提示:请注意,如果游戏重复多次,我们将正确猜测和错误猜测的总数制成表格,这些数字将趋于大致相等,因为任何一个特定猜测正确的几率是 .所以对于球员来说要赢更多 在这种情况下,他们的策略必须包括所有人在错的时候都猜错,在对的时候只有一个人猜对。这样,错误的猜测聚集在一起,正确的猜测分散开来。
解决问题的想法:
1.认为组合;计数结果。
2.考虑多次试验的效果,每一种结果都有相同的代表性。注意,个人猜测概率与策略无关。
3.使用个别概率来决定“在理想的情况下”各种试验之间如何分布猜测。
4.构造一个策略,相应地分配这些猜测。
下面是这些想法在实践中的一个例子。
这是一个稍作修改的版本这个讨论.
假设有 囚犯。典狱长有很多帽子 他的衣柜里有不同的颜色。典狱长告诉囚犯们,他将从他的衣柜里随机为每个囚犯挑选一顶帽子 帽子可能有的颜色)。请注意,他选择的帽子可能都是相同的颜色,或者都是不同的颜色。每个囚犯都能看到别人的帽子,但看不到自己的。一旦帽子戴上,囚犯们要猜出自己帽子的颜色(把它写在一张纸上)。如果至少有一人猜对了,囚犯就会被释放。猜错没有惩罚。
囚犯们有短暂的休息时间来制定策略。一旦他们进入房间,就不允许任何形式的交流或移动。如果他们玩得最优,他们获得自由的概率是多少?
与前面的帽子问题一样,如果试验全部重复,考虑正确和错误猜测的总数 (计算它们是第一步)。每个囚犯都有一个 猜对的机会,确实有 囚犯,所以平均会有一个正确的猜测(步骤2)。这里的优先级与上面的问题相反;我们的目标是将正确的猜测均匀地分布开来,这样在每个监狱里就有一个囚犯猜对了 不同的情况。如果能做到这一点,囚犯就能保证在任何情况下都能获得自由。(这是第三步。)
在其他问题中,看和是有用的,事实上也有 颜色让人看起来很摩登 在某种程度上。假设我们重新标记颜色 .然后犯人 你能猜出所有帽子(包括他的)的总数是多少吗 国防部 .这将转化为一个独特的帽子颜色猜测;如果囚犯看到的帽子总数是 ,然后囚犯猜他帽子的颜色是 国防部 .并且只有一个囚犯是对的 ,所以只有一个囚犯能猜出正确的帽子颜色。所以它们自由的概率是 .
就像硬币问题一样,重点是对边界和规模的全面考虑为构建最佳策略提供了蓝图。
信息传输-帽子问题
在许多其他逻辑谜题中,困难在于在参与者之间的交流受到严格限制的情况下,如何成功地传递信息。有时信息是通过停顿传递的,在这种情况下,可以根据另一个参与者的不作为得出推断。其他时候,并非每个参与者都是完全理性的;如果每个参与者都是完全理性的,这将被称为K-level思考.
有时,对可传输信息量的严格限制有助于指示正确的解决方案,这与前一节中的问题类似。也就是说,策略的选择受到问题条件的限制,可以用来给出任何策略成功率的上限。
解决问题的策略:
1.决定参与者之间可以传递多少信息。
2.给出基于步骤1的任何策略的成功率的上限。
3.在前两步中找到一个尽可能接近边界的解。
一个赤裸裸的疯狂国王说 聪明的囚犯知道他要让他们排成一排,每人头上戴一顶红色或蓝色的帽子。一旦排好队,他们不能互相交流,也不能试图向后看,也不能脱下自己的帽子。他们能看到前面所有的帽子,但看不到自己的帽子和后面的帽子,尽管他们能听到后面所有人的答案。
国王会从最后一个囚犯开始问:“你的帽子是什么颜色的?”囚犯只被允许回答“红”或“蓝”,仅此而已。如果答案不正确,囚犯将被处死。如果答案是正确的,那么囚犯可以活着,但必须保持绝对的沉默。然后,国王将转向第二个最后一个囚犯,重复这个问题,以此类推。
在他们排成一行之前,国王明确表示,如果有人违反了规则,所有人都将被处死。当囚犯们在排队前互相商量几分钟时,国王在旁边偷听,以确保他们除了猜测红或蓝之外,不会想出任何计划来交流。
能保证得救的最大预期人数是多少?
最好的预期生存率必须是 的 囚犯;第一个囚犯不知道他的帽子,他会活下来 的时间,但随后的囚犯将每个人从第一个囚犯的选择中至少得到一个比特的信息。注意,囚犯不能同时保证他们的生存和传递任何信息,除了他们自己的帽子颜色;如果他们知道帽子的颜色,他们的选择是被迫的。但是听到后面每个囚犯帽子的颜色仍然会对前面的囚犯有所帮助。所以每个囚犯最多只能传送一个比特的信息。
一个位的存在表明,我们看帽子的颜色mod .假设在最后面的囚犯(叫他# 在他面前的囚犯# 等等),如果他看到奇数个红帽子,他就说红色,如果他看到偶数个红帽子,他就说蓝色。
例如,如果# 说红色,意思是他看到前面有奇数顶红帽子,然后是# 数他面前有多少顶红帽子。如果他数的是偶数顶红帽子,他就知道他戴的是一顶红帽子。相反,如果他数面前有奇数顶红帽子,他就知道自己戴的是一顶蓝帽子。同样的策略也适用于# 除了他将不得不考虑什么# 和# 说。
不幸的是,这意味着# 有一个 %的生存机会,但它保证了其他人的生存。所以所有 他们中的每一个都能保证存活,这就给出了总体的预期存活率 %,我们之前认为是最好的。