Список заданий по ТИгр 2022 весна

1. Для комбинаторной игры $A=\{L|R\}$ определим игру $-A$. $-0=0$, для других игр пусть $L=\{g^L_1, g^L_2, \ldots\}$, $R=\{g^R_1, g^R_2, \ldots\}$, определим $-L=\{-g^L_1, -g^L_2, \ldots\}$, $-R$ определяется аналогично, $-A = \{-R|-L\}$. Что можно сказать про игру $A+(-A)$? Далее будем обозначать игру $A + (-B)$ как $A-B$.
2. На лекции было введено определение эквивалентности $A \approx B$ если для любой игры $C$ исход $A+C$ и $B+C$ одинаковый. Можно ввести альтернативное определение: скажем, что $A\approx B$, если $A-B$ проигрышная для текущего игрока (класс $P$). Докажите, что эти определения дают одно и то же отношение эквивалентности. Далее нам не очень интересно различать эквивалентные игры, поэтому мы будем для простоты называть их равными и использовать значок $=$.
3. Докажите формально, что сумма игр ассоциативна и коммутативна.
4. Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $\mathbin{\scriptstyle\dot{\smash{\textstyle-}}} A = \{R|L\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
5. Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $!A = \{!L|!R\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
6. Будем говорить, что игра $A$ является положительной, если в ней выигрывает игрок L и писать $A>0$. Докажите, что если $A > 0$ и $B > 0$, то $A+B>0$.
7. Будем говорить, что $A > B$, если $A-B>0$. Докажите, что отношение $>$ является антирефлексивным, антисимметричным и транзитивным (строгий порядок).
8. Определим неотрицательные целые числа по формуле $G_0 = \{|\}$, $G_n = \{G_{n-1}|\}$ (далее мы будем вместо $G_n$ писать просто $n$, но в этом задании без отдельного обозначения не обойтись). Докажите, что $G_n+G_m = G_{n+m}$.
9. Определите отрицательные целые числа. Докажите, что все законы для целых чисел как для группы по сложению выполнены. Мы вернемся к числам в одной из ближайших лекций, а пока переключаемся на матричные игры.
10. Приведите пример биматричной игры, в которой есть более одной различной точки равновесия по Нэшу, выигрыши игроков в которых различаются.
11. Лемма о масштабе Пусть матрица $A$ имеет седловую точку. Рассмотрим матрицу $B$, определенную соотношением $b_{ij} = ka_{ij}+d$, $k > 0$. Докажите, что матрица $B$ имеет седловую точку, причем множества координат седловых точек этих матриц совпадают.
12. Рассмотрим пример экономической игры с бесконечным множеством стратегий: дуополия Курно. На рынке есть две фирмы, стратегии которых заключаются в производстве $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$. Найдите равновесие по Нэшу для дуополии Курно.
13. Дуополия Бертрана. На рынке есть две фирмы, которые производят различные товары $A$ и $B$, соответственно, а их стратегии заключаются в установлении цены на товары $c_1$ и $c_2$, соответственно. После этого фирмы продают $Q_1 = q-c_1+kc_2$ и $Q_2 = q-c_2+kc_1$ единиц товара, соответственно. Себестоимость единицы товара $c$. Запишите выигрыши игроков в дуополии Бертрана и найдите равновесие по Нэшу.
14. Крестики и крестики. Два игрока играют на поле $1 \times n$ (\mbox{$n \ge 3$}), своим ходом игрок может поставить крестик в любую свободную клетку. Игрок, после хода которого на поле есть ряд из трех крестиков, побеждает. Предложите полиномиальный от $n$ алгоритм определения победителя в этой игре.
15. Рассмотрим окружность, вдоль которой нанесены $n$ различных точек. За один ход разрешается провести хорду, которая не должна иметь общих точек с ранее проведенными хордами (в том числе они не должны иметь общих концов). Кто не может сделать ход, проигрывает. Предложите полиномиальный от $n$ алгоритм определения победителя в этой игре.
16. Ним с разбиением. В кучках лежит $a_1, \ldots, a_n$ камней. За один ход можно или забрать из кучки некоторое количество камней, либо разбить кучку на две непустых. Проанализируйте игру ним с разбиением.
17. Зеленый хакенбуш на графе с циклами. Предложите алгоритм анализа игры хакенбуш на графе, который не обязательно является деревом.
18. Малыш и Карлсон. У Малыша и Карлсона есть торт, имеющий вид прямоугольного параллелепипеда, размером $a\times b\times c$ сантиметров, где $a$, $b$ и $c$~--- целые числа. Они играют в следующую игру: Малыш и Карлсон делают ходы по очереди. За один ход игрок может разрезать торт параллельно одной из его граней на две неравные части (длины ребер каждой из частей снова должны быть целыми), после чего съесть меньшую часть. Тот, кто не может сделать ход, поскольку торт имеет размер $1\times 1\times 1$, проигрывает. Определить, кто выигрывает в игре за $O(\max(a, b, c)^2)$.
19. Шахматы Доусона. Рассмотрим доску $3 \times n$, на первом ряду которой стоят белые пешки, а на последнем --- черные пешки. За один ход можно либо подвинуть свою пешку на одну клетку вперед (клетка, на которую перемещается пешка, должна быть свободна), либо побить пешку соперника на одну клетку вперед по диагонали. Если есть возможность побить пешку, то бить обязательно. Кто не может сделать ход, проигрывает. Предложите алгоритм определения победителя в шахматах Доусона за полином от $n$.
20. Посчитайте функцию Гранди для игры ним, в которой кучки упорядочены некоторым фиксированным образом, и количество камней в кучках не убывает. Это же свойство должно сохраниться после каждого хода (порядок кучек при этом остается прежним). Например, из позиции $\langle 2, 3, 3, 5\rangle$ возможен ход в позицию $\langle 2, 3, 3, 3\rangle$ или $\langle 0, 3, 3, 5\rangle$, а в позицию $\langle 2, 3, 3, 2\rangle$~--- нет.
21. Сумму игр на одном и том же графе можно интерпретировать как игру, в которой по графу перемещается не одна фишка, а несколько. За ход игрок должен переместить одну их фишек, при этом несколько фишек могут одновременно находиться в вершине графа. Введем понятие игр с аннигиляцией. Игра протекает таким же образом, но если две фишки оказываются в одной вершине графа, они <<аннигилируют>>~--- обе фишки удаляются из графа. Покажите, что в игре с аннигиляцией на ациклическом графе выигрывает тот же игрок, что и в игре без аннигиляции (обычной прямой сумме игр). Почему это рассуждение не проходит в случае, если в графе есть циклы?
22. В этой и следующих четырех задачах в качестве носителя рассматривается $\mathbb{Z}^+$. Докажите, что $a \otimes b \le ab$.
23. Докажите, что $a \otimes 1 = a$.
24. Докажите, что $(a\oplus b)\otimes c = a\otimes c \oplus b \otimes c$.
25. Вычислите $2^k\otimes 2^n$. Пользуясь этим и предыдущим заданием, предложите способ вычислить $a\otimes b$ для любых $a$ и $b$.
26. Докажите, что для любого $a$ существует единственное $a^{-1}$, что $a\otimes a^{-1}=1$. Тем самым завершим доказательство, что получается поле.
27. Докажите, что для любого $n$ множество чисел от $0$ до $2^{2^n}-1$ с операциями $\oplus$ и $\otimes$ образует поле.
28. Чему равно $\omega \otimes k$ для неотрицательного целого $k$?
29. Чему равно $\omega \otimes \omega$?
30. Чему равно $\omega \otimes \omega \otimes \omega$ (спойлер: 2)?
31. Игра в поддавки: кто не может сделать ход, тот выигрывает. Предъявите пример суммы двух проигрышных игр в поддавки, которая является выигрышной.
32. Ним в поддавки. Докажите, что за исключением случая, когда все кучки имеют размер $1$, позиция в ниме в поддавки является выигрышной тогда и только тогда, когда она является выигрышной в обычном ниме.
33. В этой серии только четкие игры. Немного арифметики. Постройте красно-синий бамбук Хакенбуш для игры со значением $3/4$. Докажите, что $3/4+3/4+3/4+3/4=3$.
34. Постройте красно-синий бамбук Хакенбуш для игры со значением $1/3$. Докажите, что $1/3+1/3+1/3=1$.
35. Постройте красно-синий бамбук Хакенбуш для игры со значением $1/4$. Докажите, что $1/4+3/4=1$.
36. Одноцветный Хакенбуш. Докажите, что если компонента в Хакенбуше имеет только синие ребра, то значение этой игры равно количеству ребер вне зависимости от структуры графа.
37. Докажите, что если $A=\{L|R\}$, где для всех $a_L \in L$, $a_R \in R$ выполнено $a_L < a_R$, то для всех $a_L \in L$, $a_R \in R$ выполнено $a_L < A < a_R$.
38. Разрезание пирога. Есть прямоугольный клетчатый пирог, высота $m$, ширина $n$. Своим ходом L может разрезать пирог горизонтальным разрезом по границам квадратиков, а R - вертикальным разрезом по границам квадратиков. Игра продолжается на нескольких пирогах. Кто не может ходить, проигрывает. Чему равно значение игры на пироге $1\times n$? $m\times 1$?
39. Чему равно значение игры в разрезание пирога для пирога $m \times n$?
40. Разрезание пирога 2.0. Теперь L разрезает пирог горизонтальным разрезом по границам квадратиков на любое число равных частей. Аналогично поступает R, но вертикальным разрезом. Проанализируйте эту игру.
41. Для определения произведения игр с лекции докажите ассоциативность и коммутативность.
42. Докажите, что $a\cdot 1=a$.
43. Докажите, что $a\cdot 0=0$.
44. Докажите, что $a\cdot (-b)=-(a\cdot b)$.
45. Докажите, что для целых чисел $a\cdot b = (ab)$.
46. Докажите, что для целого положительного $k$ выполнено $a\cdot k = a+a+\ldots+a$ (сумма $k$ слагаемых)
47. Докажите распределительный закон $(a+b)\cdot c=a\cdot c + b\cdot c$.
48. Докажите, что для любого $a$ существует игра $a^{-1}$. Тем самым класс $No$ наделен структурой поля.
49. Чему равно $\omega\cdot k$ для целого $k$?
50. Постройте игру $1/\omega$.
51. Постройте игру $\sqrt{\omega}$.
52. Рассмотрим множество допустимых решений системы неравенств $x \ge 0$, $Ax \le b$. Докажите, что множество допустимых решений выпукло.
53. Рассмотрим множество оптимальных решений задачи линейного программирования $x \ge 0$, $Ax \le b$, $c^Tx \to \mathrm{max}$. Докажите, что множество оптимальных решений выпукло.
54. Рассмотрим множество оптимальных решений задачи линейного программирования $Ax \le b$, $c^Tx \to \mathrm{max}$ (условия $x \ge 0$, если они нужны, добавим в $Ax\le b$). Пусть количество переменных $n$, количество неравенств $m$, пусть $rank(A)=n$. Будем называть вершиной точку $\tilde x$, для которой существует $n$ строк матрицы $A$, которые являются линейно независимыми, такую что если составить их них матрицу $\tilde A$ и соответственно вектор $\tilde b$, то выполнено $\tilde A\tilde x=\tilde b$. Докажите, что оптимальное решение, если оно существует, достигается в вершине.
55. Какое минимальное и максимальное число вершин может быть у множества допустимых решений задачи линейного программирования $x \ge 0$, $Ax \le b$?
56. Рассмотрим модификацию задачи линейного программирования, где нет ограничения $x \ge 0$. То есть есть лишь система линейных неравенств $Ax \le b$. Как может выглядеть множество решений такой системы? В чем отличие от решения задачи в канонической постановке?
57. Сведите задачу проверки пустоты множества решений системы неравенств $Ax \le b$ к задаче линейного программирования с допустимым решением $\vec x = 0$, чтобы существование решения исходной задачи соответствовало какому-либо условию на значение функции максимизации.
58. Сведите задачу линейного программирования к задаче проверки пустоты пустоты множества решений системы неравенств $Ax \le b$.
59. Приведите пример задачи линейного программирования с двумя переменными, у которой единственное решение.
60. Приведите пример задачи линейного программирования с двумя переменными, у которой конечное количество решений, но решение не единственное.
61. Приведите пример задачи линейного программирования с двумя переменными, у которой бесконечное количество решений.
62. Приведите пример задачи линейного программирования с двумя переменными, у которой нет допустимого решения.
63. Приведите пример задачи линейного программирования с двумя переменными, у которой нет оптимального решения.
64. Приведите пример системы линейных неравенств с двумя переменными, у задачи линейного программирования для которой существует оптимальное решение для любой целевой функции.
65. Приведите пример системы линейных неравенств с двумя переменными, у задачи линейного программирования для которой существует единственное оптимальное решение для любой целевой функции.
66. Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}2&3\\-1&2\end{array}\right)$
67. Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}-1&1\\1&-1\end{array}\right)$
68. Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}-1&2\\1&-2\end{array}\right)$
69. Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}-2&1\\1&-2\end{array}\right)$
70. Запишите игру "камень-ножницы-бумага" как матричную игру. Найдите оптимальные смешанные стратегии для обоих игроков.
71. Найдите все точки равновесия по Нэшу в биматричной игре $\left(\begin{array}{cc}(5, 2)&(-1, -1)\\(-1,-1)&(2,5)\end{array}\right)$
72. Обобщите понятие антагонистичкой игры на трех игроков. Пусть игра бескоалиционная. Запишите соответствующую задачу линейного программирования.
73. Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Приведите пример выборов для 3 кандидатов, где в указанной схеме будет избран кандидат, который не является первым в списке предпочтений ни у кого из избирателей.
74. Выборы в Флатландии проходят по следующей схеме. Каждый из $n$ избирателей имеет список предпочтения кандидатов. В каждом туре каждый избиратель голосует за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Для какого максимального $0 \le k \le 1$ в результате выборов для 3 кандидатов может выиграть кандидат, который находится на последнем месте в списках предпочтения у $kn$ избирателей?
75. Выборы в Флатландии проходят по следующей схеме. Каждый из $n$ избирателей имеет список предпочтения кандидатов. В каждом туре каждый избиратель голосует за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Для какого максимального $1 \le k \le m$ в результате выборов для $m$ кандидатов может выиграть кандидат, который находится не выше $k$-го места в списке предпочтений у всех избирателей?
76. Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После первого тура остаются два кандидата, набравшие максимальное число голосов. Приведите пример выборов для 3 кандидатов, где в указанной схеме будет избран кандидат, который не является первым в списке предпочтений ни у кого из избирателей.
77. Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После первого тура остаются два кандидата, набравшие максимальное число голосов. того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Для какого максимального $0 \le k \le 1$ в результате выборов для 3 кандидатов может выиграть кандидат, который находится на последнем месте в списках предпочтения у $kn$ избирателей?
78. Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После первого тура остаются два кандидата, набравшие максимальное число голосов. Для какого максимального $1 \le k \le m$ в результате выборов для $m$ кандидатов может выиграть кандидат, который находится не выше $k$-го места в списке предпочтений у всех избирателей?
79. В аукционе принимает участие три агента, ценности предмета аукциона для них $a$, $b$ и $c$. Ценности других агентов не известны. Каждый агент делает ставку, выигрывает тот, кто поставил максимальную ставку, но платит он цену, равную минимальной ставке. Проанализируйте возможные стратегии для этого аукциона.
80. В аукционе принимает участие три агента, ценности предмета аукциона для них $a$, $b$ и $c$. Все агенты знают все три числа. Каждый агент делает ставку, выигрывает тот, кто поставил максимальную ставку, но платит он цену, равную минимальной ставке. Проанализируйте возможные стратегии для этого аукциона.