Кажется ситуация типичная и есть готовые алгоритмы, но не могу вспомнить как их найти и сам сходу не решил.
Игра — два участника сидят перед столом на котором лежит X печенек. Они начинают есть печенье по очереди, от n до m, печенек за ход. Побеждает участник, который съел последнее печенье. То есть соперник не может съесть либо по причине отсутствия печенья либо его осталось меньше n.
Кажется здесь должна быть стратегия победы для игрока, совершающего первый ход, ведь у него больше свободы действий. Это опровергается тем, что после его хода тип задачи не меняется, меняется только X а ход уже у другого игрока.
Понятно, что к моменту когда X между n и m, игрок 1 побеждает. Но есть ли гарантированная стратегия прихода к этому состоянию при больших X (> 100*m)?
Z>Кажется ситуация типичная и есть готовые алгоритмы, но не могу вспомнить как их найти и сам сходу не решил.
Z>Игра — два участника сидят перед столом на котором лежит X печенек. Они начинают есть печенье по очереди, от n до m, печенек за ход. Побеждает участник, который съел последнее печенье. То есть соперник не может съесть либо по причине отсутствия печенья либо его осталось меньше n.
Z>Кажется здесь должна быть стратегия победы для игрока, совершающего первый ход, ведь у него больше свободы действий. Это опровергается тем, что после его хода тип задачи не меняется, меняется только X а ход уже у другого игрока.
Z>Понятно, что к моменту когда X между n и m, игрок 1 побеждает. Но есть ли гарантированная стратегия прихода к этому состоянию при больших X (> 100*m)?
Здравствуйте, Ziaw, Вы писали:
Z>Игра — два участника сидят перед столом на котором лежит X печенек. Они начинают есть печенье по очереди, от n до m, печенек за ход. Побеждает участник, который съел последнее печенье. То есть соперник не может съесть либо по причине отсутствия печенья либо его осталось меньше n.
Это похоже на игру из шоу Форт Бойар, только там n = 1. Я в детстве навязывал детям во дворе эту игру, где ставками были фишки — потому что систематически успешно метать фишки не умел, а считать умел :)
Z>Кажется здесь должна быть стратегия победы для игрока, совершающего первый ход, ведь у него больше свободы действий. Это опровергается тем, что после его хода тип задачи не меняется, меняется только X а ход уже у другого игрока.
Преимущество у того игрока, который сможет своим ходом восстановить выгодный ему инвариант. В оригинальной игре с n = 1, m = 3 этот инвариант — кратность четырём. Если число печенек изначально кратно 4, то преимущество у второго игрока. Во всех остальных случаях у первого игрока — он может довести своим ходом число печенек до числа, кратного четырём.
Если есть ограничение снизу n > 1, то надо подумать, на что это влияет в стратегии.
Здравствуйте, Ziaw, Вы писали:
Z>Все таки это какой-то форк от Ним, среди описаных в вики не нашел. Может есть варианты как подступиться к задаче?
Предыдущий оратор же указал, что это игра Баше — случай игры Ним с одной кучкой. Кажется, что тебе достаточно именно Баше, там всё сводится к ключевым позициям и правильному алгоритму. Для теоретических работ можно уже обращаться к Ним
Здравствуйте, Ziaw, Вы писали:
Z>Может есть варианты как подступиться к задаче?
Так я ж в соседней ветке предложил вариант. Нужно его просто обобщить.
Можно идти индуктивно. Если ты оставишь оппоненту n + m печенек в конце игры, то это обеспечит тебе выигрыш, не так ли?
Если он возьмёт k ∈ [n..m] печенек, то ты возьмёшь остаток (n + m − k) ∈ [n..m].
Значит тебе нужно решить задачу уже для меньшего числа печенек.
Кажется, победит тот, кто сможет после своего хода поддерживать инвариант «число оставшихся печенек кратно (n + m)».
Здравствуйте, Qbit86, Вы писали:
Q>Так я ж в соседней ветке предложил вариант. Нужно его просто обобщить. Q>Можно идти индуктивно. Если ты оставишь оппоненту n + m печенек в конце игры, то это обеспечит тебе выигрыш, не так ли? Q>Если он возьмёт k ∈ [n..m] печенек, то ты возьмёшь остаток (n + m − k) ∈ [n..m]. Q>Значит тебе нужно решить задачу уже для меньшего числа печенек.
Q>Кажется, победит тот, кто сможет после своего хода поддерживать инвариант «число оставшихся печенек кратно (n + m)».
Здравствуйте, Ziaw, Вы писали:
Z>Да, действительно, это решение. Спасибо!
Надо ещё рассмотреть ситуацию перед первым ходом.
Пусть остаток от деления числа печенек на (n + m) будет r.
Первому игроку хорошо бы съесть r.
Но вдруг r меньше n?
В общем, выиграет ли первый или второй игрок зависит от этого остатка r.
Может быть я чего-то не понял, но с первого взгляда кажется, что тут прсто остаток от деления.
Предположим есть k печенек, n — кол-во печенек за ход игрока №1, m — кол-во печенек за ход игрока №2.
То игрок №1 побеждает всегда, когда остаток от деления k mod (n + m) >= n.
В любом другом случае на промежутке [0, n) побеждает второй игрок.
