Функция Шпрага-Гранди: различия между версиями

Версия 12:58, 9 февраля 2020

Сведение любой игры к ниму

Пусть есть Ациклический ориентированный граф и игра на нем вида можно перейти по ребру, последний сделавший ход - выиграл, сведем ее к ниму :

Пусть $f(u)$ - функция, сопоставляющая вершине $u$ ним размера $f(u)$

Сопоставим листьям ним размера 0, так как и ним размера 0 и листья - проигрышные позиции.

Для каждого не листа рассмотрим список его сыновей, пусть в этом списке есть все числа от 0 до $x - 1$(возможно не один раз) и что-то еще(числа $> x$), но при этом нет $x$, тогда это значит, что мы стоим в позиции из которой можно перейти в ним размера от 0 до $x - 1$, а это значит, что мы стоим в ниме размера $x$. Данная операция(нахождение минимального неотрицательного числа, которого нет в массиве) называется mex(minimal excluding).

И в самом деле такое сведение верное, так как из проигрышной вершины(в которой стоит не 0) нет перехода в проигрышную вершину(иначе mex был бы не 0). Из выигрышной вершины всегда же есть переход в проигрышную(так как в сыновьях есть 0).

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin

@@ Строка 1: / Строка 1: @@
-Сведение любой игры к ниму :
+==Сведение любой игры к ниму==
 Пусть есть Ациклический ориентированный граф и игра на нем вида можно перейти по ребру, последний сделавший ход - выиграл, сведем ее к ниму :
-Пусть f(u)
+Пусть $f(u)$ - функция, сопоставляющая вершине $u$ ним размера $f(u)$
- - функция, сопоставляющая вершине u
- ним размера f(u)
 Сопоставим листьям ним размера 0, так как и ним размера 0 и листья - проигрышные позиции.
-Для каждого не листа рассмотрим список его сыновей, пусть в этом списке есть все числа от 0 до x−1
+Для каждого не листа рассмотрим список его сыновей, пусть в этом списке есть все числа от 0 до $x - 1$(возможно не один раз) и что-то еще(числа $> x$), но при этом нет $x$, тогда это значит, что мы стоим в позиции из которой можно перейти в ним размера от 0 до $x - 1$, а это значит, что мы стоим в ниме размера $x$. Данная операция(нахождение минимального неотрицательного числа, которого нет в массиве) называется mex(minimal excluding).
-(возможно не один раз) и что-то еще(числа >x
-), но при этом нет x
-, тогда это значит, что мы стоим в позиции из которой можно перейти в ним размера от 0 до x−1
-, а это значит, что мы стоим в ниме размера x
-. Данная операция(нахождение минимального неотрицательного числа, которого нет в массиве) называется mex(minimal excluding).
 И в самом деле такое сведение верное, так как из проигрышной вершины(в которой стоит не 0) нет перехода в проигрышную вершину(иначе mex был бы не 0). Из выигрышной вершины всегда же есть переход в проигрышную(так как в сыновьях есть 0).
 {{Автор|Глеб Лобанов|glebodin}}