1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Игра в поддавки: кто не может сделать ход, тот выигрывает. Предъявите пример суммы двух проигрышных игр в поддавки, которая является выигрышной.
# Ним в поддавки. Докажите, что за исключением случая, когда все кучки имеют размер $1$, позиция в ниме в поддавки является выигрышной тогда и только тогда, когда она является выигрышной в обычном ниме.
# В этой серии только четкие игры. Немного арифметики. Постройте красно-синий бамбук Хакенбуш для игры со значением $3/4$. Докажите, что $3/4+3/4+3/4+3/4=3$.
# Постройте красно-синий бамбук Хакенбуш для игры со значением $1/3$. Докажите, что $1/3+1/3+1/3=1$.
# Постройте красно-синий бамбук Хакенбуш для игры со значением $1/4$. Докажите, что $1/4+3/4=1$.
# Одноцветный Хакенбуш. Докажите, что если компонента в Хакенбуше имеет только синие ребра, то значение этой игры равно количеству ребер вне зависимости от структуры графа.
# Докажите, что если $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$.
# Разрезание пирога. Есть прямоугольный клетчатый пирог, высота $m$, ширина $n$. Своим ходом L может разрезать пирог горизонтальным разрезом по границам квадратиков, а R - вертикальным разрезом по границам квадратиков. Игра продолжается на нескольких пирогах. Кто не может ходить, проигрывает. Чему равно значение игры на пироге $1\times n$? $m\times 1$?
# Чему равно значение игры в разрезание пирога для пирога $m \times n$?
# Разрезание пирога 2.0. Теперь L разрезает пирог горизонтальным разрезом по границам квадратиков на любое число равных частей. Аналогично поступает R, но вертикальным разрезом. Проанализируйте эту игру.
# Для определения произведения игр с лекции докажите ассоциативность и коммутативность.
# Докажите, что $a\cdot 1=a$.
# Докажите, что $a\cdot 0=0$.
# Докажите, что $a\cdot (-b)=-(a\cdot b)$.
# Докажите, что для целых чисел $a\cdot b = (ab)$.
# Докажите, что для целого положительного $k$ выполнено $a\cdot k = a+a+\ldots+a$ (сумма $k$ слагаемых)
# Докажите распределительный закон $(a+b)\cdot c=a\cdot c + b\cdot c$.
# Докажите, что для любого $a$ существует игра $a^{-1}$. Тем самым класс $No$ наделен структурой поля.
# Чему равно $\omega\cdot k$ для целого $k$?
# Постройте игру $1/\omega$.
# Постройте игру $\sqrt{\omega}$.
# Рассмотрим множество допустимых решений системы неравенств $x \ge 0$, $Ax \le b$. Докажите, что множество допустимых решений выпукло.
# Рассмотрим множество оптимальных решений задачи линейного программирования $x \ge 0$, $Ax \le b$, $c^Tx \to \mathrm{max}$. Докажите, что множество оптимальных решений выпукло.
# Рассмотрим множество оптимальных решений задачи линейного программирования $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$. Докажите, что оптимальное решение, если оно существует, достигается в вершине.
# Какое минимальное и максимальное число вершин может быть у множества допустимых решений задачи линейного программирования $x \ge 0$, $Ax \le b$?
# Рассмотрим модификацию задачи линейного программирования, где нет ограничения $x \ge 0$. То есть есть лишь система линейных неравенств $Ax \le b$. Как может выглядеть множество решений такой системы? В чем отличие от решения задачи в канонической постановке?
# Сведите задачу проверки пустоты множества решений системы неравенств $Ax \le b$ к задаче линейного программирования с допустимым решением $\vec x = 0$, чтобы существование решения исходной задачи соответствовало какому-либо условию на значение функции максимизации.
# Сведите задачу линейного программирования к задаче проверки пустоты пустоты множества решений системы неравенств $Ax \le b$.
# Приведите пример задачи линейного программирования с двумя переменными, у которой единственное решение.
# Приведите пример задачи линейного программирования с двумя переменными, у которой конечное количество решений, но решение не единственное.
# Приведите пример задачи линейного программирования с двумя переменными, у которой бесконечное количество решений.
# Приведите пример задачи линейного программирования с двумя переменными, у которой нет допустимого решения.
# Приведите пример задачи линейного программирования с двумя переменными, у которой нет оптимального решения.
# Приведите пример системы линейных неравенств с двумя переменными, у задачи линейного программирования для которой существует оптимальное решение для любой целевой функции.
# Приведите пример системы линейных неравенств с двумя переменными, у задачи линейного программирования для которой существует единственное оптимальное решение для любой целевой функции.
# Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}2&3\\-1&2\end{array}\right)$
# Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}-1&1\\1&-1\end{array}\right)$
# Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}-1&2\\1&-2\end{array}\right)$
# Найдите оптимальную смешанную стратегию для обоих игроков в игре на матрице $\left(\begin{array}{cc}-2&1\\1&-2\end{array}\right)$
# Запишите игру "камень-ножницы-бумага" как матричную игру. Найдите оптимальные смешанные стратегии для обоих игроков.
# Найдите все точки равновесия по Нэшу в биматричной игре $\left(\begin{array}{cc}(5, 2)&(-1, -1)\\(-1,-1)&(2,5)\end{array}\right)$
# Обобщите понятие антагонистичкой игры на трех игроков. Пусть игра бескоалиционная. Запишите соответствующую задачу линейного программирования.
# Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Приведите пример выборов для 3 кандидатов, где в указанной схеме будет избран кандидат, который не является первым в списке предпочтений ни у кого из избирателей.
# Выборы в Флатландии проходят по следующей схеме. Каждый из $n$ избирателей имеет список предпочтения кандидатов. В каждом туре каждый избиратель голосует за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Для какого максимального $0 \le k \le 1$ в результате выборов для 3 кандидатов может выиграть кандидат, который находится на последнем месте в списках предпочтения у $kn$ избирателей?
# Выборы в Флатландии проходят по следующей схеме. Каждый из $n$ избирателей имеет список предпочтения кандидатов. В каждом туре каждый избиратель голосует за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Для какого максимального $1 \le k \le m$ в результате выборов для $m$ кандидатов может выиграть кандидат, который находится не выше $k$-го места в списке предпочтений у всех избирателей?
# Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После первого тура остаются два кандидата, набравшие максимальное число голосов. Приведите пример выборов для 3 кандидатов, где в указанной схеме будет избран кандидат, который не является первым в списке предпочтений ни у кого из избирателей.
# Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После первого тура остаются два кандидата, набравшие максимальное число голосов. того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После каждого тура кандидат, набравший минимальное число голосов, выбывает, если ничья, выбывает случайный из проигравших. Для какого максимального $0 \le k \le 1$ в результате выборов для 3 кандидатов может выиграть кандидат, который находится на последнем месте в списках предпочтения у $kn$ избирателей?
# Выборы в Флатландии проходят по следующей схеме. Каждый избиратель имеет список предпочтения кандидатов. В каждом туре каждый участник избиратель за того из оставшихся кандидатов, который в его списке идет на самом высоком месте. После первого тура остаются два кандидата, набравшие максимальное число голосов. Для какого максимального $1 \le k \le m$ в результате выборов для $m$ кандидатов может выиграть кандидат, который находится не выше $k$-го места в списке предпочтений у всех избирателей?
# В аукционе принимает участие три агента, ценности предмета аукциона для них $a$, $b$ и $c$. Ценности других агентов не известны. Каждый агент делает ставку, выигрывает тот, кто поставил максимальную ставку, но платит он цену, равную минимальной ставке. Проанализируйте возможные стратегии для этого аукциона.
# В аукционе принимает участие три агента, ценности предмета аукциона для них $a$, $b$ и $c$. Все агенты знают все три числа. Каждый агент делает ставку, выигрывает тот, кто поставил максимальную ставку, но платит он цену, равную минимальной ставке. Проанализируйте возможные стратегии для этого аукциона.