"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а)…
"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 89. В начальный момент в куче было S камней, 1 <= S < 89. Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Назовите минимальное значение S, при котором это возможно. "
Классно, давай разберёмся по шагам. Это очень похожие на задачки с "один ход до победы".
Ключ идеи (подсказка):
- Ваня может выиграть своим первым ходом, если после хода Пети размер кучки X удовлетворяет условию: либо X + 1 ≥ 89, либо 2X ≥ 89. Это эквивалентно X ≥ 45, потому что при X = 45 уже 2X = 90.
- Петя на первом ходу может получить X из двух вариантов: S + 1 или 2S. Чтобы у Вани был шанс выиграть на его первом ходу, должен существовать выбор Пети, дающий X ≥ 45.
- Так как 2S всегда больше или равно S + 1 для любого S ≥ 1, максимум после первого хода Пети равен 2S. Значит условие существования такого хода Пети — 2S ≥ 45.
- Решая 2S ≥ 45, получаем S ≥ 22.5, то есть минимальное целое S = 23.
- Пример: S = 23. Петя может удвоить кучу до 46. Теперь Ваня может сделать, например, удвоение до 92 и победить сразу.
Почему для меньших S это невозможно:
- Если S ≤ 22, то 2S ≤ 44, а S + 1 ≤ 23. Ни один из ходов Пети не даёт X ≥ 45, значит у Вани нет хода, который привёл бы к победе за один ход.
Итого: минимальное S = 23. Специальный пример подтверждает: Петя может выбрать удвоение, получив 46, и Ваня выигрывает в свой ход.
Хочешь, могу показать ещё чуть подробнее по таблице позиций или проверить другие варианты? Поставь лайк или дизлайк.
