Игры на графах (27 апреля 2015)

1. Доказательство Гранди методом таблички
2. Задачи на Гранди
1. Ним: за ход можно брать любое число камней из кучки
2. Спичка: за ход можно брать число спичек от 1 до k
3. Ним, плюс ещё один ход: можно делить кучку на две
4. Игра про Карлсона, Малыша и трёхмерную шоколадку
5. Hacking Bush
6. Игры про пешки 3×N
3. Задачи про DP и ретроанализ
1. Игра с одной кучкой камней. У первого своё множество ходов, у второго своё множество.
2. Игра с двумя кучками камней. У первого своё множество ходов, у второго своё множество.
3. Игра с камнями с новыми правилами: кто не может сделать ход, тот выиграл.
4. Игра на матрице − идём из (1,1) в (N,N), идти только вправо-ввех, первый максимизирует, второй минимизирует
5. [не успеем] Первый пытается дойти из (1,1) в (N,N), а второй пытается ему помешать
6. Мужик убегает от терминатора по клетчатому полю, сможет ли он бежать так, чтобы терминатор его не поймал
7. Ретроанализ: выиграть побстрее
8. Ретроанализ: выиграть помедленней (растянуть удовольствие)
4. Игра на дереве размера 2³²
5. [не успеем] Ним, можно брать из двух кучек
6. [не успеем] Игра в Ним в новыми правилами. Кто не может сделать ход, тот выиграл.