На столе лежит кучка из спичек
Петя придумал новую игру. На стол кладется кучка из N спичек, и затем Петя с Ваней по очереди берут спички из кучки. Первым берет Петя, ему разрешается взять от 1 до K спичек. Затем игрок может взять любое количество спичек, не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Например, если N = 10, K = 5, то на первом ходу Петя может взять 1, 2, 3, 4 или 5 спичек, если Петя возьмет 3, то на следующем ходу Ваня может взять 1, 2, 3 или 4, и если Ваня возьмет 1, то Петя затем может взять 1 или 2, и т. д. Проигрывает тот, кто возьмет последнюю спичку.
Теперь Петя хочет рассчитать какое количество спичек он должен взять на первом ходу, чтобы выиграть при любой игре Вани. Помогите ему.
Важно заметить, что имеется ввиду нахождение всех возможных вариантов кол-ва спичек, при которых Петя победит.
Обычно подобные задачи решаются методом динамического программирования (то есть находим необходимые решения для кол-ва спичек < N, а затем, зная решения, решаем для N).
Однако конкретно эта задача имеет более элегантное решение.
Код (на языке С++)
Если ваша первая реакция — это недоумение, то это нормально. Сейчас я попробую объяснить, что к чему.
Алгоритм
Суть алгоритма в том, чтобы у противника было всего 2 варианта:
1) оставить противнику ровно одну спичку
2) оставить противнику столько спичек, чтобы для выигрыша ему нужно было забрать больше, чем он может на данном ходе
Этого можно достичь используя «ссылки» на то число спичек, при котором проигрыш второго будет гарантирован. Рассмотрим разные варианты кол-ва спичек:
1 2 3 4 5 6 7 8 9 10 11…
Теперь проанализируем, сколько спичек нужно взять первому игроку, если есть всего 1 спичка, всего 2 и т. д.
То есть, для единицы первый игрок всегда проигрывает, для двойки ему нужно взять 1 спичку, чтобы выиграть, для тройки — 2, четверки — 3, для пяти нам следует «сослаться» на четвёрку, на которой оппонент гарантированно не сможет взять три спички. После этого последовательность повторяется.
Почему 6-ти и 11-ти соответствует 0?
Потому что на первой итерации мы полагаем, что наибольшие кол-во спичек, которые мы можем взять, меньше 5-ти.
Почему меньше 5-ти?
Потому что в последовательности (1) есть переход… 3 1 х…
х не может ссылаться на 3, потому что соперник сможет взять 2 + 1 = 3 спички. Единственный способ — «перепрыгнуть» порог… 3 1… и сослаться на самое начало, однако на первой итерации мы рассматриваем только «ближайшие» ссылки. Таким образом образовался цикл длинной 5.
Следует заметить, что длинна цикла зависит от того, насколько больше спичек может взять соперник.
Таким образом мы обнаружили периодическую последовательность, которая соответствует формуле |(n mod 5) — 1|. Но на самом деле мы можем ссылаться не только на ближайшее подходящее кол-во спичек, но и на другие. Чтобы убедиться в этом на практике достаточно в последовательности (1) предположить, что есть возможность взять до девяти спичек и построить новую последовательность, базируясь на изложенных рассуждениях:
0 1 2 3 1 5 1 2 3 1 0 1 2 3 1 5…
То есть теперь мы находим ссылки по модулю 10, и формула имеет вид |(n mod 10) — 1|.
Дальше тот же процесс нужно повторить по модулю 20, 40 и т.д., пока мы не убедимся, что не получим новых остатков (отсюда ограничения цикла 2 * n + 1).
P.S. Задача была предложена преподавателем на 2-ом курсе университета. Алгоритм придуман мной и моим соседом по комнате. Код протестирован на том же сайте, где было найдено условие.
Урок 8. Знакомство с теорией игр
Два игрока играют в следующую игру: перед игроками лежит куча из 10 монет. Игроки ходят по очереди. За один ход игрок может добавить в кучу 7 или 10 монет. У каждого игрока, чтобы делать ходы, есть неограниченное количество монет. Игра завершается в тот момент, когда количество монет в куче становится не менее 27. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 27 или больше монет. Собери дерево этой игры.
Три игры
Есть три игры «крестики-нолики», игра «Фишка» на поле 3×3 (см. «Построение стратегии») и игра «Куча монет» (см. задание игра «Куча монет»), где начальное количество монеток 5, а положить в кучу можно 3 или 5 монет до достижения 13. Распредели, кто выиграет при безошибочной игре каждого игрока.
ИГРА «СПИЧКИ ДЕТЯМ НЕ ИГРУШКИ!»
В коробке 60 спичек. За один ход можно взять любое количество спичек от 1 до 5. Проигрывает тот, кто не может сделать ход. Кто из игроков выиграет при правильной игре?
Вставь в текст стратегии правильное количество.
Если количество спичек меньше или равно , то тот игрок, чья очередь ходить, заканчивает игру и выигрывает.
Если же количество спичек равно , то игрок, чей ход был до появления этой позиции, свои следующим ходом заканчивает игру. Значит, эта позиция для того, кто ходит.
Аналогично проигрышными являются позиции, когда количество спичек кратно . Значит, и позиция «60 спичек» является для того, кто будет ходить, то есть для игрока.
ИГРА «ФИШКА»
Фишка стоит в углу шахматной доски размером 4 х 4. Двое игроков по очереди передвигают ее вправо или вниз на 1 клетку. Второй раз ходить на поле, где фишка уже побывала, нельзя. Тот, кому некуда ходить, проигрывает. Проставь в таблице все выигрышные («+») и проигрышные («–») позиции.
ИГРА «СПИЧКИ ДЕТЯМ НЕ ИГРУШКИ!»-2
В коробке n спичек. За один ход можно взять любое количество спичек от 1 до m. Проигрывает тот, кто не может сделать ход. Распределите различные варианты игры по группам «Выигрывает первый игрок» и «Выигрывает второй игрок».
Выигрывает первый игрок
Выигрывает второй игрок
ИГРА «ДВЕ КУЧКИ СПИЧЕК»
На столе лежат две кучки спичек: в одной 12, в другой 14 Обозначим количество спичек как (12, 14) Игроки ходят по очереди. За один ход можно взять любое число спичек только из одной из кучек (по выбору игрока). Кто не может сделать ход (спичек не осталось), проигрывает.
Выигрывает первый игрок. Восстановите последовательность игры.
ИГРА «ШОКОЛАДКА»
Шоколадка представляет собой прямоугольник 5×6, разделённый углублениями на 30 квадратиков. Двое по очереди разламывают её на части по углублениям: за один ход можно разломить любой из кусков (больший одного квадратика) на два. Кто не может сделать хода (все куски уже разломаны), проигрывает. Вставьте пропущенные слова в построение стратегии.
В этой игре шоколадку можно разломить ровно раз, так как при каждом разломе число кусков увеличивается ровно на . В начале игры был 1 кусок (вся шоколадка), а в конце кусков. Значит, всего было ходов. Первый игрок при этом делал ходы, а второй — . Поэтому последний ход сделал игрок, то есть выиграл.
ИГРА «ОДНОСТОРОННЯЯ ЛАДЬЯ»
Выигрышная стратегия
Маша с Васей играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй — 3 камня. Игроки ходят по очереди, первый ход делает Маша. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Игра завершается в тот момент, когда количество камней в одной из куч становится не менее 20. Если в момент завершения игры общее число камней в двух кучах не менее 28, то выиграл Вася, в противном случае — Маша. При безошибочной игре обоих игроков выигрывает Вася. Соберите его выигрышную стратегию.
Анализ графов
ИГРА «БАШЕ»
Выберите верный ответ.
Имеется кучка из n камней. За один ход разрешается взять из нее не более k камней. Играют двое, ходы делают по очереди. Проигрывает тот, кто не может сделать ход.
Инвариантом стратегии для произвольной пары (n,k) является условие ?
* запись a mod b=0 означает, что a нацело делится на b
Инвариант стратегии
Двое по очереди ломают шоколадку m*n. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход. Инвариантом стратегии первого игрока является условие .
Выигрышные стратегии
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится более 200. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 201 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 200.
а) Если S от до , то Петя может выиграть первым ходом.
б) Если S равно , то Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
в) Если S равно , то у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом.
г) Если S равно , то у Пети есть выигрышная стратегия, причём Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня, или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 24. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 24 или больше камней.
Введи, недостающие значения, чтоб утверждения были верными.
а) Если S равно от до , то Петя может выиграть в один ход.
в) Если S равно или , то у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход.
Читайте также: