Қорап жасау ойыны - Box-making game

A жәшік жасау ойыны (жиі тек а деп аталады бокс ойыны) Бұл позитивті ойын мұнда екі ойыншы кезектесіп жұптастырылған жиынтықтар тобынан элементтерді таңдайды («қораптар»). Бірінші ойыншы - шақырылды BoxMaker - бір қораптың барлық элементтерін таңдауға тырысады. Екінші ойыншы - қоңырау шалды BoxBreaker - барлық қораптардың кем дегенде бір элементін таңдауға тырысады.

Жәшік ойынын алғаш ұсынған Paul Erdős және Вацлав Чватал.^[1] Оны кейінірек Хамидун мен Лас-Вернас шешті.^[2]

Анықтама

Жәшік ойыны анықталады:

Отбасы n жұптастырылған жиынтықтар, ${ 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}$ содан кейін BoxBreaker (p: 1) бокс ойынында жеңіске жетеді (ең кішкентай қораптарды бұзудың айқын стратегиясын қолдана отырып). Салыстыру үшін, Breaker-тің жалпы ұтысы (б:q) біржақты ойын дегеніміз: ${ displaystyle n <(q + 1) ^ {k / p}}$ . Бірге q= 1 болады ${ displaystyle p cdot log _ {2} {n}$ . Дәлелдеу потенциалды функцияны қолданады. BoxBreaker-ге дейінгі ойынның әлеуеті 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) қораптағы ойында жеңеді. Салыстыру үшін, жалпы (p: q) бейтарап ойындағы Breaker ұтылу шарты: ${ 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 2}} үстінде$ .

Әдебиеттер тізімі

^ Чваталь, V .; Erdös, P. (1978). «Біржақты позициялық ойындар». Дискретті математиканың жылнамалары. 2 (C): 221-229. дои:10.1016 / S0167-5060 (08) 70335-2. ISSN 0167-5060.
^ ^а ^б Хамидун, Яхья Улд; Лас Вернас, Мишель (1987-06-01). «Box Box ойынына шешім». Дискретті математика. 65 (2): 157–171. дои:10.1016 / 0012-365X (87) 90138-5. ISSN 0012-365X.
^ Хефетц, Дэн; Кривелевич, Майкл; Стоякович, Милош; Сабо, Тибор (2014). Позициялық ойындар. Oberwolfach семинарлары. 44. Базель: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.

[Chvátal_1978-1] Чваталь, V .; Erdös, P. (1978). «Біржақты позициялық ойындар». Дискретті математиканың жылнамалары. 2 (C): 221-229. дои:10.1016 / S0167-5060 (08) 70335-2. ISSN 0167-5060.

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

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

[1]

[2]

[3]