TAILIEUCHUNG - Báo cáo toán học: "Baron M¨nchhausen Redeems Himself: u Bounds for a Coin-Weighing Puzzle Tanya Khovanova"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Baron M¨nchhausen Redeems Himself: u Bounds for a Coin-Weighing Puzzle Tanya Khovanova. | Baron Munchhausen Redeems Himself Bounds for a Coin-Weighing Puzzle Tanya Khovanova MIT Cambridge MA 02139 tanyakh@ Joel Brewster Lewis MIT Cambridge MA 02139 jblewis@ Submitted Jun 18 2010 Accepted Dec 26 2010 Published Feb 14 2011 Mathematics Subject Classification 05D99 00A08 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 upper bound. In particular we show that logarithmically-many weighings on a balance suffice. 1 Introduction B ackground Baron Miinchhausen 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 chance 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 Munchhausen claims he knows which coin is which and offers to prove himself right 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 defined the following sequence which they called Baron Munchhausen s sequence sequence A174541 in 7 THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P37 1 Let n coins weighing 1 2 . n grams be given. Suppose Baron Miinchhausen knows which coin weighs how much but his audience does not. Then b n is the minimum number of weighings 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 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học