Игра по изготовлению коробок

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

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

Определение

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

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

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

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

Стратегии

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

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

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

Ссылки

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

[Chvátal_1978-1] Хватал, В.; Эрдеш, П. (1978). «Предвзятые позиционные игры» . Анналы дискретной математики . 2 (С): 221–229. дои : 10.1016/S0167-5060(08)70335-2 . ISSN 0167-5060 .

[Hamidoune_1987-2] Перейти обратно: ^а ^б Хамидун, Яхья Ульд; Лас Верньяс, Мишель (1 июня 1987 г.). «Решение коробочной игры» . Дискретная математика . 65 (2): 157–171. дои : 10.1016/0012-365X(87)90138-5 . ISSN 0012-365X .

[pg14-3] Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинар в Обервольфахе. Том 44. Базель: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8 .

[ 1 ]

[ 2 ]

[ 3 ]