智力题:12 硬币问题


题目描述:

现在有 12 枚硬币,其中有 1 枚是假币,它的重量和真币不同,不知道它是重了还是轻了,你只有一个没有砝码的天平,最少称重几次可以找出有问题的硬币并且知道它的轻重?

题目分析:

  一次测量有左边重(>)、左边轻(<)、两边相等(=)3 种结果,而 12 枚硬币都有可能是那一枚假币,包括它们的轻重一共有 $12\times2=24$ 种情况。则理论上来说,至少需要 3 次称重,一共产生 $3^3=27$ 个分支,才有可能对每一种情况进行分类。事实上答案也确实是 3 次。我们将 12 枚硬币编号为 1 ~ 12。下面是操作的步骤。

  • 左边放上 1 2 3 4,右边放上 5 6 7 8
  • 若 1 2 3 4 = 5 6 7 8
    • 假币在 9 10 11 12 之间,左边放上 9 10 11,右边放上 1 2 3
    • 若 9 10 11 = 1 2 3
      • 假币是 12,左边放上 1,右边放上 12
      • 1 > 12,假币是 12 且轻
      • 1 < 12,假币是 12 且重
    • 若 9 10 11 > 1 2 3
      • 假币在 9 10 11 之间,并且假币重,左边放上 9,右边放上 10
      • 9 = 10,假币是 11 且重
      • 9 > 10,假币是 9 且重
      • 9 < 10,假币是 10 且重
    • 若 9 10 11 < 1 2 3
      • 假币在 9 10 11 之间,并且假币轻,左边放上 9,右边放上 10
      • 9 = 10,假币是 11 且轻
      • 9 > 10,假币是 10 且轻
      • 9 < 10,假币是 9 且轻
  • 若 1 2 3 4 > 5 6 7 8
    • 可知 9 10 11 12 为真,左边放上 1 2 3 5,右边放上 4 9 10 11
    • 若 1 2 3 5 = 4 9 10 11
      • 假币在 6 7 8 之间,并且假币轻,左边放上 6,右边放上 7
      • 6 = 7,假币是 8 且轻
      • 6 > 7,假币是 7 且轻
      • 6 < 7,假币是 6 且轻
    • 若 1 2 3 5 > 4 9 10 11
      • 可以确定 6 7 8 是真,拿 6 7 8 换掉 9 10 11,等式变成 1 2 3 5 > 4 6 7 8,结合第一次称重的结果 1 2 3 4 > 5 6 7 8,可以知道 4 和 5 互换没有影响,4 5 也是真。假币在 1 2 3 里面,并且假币重。左边放上 1,右边放上 2
      • 1 = 2,假币是 3 且重
      • 1 > 2,假币是 1 且重
      • 1 < 2,假币是 2 且重
    • 若 1 2 3 5 < 4 9 10 11
      • 可以确定 6 7 8 是真,同上置换可以知道假币就在 4 和 5 之间
      • 1 = 4,假币是 5 且轻
      • 1 < 4,假币是 4 且重
  • 1 2 3 4 < 5 6 7 8,逻辑同上