Hra na výrobu krabic - Box-making game

A hra na výrobu krabic (často nazývané jen a boxová hra) je zaujatá poziční hra kde dva hráči střídavě vybírají prvky z rodiny párově disjunktních sad („krabic“). Volal první hráč BoxMaker - pokusí se vybrat všechny prvky jedné krabice. Volal druhý hráč BoxBreaker - pokusí se vybrat alespoň jeden prvek ze všech polí.

Krabicovou hru poprvé představil Paul Erdős a Václav Chvátal.^[1] To později vyřešili Hamidoune a Las-Vergnas.^[2]

Definice

Krabicová hra je definována:

• Rodina n párově disjunktní sady, ${ displaystyle A_ {1}, ldots, A_ {n}}$, různých velikostí. Sady se často nazývají „boxy“ a prvky se nazývají „koule“.
• Dvě celá čísla, p a q.

První hráč, BoxMaker, výběry p koule (ze stejných nebo různých krabic). Pak druhý hráč, BoxBreaker, přestávky q krabice. A tak dále.

BoxMaker vyhrává, pokud se mu podařilo vyzvednout všechny míčky v alespoň jedné krabici, než se BoxBreakeru podařilo tuto krabičku rozbít. BoxBreaker vyhrává, pokud se mu podařilo rozbít všechny boxy.

Strategie

Optimální strategií pro BoxBreaker je obecně rozbití krabic s nejmenším počtem zbývajících prvků. Optimální strategií pro BoxMaker je pokusit se vyrovnat velikosti všech krabic. Simulací těchto strategií Hamidoune a Las-Vergnas^[2] našel dostatečnou a nezbytnou podmínku pro každého hráče v (p:q) boxová hra.

Pro zvláštní případ, kdy q= 1, postačuje každá z následujících podmínek:^[3]:36–39

• Pokud mají všechna pole stejnou velikost k, a ${ displaystyle p cdot sum _ {i = 1} ^ {n} {1 nad i}$, pak BoxBreaker vyhrává hru (p: 1) v boxu (za použití zřejmé strategie rozbití nejmenších krabic). Pro srovnání platí, že výherní podmínka pro Breaker obecně (p:q) zaujatá hra je: ${ displaystyle n <(q + 1) ^ {k / p}}$. S q= 1 toto se stane ${ displaystyle p cdot log _ {2} {n}$. Důkaz využívá potenciální funkci. Potenciál hry před BoxBreakerem j-tý tah je definován jako: ${ displaystyle {1 over n-j + 1} součet _ {i = j} ^ {n} c_ {i}}$kde ${ displaystyle c_ {i}}$je počet prvků zbývajících v poli i.
• Pokud mají krabice různé velikosti k1, ..., kn a ${ displaystyle sum _ {i = 1} ^ {n} e ^ {- k_ {i} / p} <{1 / e}}$, pak BoxBreaker vyhraje (p: 1) boxovou hru. Pro srovnání, vítězná podmínka pro hru Breaker v obecné (p: q) zaujaté hře je: ${ displaystyle sum _ {i = 1} ^ {n} (1 + q) ^ {- k_ {1} / p} <{1 nad 1 + q}}$. S q = 1 se to stane ${ displaystyle sum _ {i = 1} ^ {n} 2 ^ {- k_ {i} / p} <{1 nad 2}}$.

Reference