词条 | Box-making game |
释义 |
A box-making game (often called just a box game) is a biased positional game where two players alternately pick elements from a family of pairwise-disjoint sets ("boxes"). The first player - called BoxMaker - tries to pick all elements of a single box. The second player - called BoxBreaker - tries to pick at least one element of all boxes. The box game was first presented by Paul Erdős and Václav Chvátal.[1] It was solved later by Hamidoune and Las-Vergnas.[2] DefinitionA box game is defined by:
The first player, BoxMaker, picks p balls (from the same or different boxes). Then the second player, BoxBreaker, breaks q boxes. And so on. BoxMaker wins if he has managed to pick all balls in at least one box, before BoxBreaker managed to break this box. BoxBreaker wins if he has managed to break all the boxes. StrategiesIn general, the optimal strategy for BoxBreaker is to break the boxes with the smallest number of remaining elements. The optimal strategy for BoxMaker is to try to balance the sizes of all boxes. By simulating these strategies, Hamidoune and Las-Vergnas[2] found a sufficient and necessary condition for each player in the (p:q) box game. For the special case where q=1, the each of the following conditions is sufficient:[3]{{Rp|36-39}}
References1. ^{{Cite journal|last=Chvátal|first=V.|last2=Erdös|first2=P.|date=1978|title=Biased Positional Games|url=https://hungary.pure.elsevier.com/en/publications/biased-positional-games|journal=Annals of Discrete Mathematics|language=English|volume=2|issue=C|pages=221–229|doi=10.1016/S0167-5060(08)70335-2|issn=0167-5060}} 2. ^1 {{Cite journal|date=1987-06-01|title=A solution to the Box Game|url=https://www.sciencedirect.com/science/article/pii/0012365X87901385|journal=Discrete Mathematics|language=en|volume=65|issue=2|pages=157–171|doi=10.1016/0012-365X(87)90138-5|issn=0012-365X|last1=Hamidoune|first1=Yahya Ould|last2=Las Vergnas|first2=Michel}} 3. ^{{Cite Positional Games 2014}} 1 : Positional games |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。