Изменения
Нет описания правки
# Рассмотрим пример экономической игры с бесконечным множеством стратегий: дуополия Курно. На рынке есть две фирмы, стратегии которых заключаются в производстве $q_1$ и $q_2$ товара, соответственно. Цена за единицу товара равна $p-q_1-q_2$. Себестоимость единицы товара $c$. Соответственно, выигрыши игроков равны $u_1(q_1,q_2)=(p-q_1-q_2-c)q_1$ и $u_2(q_1,q_2)=(p-q_1-q_2-c)q_2$. Найдите равновесие по Нэшу для дуополии Курно.
# Дуополия Бертрана. На рынке есть две фирмы, которые производят различные товары $A$ и $B$, соответственно, а их стратегии заключаются в установлении цены на товары $c_1$ и $c_2$, соответственно. После этого фирмы продают $Q_1 = q-c_1+kc_2$ и $Q_2 = q-c_2+kc_1$ единиц товара, соответственно. Себестоимость единицы товара $c$. Запишите выигрыши игроков в дуополии Бертрана и найдите равновесие по Нэшу.
# Крестики и крестики. Два игрока играют на поле $1 \times n$ (\mbox{$n \ge 3$}), своим ходом игрок может поставить крестик в любую свободную клетку. Игрок, после хода которого на поле есть ряд из трех крестиков, побеждает. Предложите полиномиальный от $n$ алгоритм определения победителя в этой игре.
# Рассмотрим окружность, вдоль которой нанесены $n$ различных точек. За один ход разрешается провести хорду, которая не должна иметь общих точек с ранее проведенными хордами (в том числе они не должны иметь общих концов). Кто не может сделать ход, проигрывает. Предложите полиномиальный от $n$ алгоритм определения победителя в этой игре.
# Ним с разбиением. В кучках лежит $a_1, \ldots, a_n$ камней. За один ход можно или забрать из кучки некоторое количество камней, либо разбить кучку на две непустых. Проанализируйте игру ним с разбиением.
# Зеленый хакенбуш на графе с циклами. Предложите алгоритм анализа игры хакенбуш на графе, который не обязательно является деревом.
# Малыш и Карлсон. У Малыша и Карлсона есть торт, имеющий вид прямоугольного параллелепипеда, размером $a\times b\times c$ сантиметров, где $a$, $b$ и $c$~--- целые числа. Они играют в следующую игру: Малыш и Карлсон делают ходы по очереди. За один ход игрок может разрезать торт параллельно одной из его граней на две неравные части (длины ребер каждой из частей снова должны быть целыми), после чего съесть меньшую часть. Тот, кто не может сделать ход, поскольку торт имеет размер $1\times 1\times 1$, проигрывает. Определить, кто выигрывает в игре за $O(\max(a, b, c)^2)$.
# Шахматы Доусона. Рассмотрим доску $3 \times n$, на первом ряду которой стоят белые пешки, а на последнем --- черные пешки. За один ход можно либо подвинуть свою пешку на одну клетку вперед (клетка, на которую перемещается пешка, должна быть свободна), либо побить пешку соперника на одну клетку вперед по диагонали. Если есть возможность побить пешку, то бить обязательно. Кто не может сделать ход, проигрывает. Предложите алгоритм определения победителя в шахматах Доусона за полином от $n$.
# Посчитайте функцию Гранди для игры ним, в которой кучки упорядочены некоторым фиксированным образом, и количество камней в кучках не убывает. Это же свойство должно сохраниться после каждого хода (порядок кучек при этом остается прежним). Например, из позиции $\langle 2, 3, 3, 5\rangle$ возможен ход в позицию $\langle 2, 3, 3, 3\rangle$ или $\langle 0, 3, 3, 5\rangle$, а в позицию $\langle 2, 3, 3, 2\rangle$~--- нет.
# Сумму игр на одном и том же графе можно интерпретировать как игру, в которой по графу перемещается не одна фишка, а несколько. За ход игрок должен переместить одну их фишек, при этом несколько фишек могут одновременно находиться в вершине графа. Введем понятие игр с аннигиляцией. Игра протекает таким же образом, но если две фишки оказываются в одной вершине графа, они <<аннигилируют>>~--- обе фишки удаляются из графа. Покажите, что в игре с аннигиляцией на ациклическом графе выигрывает тот же игрок, что и в игре без аннигиляции (обычной прямой сумме игр). Почему это рассуждение не проходит в случае, если в графе есть циклы?
# В этой и следующих четырех задачах в качестве носителя рассматривается $\mathbb{Z}^+$. Докажите, что $a \otimes b \le ab$.
# Докажите, что $a \otimes 1 = a$.
# Докажите, что $(a\oplus b)\otimes c = a\otimes c \oplus b \otimes c$.
# Вычислите $2^k\otimes 2^n$. Пользуясь этим и предыдущим заданием, предложите способ вычислить $a\otimes b$ для любых $a$ и $b$.
# Докажите, что для любого $a$ существует единственное $a^{-1}$, что $a\otimes a^{-1}=1$. Тем самым завершим доказательство, что получается поле.
# Докажите, что для любого $n$ множество чисел от $0$ до $2^{2^n}-1$ с операциями $\oplus$ и $\otimes$ образует поле.
# Чему равно $\omega \otimes k$ для неотрицательного целого $k$?
# Чему равно $\omega \otimes \omega$?
# Чему равно $\omega \otimes \omega \otimes \omega$ (спойлер: 2)?
# Игра в поддавки: кто не может сделать ход, тот выигрывает. Предъявите пример суммы двух проигрышных игр в поддавки, которая является выигрышной.
# Ним в поддавки. Докажите, что за исключением случая, когда все кучки имеют размер $1$, позиция в ниме в поддавки является выигрышной тогда и только тогда, когда она является выигрышной в обычном ниме.
