An Open Pouring Problem

Authors Fabian Frei, Peter Rossmanith, David Wehner



PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.14.pdf
  • Filesize: 2.5 MB
  • 9 pages

Document Identifiers

Author Details

Fabian Frei
  • Department of Computer Science, ETH Zürich, Switzerland
Peter Rossmanith
  • Department of Computer Science, RWTH Aachen, Germany
David Wehner
  • Department of Computer Science, ETH Zürich, Switzerland

Acknowledgements

We would like to thank the anonymous reviewers who carefully read this paper for their detailed feedback.

Cite As Get BibTex

Fabian Frei, Peter Rossmanith, and David Wehner. An Open Pouring Problem. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FUN.2021.14

Abstract

We analyze a little riddle that has challenged mathematicians for half a century.
Imagine three clubs catering to people with some niche interest. Everyone willing to join a club has done so and nobody new will pick up this eccentric hobby for the foreseeable future, thus the mutually exclusive clubs compete for a common constituency. Members are highly invested in their chosen club; only a targeted campaign plus prolonged personal persuasion can convince them to consider switching. Even then, they will never be enticed into a bigger group as they naturally pride themselves in avoiding the mainstream. Therefore each club occasionally starts a campaign against a larger competitor and sends its own members out on a recommendation program. Each will win one person over; the small club can thus effectively double its own numbers at the larger one’s expense. 
Is there always a risk for one club to wind up with zero members, forcing it out of business? If so, how many campaign cycles will this take?

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
  • Theory of computation → Representations of games and their complexity
Keywords
  • Pitcher Pouring Problem
  • Water Jug Riddle
  • Water Bucket Problem
  • Vessel Puzzle
  • Complexity
  • Die Hard

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. URL: https://kskedlaya.org/putnam-archive/1993.pdf.
  2. URL: https://www.research.ibm.com/haifa/ponderthis/challenges/May2015.html.
  3. URL: https://bwinf.de/fileadmin/bundeswettbewerb/38/BwInf38-Aufgabenblatt.pdf.
  4. URL: https://oeis.org/A256001.
  5. Paolo Boldi, Massimo Santini, and Sebastiano Vigna. Measuring with jugs. Theor. Comput. Sci., 282(2):259-270, 2002. Google Scholar
  6. Yiu-Kwong Man. A non-heuristic approach to the general two water jugs problem. Theor. Comput. Sci., (10):904-908, 2013. Google Scholar
  7. Николай Борисович Васильев (Nikolaj Borisovich Vasil'ev) and Александр Александрович Егоров (Aleksandr Aleksandrovich Egorov). Задачи всесоюзных математических олимпиад (Zadachi Vsesojuznyh Matematicheskih Olimpiad, Problems of the All-Union Mathematical Olympiads). Наука (Nauka), 1988. Google Scholar
  8. Glânffrwd P. Thomas. The water jugs problem: Solutions from artificial intelligence and mathematical viewpoints. Mathematics in School, 24(5):34-37, 1995. Google Scholar
  9. Peter Winkler. Mathematical Puzzles: A Connoisseur’s Collection. A K Peters, 2004. Google Scholar
  10. Peter Winkler. Five algorithmic puzzles. In Tribute to a Mathemagician, pages 109-118. A K Peters, 2005. Google Scholar
  11. Peter Winkler. Mathematische Rätsel für Liebhaber. Springer, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail