Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу один камень или увеличить количество камней в любой куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 30. начальный момент в первой куче было К камней, а во второй - S камней, 1 ≤K ≤ 29, 1 ≤S ≤29. Ответьте на следующие вопросы: Задание 19. Сколько существует пар (К; S), таких что Ваня выигрывает первым ходом при
любой игре Пети?
Ответы
Чтобы Ваня выиграл первым ходом при любой игре Пети, необходимо, чтобы в начальный момент в обеих кучах было не менее 30 камней. Значит, мы можем рассмотреть только такие пары (K; S), что K + S ≥ 30.
Для каждой такой пары мы можем рассмотреть все возможные ходы Пети и посчитать, какие позиции он может создать. Если при любом ходе Пети Ваня может выиграть первым ходом, то данная пара (K; S) подходит под условие задачи.
Рассмотрим все пары (K; S), где K + S ≥ 30:
(1; 29), (2; 29), ..., (14; 16) - в каждом из этих случаев Петя может увеличить количество камней в одной из куч в два раза, но Ваня может сделать то же самое в другой куче, и в результате суммарное количество камней не изменится. Поэтому Ваня может выиграть первым ходом при любой игре Пети.
(15; 15) - в этом случае Петя может увеличить количество камней в одной из куч в два раза, и вторая куча будет содержать не более 30 камней. Тогда Ваня может увеличить количество камней в этой куче до 30 и выиграть первым ходом.
(16; 14), (17; 13), ..., (29; 1) - в каждом из этих случаев Петя может увеличить количество камней в одной из куч в два раза, и Ваня может сделать то же самое в другой куче, и в результате суммарное количество камней будет не менее 30. Поэтому Ваня может выиграть первым ходом при любой игре Пети.
Итак, всего существует 29 пар (K; S), таких что Ваня выигрывает первым ходом при любой игре Пети.