puzzle - 难题:找到最小重量

Question

我遇到了这个问题：说给定两个权重1和3，您可以权衡1,2（乘以3-1），3,4（乘以3 + 1）（使用平衡的两面）。现在找到最小的砝码数量，以便可以测量1到1000。

答案是1,3,9,27 ...

我想知道您如何得出这样的解决方案，意味着3的幂。

资料来源：http://classic-puzzles.blogspot.com/search/label/Google%20Interview%20Puzzles

解决方案：http://classic-puzzles.blogspot.com/2006/12/solution-to-shopkeeper-problem.html

Answer 1

定理：对于i = 0到N，您需要权重3 ^ 0到3 ^ N来覆盖值1到S（N）= sum（3 ^ i）。

证明：


您已经给出了N = 1的基本情况。
现在假设这适用于N = 3 ^ M-S（M-1），就可以清楚地知道。也就是说，如果3 ^ M <= 1 + 2 * S（M-1）= 1 + sum（2 * 3 ^ i），则i = 0至M-1。目前，这对我来说似乎很清楚，但我已经喝了几杯鸡尾酒，但事实证明并不是您真正要求的，所以我将最后一步留给读者练习。
通过归纳，QED。