返回题库

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{ 美元}}。

英文解析

Since different coins may be "heavier" or "lighter," there are 90×2=18090\times 2=180 possible scenarios.

A single weighing has 3 possible outcomes (left heavy/balanced/right heavy), so ww weighings can distinguish at most 3w3^w scenarios. To cover 180 scenarios, we must have

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

Thus, in the worst case, at least 5 weighings are required, and the minimum worst-case cost is at least 5×100=5005\times 100=500 dollars.

Furthermore, 5 weighings are sufficient: assign a "balanced ternary code" of length 5 to each coin

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,

and ensure that no two coins use codes that are opposites of each other (i.e., neither vv nor −v-v appears simultaneously). Since there are 35−1=2423^5-1=242 non-zero codes, pairing them by opposites allows accommodating 242/2=121242/2=121 coins, which is sufficient to cover the 90 coins.

The ii-th weighing is arranged according to viv_i:

-vi=1v_i=1: place the coin on the left pan
-vi=−1v_i=-1: place the coin on the right pan
-vi=0v_i=0: the coin does not participate in this weighing

The weighing results yield a vector o∈{−1,0,1}5o\in\{-1,0,1\}^5 (left heavy/balanced/right heavy denoted as 1/0/−11/0/-1 respectively).

  • If a coin has code vv and is heavier, the result vector is o=vo=v;
  • If it is lighter, the result vector is o=−vo=-v.

Therefore, using 5 weighings, one can uniquely determine "which coin is abnormal" and "whether it is heavier or lighter."

The minimum worst-case cost is 500 dollars\boxed{500\text{ dollars}}.