Игра в изготовление коробок - Box-making game

Для использования в других целях см. Коробочная игра.

А игра по изготовлению коробок (часто называют просто коробочная игра) это предвзятая позиционная игра где два игрока поочередно выбирают элементы из семейства попарно непересекающихся множеств («ящиков»). Первый игрок - называется BoxMaker - пытается выбрать все элементы одного ящика. Второй игрок - называется BoxBreaker - пытается выбрать хотя бы один элемент из всех ящиков.

Коробочную игру впервые представил Пол Эрдёш и Вацлав Хваталь.^[1] Позднее ее решили Хамидун и Лас-Вергнас.^[2]

Определение

Коробочная игра определяется:

• Семья п попарно непересекающиеся множества, ${\displaystyle A_{1},\ldots ,A_{n}}$, разных размеров. Наборы часто называют «коробками», а элементы - «шарами».
• Два целых числа, п и q.

Первый игрок, BoxMaker, выбирает п шары (из одной или разных коробок). Затем второй игрок, BoxBreaker, перерывы q коробки. И так далее.

BoxMaker выигрывает, если ему удалось собрать все шары хотя бы из одной коробки, прежде чем BoxBreaker удалось разбить эту коробку. BoxBreaker выигрывает, если ему удалось разбить все коробки.

Стратегии

В общем, оптимальная стратегия для BoxBreaker - разбивать ящики с наименьшим количеством оставшихся элементов. Оптимальная стратегия для BoxMaker - попытаться сбалансировать размеры всех ящиков. Моделируя эти стратегии, Хамидун и Лас-Вергнас^[2] нашел достаточное и необходимое условие для каждого игрока в (п:q) коробка игры.

Для особого случая, когда q= 1, достаточно каждого из следующих условий:^[3]:36–39

• Если все коробки имеют одинаковый размер k и ${\displaystyle p\cdot \sum _{i=1}^{n}{1 \over i}<k}$, то BoxBreaker выигрывает игру с ячейками (p: 1) (используя очевидную стратегию разбивания самых маленьких ящиков). Для сравнения, условие победы для Breaker в целом (п:q) предвзятая игра: ${\displaystyle n<(q+1)^{k/p}}$. С q= 1 это становится ${\displaystyle p\cdot \log _{2}{n}<k}$. Доказательство использует потенциальную функцию. Потенциал игры до BoxBreaker's j-й ход определяется как: ${\displaystyle {1 \over n-j+1}\sum _{i=j}^{n}c_{i}}$куда ${\displaystyle c_{i}}$количество элементов, оставшихся в коробке я.
• Если коробки имеют разные размеры k1, ..., kn и ${\displaystyle \sum _{i=1}^{n}e^{-k_{i}/p}<{1/e}}$, затем BoxBreaker побеждает в игре на поле (p: 1). Для сравнения, условие победы Breaker в общей (p: q) предвзятой игре: ${\displaystyle \sum _{i=1}^{n}(1+q)^{-k_{1}/p}<{1 \over 1+q}}$. При q = 1 это становится ${\displaystyle \sum _{i=1}^{n}2^{-k_{i}/p}<{1 \over 2}}$.

Рекомендации

1. Chvátal, V .; Эрдеш, П. (1978). «Предвзятые позиционные игры». Анналы дискретной математики. 2 (C): 221–229. Дои:10.1016 / S0167-5060 (08) 70335-2. ISSN  0167-5060.
2. Хамидун, Яхья Ульд; Лас Вергнас, Мишель (1 июня 1987). «Решение коробочной игры». Дискретная математика. 65 (2): 157–171. Дои:10.1016 / 0012-365X (87) 90138-5. ISSN  0012-365X.
3. Хефец, Дэн; Кривелевич Михаил; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры. Обервольфахские семинары. 44. Базель: Birkhäuser Verlag GmbH. ISBN  978-3-0348-0824-8.