谜题/决策谜题/再次称重/解决方案

以下是一个糟糕的图

     /|\
    / | \
   /  |  \#
 ---- | ----
      |
   -------

要测量的重量是#。

我们证明，4 是用来测量 1 到 40 之间数字的称重集的最小尺寸。

第一个观察：称重集中的每个砝码都可以处于三种状态。它可以放在左侧，放在右侧，或者根本不在秤上。因此，对于 n 个砝码，最多有 3ⁿ 种可能的组合。

第二个观察：物体重量为 x 的有效称重必须满足以下方程

W_l = W_r + x

其中 W_l 和 W_r 分别是左侧和右侧所有砝码的总和。对于每对 W_l 和 W_r，x 都有唯一的解。

第三个观察：如果存在正数 x 的有效称重，则必须存在 -x 的有效称重。对于每个称重集，0 都有一个平凡解。如果我们想要 1 到 40 之间所有数字的解，则 n 必须至少为 4，因为 3⁴ = 2 • 40 + 1。

现在，我们构建一个最小解

引理：称重集 S(n) = {1, 3, ..., 3ⁿ} 可以测量 1 到 |S(n)| 之间的所有重量。

用归纳法证明：对于 S(0)，该引理显然成立。假设该引理对于 S(n) 成立。现在我们将证明它对于 S(n+1) 也成立。因为 S(n) 是 S(n+1) 的子集，所以我们当然可以在不使用砝码 3ⁿ⁺¹ 的情况下测量 1 到 |S(n)| = (3^n + 1)/2 之间的所有重量。通过将此砝码添加到左侧，我们可以达到 3ⁿ⁺¹ - (3ⁿ⁺¹)/2 = |S(n)| + 1 到 3ⁿ⁺¹ + (3ⁿ⁺¹)/2 = 3ⁿ⁺²/2 = |S(n+1)| 之间的所有解。QED。

因为 |S(3)| = 40，所以问题的解是称重集 {1,3,9,27}，它是最小的。

问题

证明这是一个唯一的解。
谁能想到“第四维度”的扩展？

用于找到如何从 1 到 S(n) 称量特定整数重量的算法

1 - 令 x 为你要找到称重集的重量。

2 - 从 S(n) 中减去 x，并将结果转换为 3 进制。然后用零填充，使结果字符串的大小等于称重集的大小。

3 - 从每个位减去一。由于字符串是 3 进制的，减去一后的结果是 -1、0 或 1。反转每个数字的符号。

4 - 每个数字决定在反向顺序中将它对应的位值砝码放在哪里（即 81、27、9、3、1）。零表示对应的砝码不在秤上，+1 表示在右侧，-1 表示在左侧。

例如，假设我们想知道如何放置 5 个砝码（1、3、9、27、81）来称量 51。

S(n) = 121

121 - 51 = 70

base₃(70) = 2121，零填充 => 02121，从每个数字中减去一 => -1、1、0、1、0，反转符号 => 1、-1、0、-1、0 => (+1 x 81) + (-1 x 27) + (0 x 9) + (-1 x 3) + (0 x 1) = 51

这些数字决定了砝码的放置位置：81 在右侧，27 在左侧，9 不在秤上，3 在左侧，1 不在秤上。