《另类称球趣题：验证砝码所标克数的正确性》由会员分享，可在线阅读，更多相关《另类称球趣题：验证砝码所标克数的正确性（14页珍藏版）》请在金锄头文库上搜索。
1、Baron M unchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle Tanya Khovanova MIT Cambridge, MA 02139 tanyakh Joel Brewster Lewis MIT Cambridge, MA 02139 jblewismath.mit.edu Submitted: Jun 18, 2010; Accepted: Dec 26, 2010; Published: Feb 14, 2011 Mathematics Subject Classifi cation: 05D99, 0
2、0A08, 11B75 Abstract We investigate a coin-weighing puzzle that appeared in the 1991 Moscow Math Olympiad. We generalize the puzzle by varying the number of participating coins, and deduce an upper bound on the number of weighings needed to solve the puzzle that is noticeably better than the trivial
3、 upper bound. In particular, we show that logarithmically-many weighings on a balance suffi ce. 1Introduction 1.1Background Baron M unchhausen is famous for telling the truth, only the truth and nothing but the truth 6. Unfortunately, no one believes him. Alexander Shapovalov gave him an unusual cha
4、nce to redeem himself by inventing a problem that appeared in the Regional round of the All-Russian Math Olympiad in 2000 8. Eight coins weighing 1,2,.,8 grams are given, but which weighs how much is unknown. Baron M unchhausen claims he knows which coin is which; and off ers to prove himself right
5、by conducting one weighing on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins. Is this possible, or is he exaggerating? In 4, T. Khovanova, K. Knop and A. Radul considered a natural generalization of this problem. They defi ned the following sequence, whic
6、h they called Baron M unchhausens sequence (sequence A174541 in 7): the electronic journal of combinatorics 18 (2011), #P371 Let n coins weighing 1,2,.,n grams be given. Suppose Baron M unchhausen knows which coin weighs how much, but his audience does not. Then b(n) is the minimum number of weighin
7、gs the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins. They completely described the sequence. Namely, they proved that b(n) 2, and provided the list of n for which b(n) = 1. A similar coin-weighing puzzle, due to Sergey Tokarev 5, a
8、ppeared in the last round of the Moscow Math Olympiad in 1991: You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number 1,2,3,4,5,6 on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, u
9、sing the balance scale only twice? Most people are surprised to discover that only in two weighings the weight of the each coin can be established. We invite the reader to try this puzzle out before the enjoyment is spoiled on page 3. 1.2The Sequence We generalize the preceding puzzle to n coins tha
10、t weigh 1, 2, ., n grams. We are interested in the minimum number of weighings a(n) on a balance scale that are needed in order to convince the audience about the weight of all coins. In this paper, we demonstrate that we can do this in not more than order of logn weighings. Because the sequence a(n
11、) relates to the task of identifying all coins (while the sequence b(n) relates to the task of identifying some coin) we will call it the Barons omni-sequence. We also calculate bounds for how many weighings are needed to prove the weight for a given particular coin. 1.3The Roadmap In Section 2 we g
12、ive a precise defi nition of the Barons omni-sequence and calculate its fi rst few terms. In Section 3 we prove natural lower and upper bounds for the sequence, and in Section 4 we present the values of all known terms of the sequence. Section 5 is devoted to useful notations and terminology. In Sec
13、tion 6 we describe the idea behind the main proof of a tighter upper bound. We put this idea into practice in the subsequent three sections: in Section 7, we show that it is possible to determine the weights of several special coins in log2n weighings, and in Section 8 we show how to use log2n addit
14、ional weighings to prove the weights of the rest of the coins. We thus establish that a(n) does not exceed 2log2n. In Section 9, we give a refi ned version of the argument which results in a modestly improved bound. In Section 10 we consider the related task of proving the weight of a particular (e.
15、g., adversarially-chosen) coin and prove that it can be done in not more than seven weighings. the electronic journal of combinatorics 18 (2011), #P372 In Section 11 we discuss two topics. First, we discuss the question of the monotonic- ity of the Barons omni-sequence.We do not come to a conclusion
16、, but just provide considerations. Second, we show how Konstantin Knop and his collaborators used the rearrangement inequality to fi nd optimal sets of weighings for a number of diff erent values of n. Finally, in Section 12 we off er some further comments, questions and ideas for future research. 2The Sequence The sequence a(n) is defi ned as follows: Let n coins weighing 1,2,.,n grams be given. Suppose Baron M unchhausen knows which coin weighs how much, but th
