謎題/決策謎題/再次稱重/解決方案

以下是一個糟糕的圖

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

要測量的重量是#。

我們證明，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 不在秤上。