PUMaC 2009 · 组合（A 组） · 第 2 题
PUMaC 2009 — Combinatorics (Division A) — Problem 2
题目详情
- It is known that a certain mechanical balance can measure any object of integer mass anywhere between 1 and 2009 (both included). This balance has k weights of integral values. What is the minimum k for which there exist weights that satisfy this condition?
解析
- It is known that a certain mechanical balance can measure any object of integer mass anywhere between 1 and 2009 (both included). This balance has k weights of integral values. What is the minimum k that satisfies this condition? k 3 Solution. 8. If n < , then one can weigh an object of weight n with at most k weights, of 2 k − 1 weights 1, 3, . . . , 3 by putting the unit weight on the same side as the object if the last ternary digit of n is 2, on the other side if it is 1, and ignoring the weight if it is 0; after which one divides everything by 3 and uses induction. This is also clearly optimal, as one needs at k 3 +1 least k weights to weigh the object of weight , so the answer is greater than log (2 ∗ 2009), 3 2 and one can check that that is about 7 . 55, so 8 is the answer.