Задача 1 Два игрока, Федя и Стёпа, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Федя. За один ход игрок может: а) добавить в любую кучу один камень; б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 81, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, а во второй S камней, Известно, что Степа выиграл своим первым ходом после первого хода Феди. Найдите минимальное значение S, при котором это возможно.

Кратко: ищем минимальное S такое, чтобы после первого хода Феди можно было на следующем ходе Степы выиграть мгновенно (то есть довести сумму камней до не менее 81). 1) Возможные ходы Феди из позиции (A, B) = (7, S): - a) увеличить любую кучу на 1: (8, S) или (7, S+1) - b) увеличить одну кучу на размер другой: (7+S, S) или (7, S+7) Итак, после первого хода Феди имеют место четыре позиции: 1) (8, S) 2) (7, S+1) 3) (7+S, S) 4) (7, S+7) 2) Условия, чтобы Степа смог выиграть своим первым ходом из каждой позиции. За один ход Степа может увеличить сумму на 1 (плюс 1 к любой куче) или увеличить одну кучу на размер другой (то есть сумма увеличивается на max(1, новая_первичная_крупа)). Следовательно, максимальная сумма после хода Степы из позиции (a, b) равна (a + b) + max(1, a, b). Степа выигрывает, если эта величина ≥ 81. Рассмотрим каждую позицию: 1) (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. 2) (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. 3) (7+S, S): сумма 7 + 2S, максимум max(S+7, S) = S + 7. Условие: (7 + 2S) + (S + 7) ≥ 81 → 3S + 14 ≥ 81 → S ≥ 23. 4) (7, S+7): сумма S + 14, максимум max(7, S+7) = S + 7. Условие: (S + 14) + (S + 7) ≥ 81 → 2S + 21 ≥ 81 → S ≥ 30. 3) Минимально возможное S Из всех условий минимальное S = 23 (из случая 3). 4) Пример для минимального 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.