Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 20 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней; 1 S 40. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Найдите минимальное значениеS, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Привет! Давай разберемся с твоим ответом на задание по информатике.
Так, в задаче речь идет о том чтобы найти такое начальное число камней в куче (S), при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но при этом нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Твой ответ "21" неверен, потому что если в начале игры будет 21 камень, тогда Ваня выиграет сразу, утроив количество камней (21 * 3 = 63, что больше 41).
Правильный ответ на задачу - "7". Давай разберем почему:
Если в начальный момент в куче 7 камней, Петя может сделать один из трех ходов:
- Добавить 1 камень, будет 8.
- Добавить 5 камней, будет 12.
- Утроить количество камней, будет 21.
Если после хода Пети получится 21 камень, Ваня сразу выиграет, утроив количество камней. Это не удовлетворяет условиям задачи, так как Ване нельзя выиграть первым ходом.
Поэтому Петя не будет выбирать ход утроение камней с 7 до 21.
Если Петя добавит один камень (будет 8) или пять камней (будет 12), Ваня в ответ может сделать так, чтобы в итоге получилось 13 камней (добавив 5 камней в первом случае, или 1 камень во втором).
Теперь, после хода Вани, Пете не удастся выиграть одним ходом, так как даже утроив количество камней (13 * 3), он получит 39 камней, что меньше 41. А вне зависимости от действий Пети, Ваня выиграет следующим ходом, так как
- Следующее возможное утроение с 39 камней даст ему 117 камней.
- Добавление одного камня к 39 даст 40, и Ваня выиграет, добавив еще один.
- При добавлении Петей пяти камней ко всем вариантам суммы ниже 36, Ваня также сможет выиграть, утроив число камней или добавив недостающее количество.
Так что минимальное значение S, позволяющее Ване выиграть либо первым, либо вторым ходом и не иметь возможности выиграть сразу первым ходом, действительно равно 7.
Надеюсь, теперь стало понятно, как найти правильное решение. Оцени мой ответ лайком или дизлайком, чтобы я знал, нужно ли мне что-то улучшить в обяснениях.
