1 Тема от Senya

  • Senya
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-01
  • Сообщений: 11

Тема: Ним в поддавки и теорема Шпрага-Гранди

Ним в поддавки - тотже ним, только кто берет последний камень - проигрывает.. граф игры практически совпадает с графом ним, вот только положение 1 - проигрышное.. а вот 0 какое? точно не проигрышное, иначе 1 - выигрышное.. значит 0 - выигрышное. получается что есть выигрышное состояние, из которого нет переходов.. и что делать? это противоречит части того (про выигрышные и проигрышные состояния) что написано тут http://e-maxx.ru/algo/sprague_grundy ... Хотя игра вроде равноправная.. Или я чето не так понимаю? в любом случае если мы пытаемся посчитать функцию Гранди она получается такойже как у обычного ним. но тогда скажем три кучки по одному камню - ним - выигрываем, а ним в поддавки - проигрываем - не сходится... Так равноправная ли это игра?

Как решать немного по другому вроде понятно, но интересно, как эта задача соотносится с теорией Шпрага-Гранди.

2 Ответ от freopen

  • freopen
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-28
  • Сообщений: 2

Re: Ним в поддавки и теорема Шпрага-Гранди

Предположим, что у нас все кучки из одного камня. Тогда в ниме мы выиграем, если кучек четно, а в поддавках - если нечетно. Теперь пусть есть другие кучки. Сыграем с противником в обычный ним. В какой то момент времени остались только кучки величины 1 (возможно, 0 кучек). Утверждение: тот, кто это сделал - выиграл в ним (очевидно, он просто оставил от этой кучки 0 или 1 камень чтобы сделать нужную четность). Но он же выиграет и в поддавки сыграв в противоположную четность. Теперь видна стратегия:
1. Играть как в обычный ним
2. Когда осталась 1 кучка из >1 камня, оставить от нее 0 или 1 камень, чтобы было нечетно кучек
3. Дальше игра протекает однозначно

3 Ответ от Senya

  • Senya
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-01
  • Сообщений: 11

Re: Ним в поддавки и теорема Шпрага-Гранди

бр, это понятно. собственно про это я и писал

Как решать немного по другому вроде понятно

интересно другое.. (читайте выше)

4 Ответ от freopen Отредактировано freopen (2010-09-26 23:08:42)

  • freopen
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-28
  • Сообщений: 2

Re: Ним в поддавки и теорема Шпрага-Гранди

Я предположил, что надо пояснить самое непонятное. Просто функция Шпрага-Гранди предполагает, что проигравший не может сделать ход. Соответственно, когда игр несколько - проиграл тот, кто не ходит ни в одной игре. Нашу игру так не представить.

ADDED. Сама игра равноправная. Просто ты не можешь разбить эту игру в сумму игр (по кучке на каждую)

5 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Ним в поддавки и теорема Шпрага-Гранди

Добавлю, что насколько я знаю, теория Шпрага-Гранди вообще не обобщается на случай игр в поддавки (misere по-английски). Вроде бы ним в поддавки - одна из немногих игр, для которых это удалось, да и то вон какое шаманство получается smile

Сайтe-maxx