Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в четыре раза. Например, пусть в одной куче 7 камней, а в другой 9 камней; такую позицию мы будем обозначать (7, 9). За один ход из позиции (7, 9) можно получить любую из четырёх позиций: (8, 9), (28, 9), (7, 10), (7, 36). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 151. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 151 или больше камней.
В начальный момент в первой куче было 9 камней, во второй куче — S камней; 1 ≤ S ≤ 141.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна
295
423
Ответы на вопрос:
Заметим, что игра должна закончиться в 2 хода. Минимальное значение количества камней в обеих кучах, при котором игра заканчивается — 77. Эта ситуация возможна, например, когда в первой куче 7 камней, а во второй — 70. Значит, чтобы Ваня мог выиграть своим первым ходом, количество камней во второй куче должно быть ≥35. Поскольку удваиванием число 35 получить нельзя, после первого хода Пети во второй куче должно получиться 36 камней. Это возможно при значении S = 18. При таком минимальном значении S Ваня выиграет своим первым ходом после неудачного хода Пети.
ответ:18.
Реши свою проблему, спроси otvet5GPT
-
Быстро
Мгновенный ответ на твой вопрос -
Точно
Бот обладает знаниями во всех сферах -
Бесплатно
Задай вопрос и получи ответ бесплатно
Популярно: Информатика
-
asya160706.06.2020 12:32
-
Fluttys22.06.2023 10:20
-
davideblan3320.12.2020 17:36
-
abdulismailova220.08.2021 17:31
-
mikhailstrelni08.12.2022 19:41
-
pantehnik77777oz07f114.02.2020 20:12
-
mangleplaydj125.03.2021 20:16
-
Infinity16703.07.2021 16:53
-
Fltkbyf201704.09.2022 23:11
-
dmitrius211.07.2022 06:55
![Caktus Image](/tpl/img/cactus.png)
Есть вопросы?
-
Как otvet5GPT работает?
otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса. -
Сколько это стоит?
Проект находиться на стадии тестирования и все услуги бесплатны. -
Могу ли я использовать otvet5GPT в школе?
Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое! -
В чем отличия от ChatGPT?
otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.