Задача 1 Два игрока, Федя и Стёпа, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Федя. За один ход игрок может: а)…
Задача 1 Два игрока, Федя и Стёпа, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Федя. За один ход игрок может: а) добавить в любую кучу один камень; б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 81, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, а во второй S камней, Известно, что Степа выиграл своим первым ходом после первого хода Феди. Найдите минимальное значение S, при котором это возможно.
Кратко: ищем минимальное S такое, чтобы после первого хода Феди можно было на следующем ходе Степы выиграть мгновенно (то есть довести сумму камней до не менее 81).
- Возможные ходы Феди из позиции (A, B) = (7, S):
- a) увеличить любую кучу на 1: (8, S) или (7, S+1)
- b) увеличить одну кучу на размер другой: (7+S, S) или (7, S+7)
Итак, после первого хода Феди имеют место четыре позиции:
(8, S)
(7, S+1)
(7+S, S)
(7, S+7)
Условия, чтобы Степа смог выиграть своим первым ходом из каждой позиции. За один ход Степа может увеличить сумму на 1 (плюс 1 к любой куче) или увеличить одну кучу на размер другой (то есть сумма увеличивается на max(1, новая_первичная_крупа)). Следовательно, максимальная сумма после хода Степы из позиции (a, b) равна (a + b) + max(1, a, b). Степа выигрывает, если эта величина ≥ 81.
Рассмотрим каждую позицию:
- (8, S): сумма 8 + S, максимум между 8 и S — max(8, S). Неравенство: (8 + S) + max(8, S) ≥ 81.
- Если S ≥ 8: 2S + 8 ≥ 81 → S ≥ 37.
- Если S ≤ 7: S + 16 ≥ 81 → S ≥ 65 (невыполнимо для S ≤ 7). Минимальное требование: S ≥ 37.
- (7, S+1): сумма S + 8, максимум max(7, S+1).
- Если S + 1 ≥ 7 (то есть S ≥ 6): (S + 8) + (S + 1) ≥ 81 → 2S + 9 ≥ 81 → S ≥ 36.
- Если S ≤ 5: (S + 8) + 7 ≥ 81 → S ≥ 66 (невыполнимо). Минимальное требование: S ≥ 36.
(7+S, S): сумма 7 + 2S, максимум max(S+7, S) = S + 7. Условие: (7 + 2S) + (S + 7) ≥ 81 → 3S + 14 ≥ 81 → S ≥ 23.
(7, S+7): сумма S + 14, максимум max(7, S+7) = S + 7. Условие: (S + 14) + (S + 7) ≥ 81 → 2S + 21 ≥ 81 → S ≥ 30.
Минимально возможное S Из всех условий минимальное S = 23 (из случая 3).
Пример для минимального S = 23
- Начальное: (7, 23).
- Ход Феди: увеличить первую кучу на размер другой, т.е. A → A + B = 7 + 23 = 30. Позиция становится (30, 23).
- Ход Степы: он может увеличить вторую кучу на размер первой (плохой ход Феди уже сломал тактику Феди), т. е. B → B + A = 23 + 30 = 53. Новая сумма = 30 + 53 = 83 ≥ 81. Степа выигрывает.
Итак, минимальное значение S, при котором существует ход Феди, после которого Степа может выиграть своим первым ходом, равно 23.
Ответ: S_min = 23.
