天平称重的最少砝码

最优选择为平衡三进制：取砝码重量

$$1,3,9,\dots,3^k$$

其中 $k$ 为最小满足

$$\frac{3^{k+1}-1}{2}\ge N$$

的整数。

原因：在两盘天平上，每个砝码可放在左盘（系数 $-1$）、不使用（0）、右盘（+1），从而任意重量都可唯一表示为

$$\sum_{i=0}^{k} s_i 3^i,\quad s_i\in\{-1,0,1\}.$$

---

Original Explanation

Solution

We will require the set (1,3,9.....3^x ) where x is lowest integer with 3^x > N. This is true because each number now has exactly one ternary representation. Any 2 * 3^i can always be represented as 3^(i+1) - 3^i. So, there is a unique way of representing a number in the form of sigma s_i * 3^i where s_i belongs to {0, 1, -1}. So, this is optimal Verify that this can be used to weigh all integers from 1 to N Number of pebbles = log_{base:3} (2N+1)

If each weight w_i has k copies, then 2k+1 combinations can be weighed using them (from -k * w_i to 0 to k * w_i). So, if we choose w_i = (2k+1)^{i-1}, i=1...p, then everything till k*((2k+1)^p - 1)/((2k+1)-1) = ((2k+1)^p-1)/2 can be weighted, thus requiring p=log_{2k+1} (2N+1) number of distinct weights.