次品球 (Defective ball)

Q：12颗理应相同的球中存在一个次品球，该次品球可能略轻或略重。请用一个天平在三次测量中找出这个次品球，并给出其是略重（H）还是略轻（L）。

思路：若采用传统二分法，需要称四次，不合题目要求，因此需要另辟蹊径，即：将球分三份而不是两份，因为前两份的测量结果直接给出第三份的信息。

• 测量1，2，3，4 vs 5，6，7，8
  • 相等：则9-12中存在坏球。这里要把这4个球分为211的三份测其中两份，比如测 9，10 vs 11，8
    • 相等：则12坏。测 8 vs 12
      • 大于：12L
      • 小于：12H
    • 大于：则9，10存在H球，或11L。测 9 vs 10
      • 大于：9H
      • 小于：10H
      • 相等：11L
    • 小于：则9，10存在L球，或11H。测 9 vs 10
      • 大于：10L
      • 小于：9L
      • 相等：11H
  • 小于：则1-8中存在坏球，要么1-4存在L球，要么5-8存在H球。这里要把这8个球分为332的三份测其中两份（注：当测32的时候可带一个9-12中的正常球），比如测 1，2，5 vs 3，4，6
    • 大于：则5H/3L/4L。测 3 vs 4
      • 大于：4L
      • 小于：3L
      • 相等：5H
    • 小于：则1L/2L/6H。测 1 vs 2
      • 大于：2L
      • 小于：1L
      • 相等：6H
    • 相等：则7H/8H。测 7 vs 9
      • 大于：7H
      • 相等：8H
  • 大于：同理。

如果已知坏球是L还是H，则用n次测量可最多测出$(3^n)$个球；若不知道坏球是L还是H，则用n次测量最多可测$(3^n-3)/2$个球。