Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle
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 part...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Electronic Journal of Combinatorics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89805 https://orcid.org/0000-0003-0868-8981 |
| _version_ | 1826201460835090432 |
|---|---|
| author | Khovanova, Tanya Lewis, Joel Brewster |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Khovanova, Tanya Lewis, Joel Brewster |
| author_sort | Khovanova, Tanya |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:52:10Z |
| format | Article |
| id | mit-1721.1/89805 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:52:10Z |
| publishDate | 2014 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/898052022-10-01T06:33:21Z Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle Khovanova, Tanya Lewis, Joel Brewster Massachusetts Institute of Technology. Department of Mathematics Khovanova, Tanya Lewis, Joel Brewster 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. 2014-09-18T16:24:22Z 2014-09-18T16:24:22Z 2011-02 2010-06 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/89805 Khovanova, Tanya, and Joel Brewster Lewis. "Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle." Electronic Journal of Combinatorics, Volume 18, Issue 1 (2011). https://orcid.org/0000-0003-0868-8981 en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p37 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Electronic Journal of Combinatorics Electronic Journal of Combinatorics |
| spellingShingle | Khovanova, Tanya Lewis, Joel Brewster Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle |
| title | Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle |
| title_full | Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle |
| title_fullStr | Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle |
| title_full_unstemmed | Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle |
| title_short | Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle |
| title_sort | baron munchhausen redeems himself bounds for a coin weighing puzzle |
| url | http://hdl.handle.net/1721.1/89805 https://orcid.org/0000-0003-0868-8981 |
| work_keys_str_mv | AT khovanovatanya baronmunchhausenredeemshimselfboundsforacoinweighingpuzzle AT lewisjoelbrewster baronmunchhausenredeemshimselfboundsforacoinweighingpuzzle |