返回题库

90 枚硬币找异币（未知偏重或偏轻）：最小化最坏称重成本

a set of scales and 90 coins

专题
Probability / 概率
难度
L6

题目详情

你有一架老式天平（只能告诉你两边等重或哪边更重），以及 90 枚外观完全相同的硬币。事实上其中 89 枚完全相同，另 1 枚重量不同。

每使用天平一次都要付 100 美元。你要在最坏情况下以最小成本找出那枚异币，并判断它是偏重还是偏轻。

问：你的算法是什么？在最优策略下，最坏情况总成本是多少？

You are given a set of scales and 90 coins. The scales are of the old balance variety. That is, a small dish hangs from each end of a rod that is balanced in the middle. The device enables you to conclude either that the contents of the dishes weigh the same or that the dish that falls lower has heavier contents than the other. You must pay $100100 every time you use the scales. The 90 coins appear to be identical. In fact, 89 of them are identical, and one is of a different weight. Your task is to identify the unusual coin and to discard it while minimizing the maximum possible cost of weighing. What is your algorithm to complete this task? What is the most it can cost to identify the unusual coin (assuming your strategy minimizes the maximum possible cost)? Note that the unusual coin may be heavier than the others, or it may be lighter. You are asked to both identify it and determine whether it is heavy or light.

解析

异币可能“偏重”或“偏轻”，因此共有 90×2=18090\times 2=180 种可能情况。

一次称重有 3 种结果（左重/平衡/右重），所以 ww 次称重最多区分 3w3^w 种情况。要覆盖 180 种情况必须有

3w≥180⇒w≥5(因为 34=81<180, 35=243≥180).3^w\ge 180\Rightarrow w\ge 5\quad (\text{因为 }3^4=81<180,\ 3^5=243\ge 180).

因此最坏情况下至少需要 5 次称重，最少最坏成本至少为 5×100=5005\times 100=500 美元。

并且 5 次称重足够：给每枚硬币分配一个长度为 5 的“平衡三进制码”

v=(v1,…,v5),vi∈{−1,0,1}, v≠0,v=(v_1,\ldots,v_5),\quad v_i\in\{-1,0,1\},\ v\ne 0,

并且保证没有两枚硬币使用互为相反数的编码（即不同时出现 vv 与 −v-v）。因为非零编码共有 35−1=2423^5-1=242 个，按“相反数成对”可容纳 242/2=121242/2=121 枚硬币，足够覆盖 90 枚。

第 ii 次称重按 viv_i 安排：

  • vi=1v_i=1：把该硬币放到左盘
  • vi=−1v_i=-1：放到右盘
  • vi=0v_i=0：不参与本次称重

称重结果得到一个向量 o∈{−1,0,1}5o\in\{-1,0,1\}^5（左重/平衡/右重分别记为 1/0/−11/0/-1）。

  • 若某枚硬币编码为 vv 且它偏重，则结果向量为 o=vo=v；
  • 若它偏轻，则结果向量为 o=−vo=-v。

因此用 5 次称重可以唯一确定“哪一枚硬币异常”以及“偏重还是偏轻”。

最坏情况最小成本为 500 美元\boxed{500\text{ 美元}}。