Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличивать количество камней в куче в три раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 68. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 68 или больше камней.
В начальный момент в первой куче было 8 камней, во второй куче – S камней;
1 ≤ S ≤ 59.
А) При каком минимальном S Петя выигрывает первым ходом?
Б) Назовите значение S, при котором Петя может выиграть своим вторым ходом, независимо от ходов противника. Если таких несколько, укажите минимальное.
В) Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом, независимо от ходов противника. Если таких несколько, укажите минимальное.

Answer 1

(см. объяснение)

Объяснение:

Пункт A:

Пусть во второй куче x камней. Тогда стратегия примет вид:

(8; x)⇒(8; 3x)

По условию 8+3x≥68 ⇒ x≥20.

Так как нам нужно найти минимальное значение, то берем число 20.

Пункт Б:

Здесь многие рекомендуют просто подбирать. Но если вы все время боитесь, что найдете подходящее значение S, а оно не окажется минимальное, попробуйте предложенный ниже вариант.

Напишем программу на языке Python 3:

def f(x, y, p):

   if x + y >= 68 and p == 4:

       return True

   elif x + y < 68 and p < 4:

       if p % 2 > 0:

           return f(x + 2, y, p + 1) or f(x, y + 2, p + 1) or f(3 * x, y, p + 1) or f(x, 3 * y, p + 1)

       else:

           return f(x + 2, y, p + 1) and f(x, y + 2, p + 1) and f(3 * x, y, p + 1) and f(x, 3 * y, p + 1)

   else:

       return False

for i in range(1, 60):

   if f(8, i, 1):

       print(i)

Результатом ее работы будет число 19, поэтому его берем в ответ. Для самоконтроля, найденное число должно быть меньше 20, так как в противном случае Петя выиграет своим первым ходом.

Пункт В:

def f(x, y, p):

   if x + y >= 68 and (p == 5 or p == 3):

       return True

   elif x + y < 68 and p < 5:

       if p % 2 > 0:

           return f(x + 2, y, p + 1) and f(x, y + 2, p + 1) and f(3 * x, y, p + 1) and f(x, 3 * y, p + 1)

       else:

           return f(x + 2, y, p + 1) or f(x, y + 2, p + 1) or f(3 * x, y, p + 1) or f(x, 3 * y, p + 1)

   else:

       return False

for i in range(1, 60):

   if f(8, i, 1):

       print(i)

Результатом работы программы будут два числа: 17 и 18. В ответ берем число 17.

Задание выполнено!