Задача-игра

bars70

на доске число 60.
двое играют в игру
отнимается делитель записанного на доске числа и пишется результат.
проигрывает тот, кто получает 0.
кто выигрывает при правильной игре и как играть?

elena144

Логично, что надо подбирать такой делитель, чтобы после его отнятия осталось простое число. Я так понимаю, единицу мы не считаем делителем.

bars70

единица делитель.
не всегда же можно добиваться того, чтоб перед противником было простое число.

Lokomotiv59

Выигрывает первый. Ходить надо так, чтобы после его ходов получалось нечетное число. Тогда после соответствующего хода второго будет обязательно четное число.

olga75olga75

чот я не понял прикола.
Первый вычитает 3. Второму остается 57 - он проиграл.
---
а ну вот поэтому 1 и считается)

vitamin8808

решается просто, как и все подобные игры. Советую вот тут почитать первую главу про Sprague-Grundy function. Если эта функция от позиции нуль — значит проигрыш, если нет — то выигрыш. Ну и ходить из выигранной позиции надо в такую, где значение нуль. Чтобы соперник проиграл.
Хотя в этой игре и так понятно, что чётные позиции выиграны, а нечётные проиграны.
ЗЫ сначала забыл линк на книжку дать. На русском что-то тоже должно быть.

Evgenui

Второму остается 57 - он проиграл.
:smirk:
:smirk:
:smirk:

a7137928

Еще один способ решения подобных задач - решать с конца.
Допустим, первый хочет выиграть. Посмотрим на последний ход. У второго должно быть какое-то такое число, что, как бы он ни пошел, получается 0, и он проигрывает. Какое число перед вторым? Очевидно, это 1, поскольку если второй видит перед собой любое другое число, он может вычесть 1, и игра будет продолжаться.
Теперь смотрим на предпоследний ход. Какое число должно быть перед первым игроком, так чтобы он мог сделать ход и оставить второму число 1? Очевидно, это 2.
Предпредпоследний ход. Какое число перед вторым, чтобы при любом его ходе первому доставалось 2? Это число 3.
Таким образом, если первый оставит второму 1 или 3, то он выиграл.
Третий с конца ход. Как первый мог оставить второму число 3? Только если перед ним было 4 (вычел единицу) или 6 (вычел тройку).
********************
И так далее. Таким образом, мы строим дерево возможных ситуаций и ходов в игре, но начинаем с конца игры, и через некоторое число итераций мы должны определить, к какой ситуации должен вести игру каждый игрок, чтобы выиграть. Предполагается, что такой способ должен натолкнуть на мысль, как решить задачу в общем случае.

vitamin8808

Ну да, простейший способ решения — рисовать граф игры(начиная с конечных позиций) и проставлять В(выигранная) или П(проигранная) возле каждой вершины. Вот только в случае, когда кучек несколько, запаришься. А так есть теорема о том, что Sprague-Grundy function такой игры есть просто nim-sum от фунций от каждой кучки. Даже если для разных кучек правила разные. Типа из первой всё что угодно, из второй только делители можно вычитать, из третьей только чётное не меньше половины, и т.д.

lena1978

:grin:
Оставить комментарий
Имя или ник:
Комментарий: