Finding the Counterfeit


题目

你有一个天平和12枚硬币，其中11枚是真币，重量相同；但有一枚是假币，且它比其他硬币要么更轻，要么更重。你能否在三次称重内确定哪一枚是假币，并判断它是较轻还是较重？

分析

这里有一个洞见。每次称重可能得到三个结果：两边相等，左边重，右边重。如果称3次，可以得到\(3^3=27\)种不同的结果。而总共有12枚硬币，每个硬币都可能是假币（12种可能），而假币可能轻也可能重（2种可能），总共是24种可能。因此，可以用3次称重解决问题。1

下面给出一个常见且可行的三次称重策略（按编号1–12标记硬币）。第一步将问题规模缩小至4枚，剩下两步用于判别哪一枚以及轻重。

记硬币为\(1,2,\dots,12\)。

第一次称重：称1,2,3,4与5,6,7,8。

  • 若天平平衡，则1–8均为真币，假币在集合\(\{9,10,11,12\}\)中。此时第二次称重：称 9,10 与 11,1（其中 1 为已知真币）。——这里需要引入一枚已经判定是真币的硬币，也就是1。

    • 若第二次称重也平衡，则假币为12；第三次称重称12与1可判断12为轻还是重。
    • 若第二次称重左边偏重（9+10 > 11+1），则三种可能：9为重、10为重、或11为轻。第三次称重令9与10相互称：若9=10则11为轻；若9>10则9为重；若9<10则10为重。
    • 若第二次称重左边偏轻（9+10 < 11+1），则三种可能对称：9为轻、10为轻、或11为重。第三次称重同上（9 vs 10）即可区分。

  • 若第一次称重不平衡，下面给出完整的判别表（先给左重的情况；若第一次右重，则按对称规则把“重/轻”和左右交换即可）。

    • 假设第一次为左重（即1,2,3,4较重），则候选为：1–4中某枚为重，或5–8中某枚为轻。第二次称重：称1,2,5对3,6,9。

    • 若第二次平衡：则参与称量的硬币均为真币，结合第一次可知假币在集合\(\{4,7,8\}\)中，且为4重或7/8轻。第三次称重：称7与8。若7=8则4为重；若7<8则7为轻；若7>8则8为轻。

    • 若第二次左重（1,2,5较重）：结合第一次信息，可推出可能为1重、2重或6轻。第三次称重：称1与2。若1=2则6为轻；若1>2则1为重；若1<2则2为重。

    • 若第二次右重（1,2,5较轻）：结合第一次信息，可推出可能为3重或5轻。第三次称重：称5与6。若5=6则3为重；若5<6则5为轻。

  • 若第一次称重为右重（即 5,6,7,8 较重），对称地使用相同的第二次称重（1,2,5对3,6,9）并对结果作对称解释：候选为 1–4 中某枚为轻，或 5–8 中某枚为重。

    • 若第二次平衡：假币在集合\(\{4,7,8\}\)中，且为4轻或7/8重。第三次称重：称7与8。若7=8则4为轻；若7>8则7为重；若7<8则8为重。
    • 若第二次左重（1,2,5较重）：结合第一次信息，可推出可能为5重或3轻。第三次称重：称5与6。若5=6则3为轻；若5>6则5为重。
    • 若第二次右重（1,2,5较轻）：结合第一次信息，可推出可能为1轻、2轻或6重。第三次称重：称1与2。若1=2则6为重；若1<2则1为轻；若1>2则2为轻。

说明与思路：上面对第一次称重平衡的分支给出了完整的三步判别流程；对第一次不平衡的分支给出了完整的判别流程。该方法基于每次称重有三种结果（左重、平衡、右重），称3次可得到\(3^3=27\)种结果，足以区分12枚硬币在“轻/重”两种状态下的\(12\times2=24\)种情况。通过合理设计三次称重的置换（即每枚硬币在三次称重中的“出现/位置/方向”编码唯一化），即可确保成功。

Mermaid 决策树

总览

flowchart TB S([开始：12 枚硬币]) --> W1[第一次称重：1 2 3 4 对 5 6 7 8] W1 -->|平衡| B[进入图 A] W1 -->|左重| L[进入图 B] W1 -->|右重| R[进入图 C]

图 A：第一次平衡分支

flowchart TB A0([第一次平衡]) --> A1[候选：9 10 11 12] A1 --> A2[第二次称重：9 10 对 11 和真币 1] A2 -->|平衡| A3[第三次称重：12 对 1] A3 -->|左重| A12H([12 偏重]) A3 -->|左轻| A12L([12 偏轻]) A2 -->|左重| A4[第三次称重：9 对 10] A4 -->|平衡| A11L([11 偏轻]) A4 -->|左重| A9H([9 偏重]) A4 -->|左轻| A10H([10 偏重]) A2 -->|左轻| A5[第三次称重：9 对 10] A5 -->|平衡| A11H([11 偏重]) A5 -->|左重| A10L([10 偏轻]) A5 -->|左轻| A9L([9 偏轻])

图 B：第一次左重分支

flowchart TB B0([第一次左重]) --> B1[候选：1 到 4 偏重，或 5 到 8 偏轻] B1 --> B2[第二次称重：1 2 5 对 3 6 9] B2 -->|平衡| B3[第三次称重：7 对 8] B3 -->|平衡| B4H([4 偏重]) B3 -->|左轻| B7L([7 偏轻]) B3 -->|左重| B8L([8 偏轻]) B2 -->|左重| B4[第三次称重：1 对 2] B4 -->|平衡| B6L([6 偏轻]) B4 -->|左重| B1H([1 偏重]) B4 -->|左轻| B2H([2 偏重]) B2 -->|右重| B5[第三次称重：5 对 6] B5 -->|平衡| B3H([3 偏重]) B5 -->|左轻| B5L([5 偏轻])

图 C：第一次右重分支

flowchart TB C0([第一次右重]) --> C1[候选：1 到 4 偏轻，或 5 到 8 偏重] C1 --> C2[第二次称重：1 2 5 对 3 6 9] C2 -->|平衡| C3[第三次称重：7 对 8] C3 -->|平衡| C4L([4 偏轻]) C3 -->|左重| C7H([7 偏重]) C3 -->|左轻| C8H([8 偏重]) C2 -->|左重| C4[第三次称重：5 对 6] C4 -->|平衡| C3L([3 偏轻]) C4 -->|左重| C5H([5 偏重]) C2 -->|右重| C5[第三次称重：1 对 2] C5 -->|平衡| C6H([6 偏重]) C5 -->|左轻| C1L([1 偏轻]) C5 -->|左重| C2L([2 偏轻])

  1. 在经典设定下（无额外已知真币），三次称重最多可区分12枚硬币的轻/重异常；13枚通常无法保证在三次内完成。 ↩

Next