Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в любую кучу один камень;
б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 80. В начальный момент в первой куче было 8 камней, а во второй – S камней, 1 ≤ S ≤ 71.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
A. Для игры, описанной в предыдущем задании, найдите два таких значения S, при
которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
B. . Для игры, описанной в задании 1, найдите значение S, при котором одновременно
выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при
любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
а) Найдем минимальное значение S, при котором Ваня выиграет своим первым ходом после неудачного первого хода Пети.
Пусть в начальный момент Петя добавляет в первую кучу один камень, тогда в первой куче будет 9 камней. Ваня добавляет во вторую кучу столько камней, сколько их в данный момент в другой куче, то есть 9 камней. Теперь в первой и второй кучах у нас 9 камней.
На втором ходу Петя добавит в первую кучу еще один камень, и теперь в первой куче будет 10 камней. Ваня добавляет во вторую кучу столько камней, сколько их в данный момент в другой куче, то есть 10 камней. Теперь в первой и второй кучах у нас 10 камней.
На третьем ходу Петя добавит в первую кучу один камень, и теперь в первой куче будет 11 камней. Ваня добавляет во вторую кучу столько камней, сколько их в данный момент в другой куче, то есть 11 камней. Теперь в первой и второй кучах у нас 11 камней.
Таким образом, Ване удается выиграть за 3 хода после первого неудачного хода Пети. Минимальное значение S, при котором это возможно, равно 11.
б) Теперь найдем два значения S, при которых у Пети есть выигрышная стратегия и он может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Один из возможных вариантов - если S = 1. В начальный момент первая куча содержит 8 камней, а вторая куча содержит 1 камень. Петя добавляет в первую кучу один камень, и вторая куча остается без изменений. Теперь в первой и второй кучах у нас 9 камней.
На втором ходу Ваня добавляет в первую кучу один камень, и они становятся равными, в обеих кучах по 9 камней. Здесь у Пети есть возможность выиграть своим вторым ходом. Он может добавить в первую кучу 9 камней, и тогда в обеих кучах будет 18 камней, что является не менее 80.
Еще один вариант - если S = 29. В начальный момент первая куча содержит 8 камней, а вторая куча содержит 29 камней. Петя добавляет в первую кучу один камень, и вторая куча становится равной первой - 9 камней.
На втором ходу Ваня должен добавить в первую кучу не меньше 9 камней, чтобы Петя не смог выиграть за один ход. После очередного хода Вани количество камней в первой и второй кучах равны 9.
На третьем ходу Петя добавит в первую кучу один камень, и вторая куча становится равной первой - 10 камней.
Ваня должен добавить в первую кучу не меньше 10 камней, чтобы Петя не смог выиграть за один ход. После очередного хода Вани количество камней в первой и второй кучах снова станут равными 10.
Теперь у Пети есть возможность выиграть своим вторым ходом. Он может добавить в первую кучу 10 камней, и тогда в обеих кучах будет 20 камней, что является не менее 80.
Таким образом, два значения S, при которых у Пети есть выигрышная стратегия и он может выиграть своим вторым ходом независимо от ходов Вани, равны 1 и 29.
в) Для третей части задания необходимо знать текст задачи.