Creative Commons Attribution 3.0 Unported license
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?
@InProceedings{frei_et_al:LIPIcs.FUN.2021.14,
author = {Frei, Fabian and Rossmanith, Peter and Wehner, David},
title = {{An Open Pouring Problem}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {14:1--14:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.14},
URN = {urn:nbn:de:0030-drops-127751},
doi = {10.4230/LIPIcs.FUN.2021.14},
annote = {Keywords: Pitcher Pouring Problem, Water Jug Riddle, Water Bucket Problem, Vessel Puzzle, Complexity, Die Hard}
}