Семинар лаборатории теоретической информатики: "Функции Шпрага-Гранди (ШГ) игры НИМ на гиперграфе." Докладчик: В. Гурвич

На очередном семинаре лаборатории теоретической информатики в среду 14 ноября состоится доклад  
Владимира Гурвича 
"Функции Шпрага-Гранди (ШГ) игры НИМ на гиперграфе". 
Время проведения:18:10 - 19:30 
Адрес мероприятия: Кочновский проезд, д. 3, ауд. 503 
Заказ пропуска: evavilova@hse.ru

Аннотация

Мы рассматриваем следующее, весьма широкое, обобщение игры НИМ.
Имеется $n$ кучек содержащих $х_1, ..., х_n$ камней и задан произвольный гиперграф $H$ на множестве вершин $V = \{1,..., n\}$. Ход состоит в выборе любого ребра $e \in H$ и (строгом) уменьшении  всех кучек $i \in e$. Игрок, не имеющий хода проиграл (в нормальной версии игры и выиграл в мизерной). Игра называется НИМ на гипперграфе  $H$ и обозначается НИМ-$H$.
Случай $H = \{(1), ..., (n)\}$ соответствует обычной игре НИМ; далее, $H = \{S \subset V | |S| \le k\}$, где $1 \le k \le n$ соответствует игре Мура $НИМ-k$ ; и $H = \{S \subset V | |S| = k\}$, где $1 \le k \le n$ соответствует игре точный $НИМ_k$.
Бутон решил НИМ, вычислив $P$-позиции (0-позиции) в 1901-м. Фактически, он дал явную формулу для функции ШГ (которая была формально введена только в конце 30-х). Мур вычислил 0-позиции своей игры в 1910-м, определив функцию $М(х)$, обобщающую функцию Бутона. В 1962-м Клод Берж утверждал в своей книге "Гиперграфы", что $М(х)$ в точности совпадает с функцией ШГ. Однако, в 1980-м Дженкинс и Майберри показали, что это верно, лишь когда одна из  функций принимает значение 0 или 1. Т.е. 0- и 1-позиции вычислить легко, но уже при $n=4$ и $k=2$ явной формулы для функции ШГ нет. Однако Дженкинс и Майберри нашли такую формулу при $n = k+1$.
Три года назад мы ввели и изучили игру точный $НИМ_k$. Случай $n < 2k$ оказался простым. При этом функция ШГ в $х$ равна максимальной длине партии, начинающейся в $х$. Напротив, случай $n2k$ чересчур сложен: даже 0-позиции неизвестнны. Попробуйте сыграть хотя бы при $n = 5$ и $k = 2$. (Пять кучек камней и брать нужно ровно из двух.) Интереснее всех оказался случай $n = 2k$. При этом функция ШГ задаётся в точности функцией Дженкинса и Майберри для НИМ Мура, только одна из переменных определяется "немного" по-другому.
Оказывается, это не случайное совпадение. Мы нашли очень широкий класс гиперграфов, для которых функция ШГ даётся формулой Дженкинса и Майберри.