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