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.

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

Answer 2

Давайте рассмотрим каждую часть задачи по очереди:

А) При каком минимальном S Петя выигрывает первым ходом?

Петя выигрывает первым ходом, если он может так изменить количество камней во второй куче, чтобы сумма в обеих кучах стала не менее 68. Для этого вторая куча S должна быть не меньше 68 - 8 = 60 камней. Таким образом, минимальное значение S, при котором Петя выигрывает первым ходом, равно 60.

Б) Назовите значение S, при котором Петя может выиграть своим вторым ходом, независимо от ходов противника. Если таких несколько, укажите минимальное.

Чтобы Петя выиграл своим вторым ходом, он должен создать ситуацию, в которой после его хода вторая куча станет не меньше 68. Поскольку первый ход делает Петя, второй ход Вани, Петя может выбрать S так, чтобы после своего хода вторая куча имела 68 или больше камней. Петя может увеличить S в 3 раза, чтобы создать такую ситуацию:

S * 3 >= 68

Минимальное значение S, удовлетворяющее этому неравенству, равно:

S = ceil(68 / 3) = 23

Таким образом, минимальное значение S, при котором Петя может выиграть своим вторым ходом, равно 23.

В) Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом, независимо от ходов противника. Если таких несколько, укажите минимальное.

Чтобы Ваня выиграл своим первым или вторым ходом, первая куча должна содержать такое количество камней, что после хода Вани сумма в обеих кучах станет не менее 68. В этом случае Ваня может контролировать игру и выиграть.

Для минимального значения S, Ваня может увеличить S в 3 раза, чтобы создать такую ситуацию:

S * 3 >= 68

Минимальное значение S, удовлетворяющее этому неравенству, равно:

S = ceil(68 / 3) = 23

Таким образом, минимальное значение S, при котором Ваня выигрывает своим первым или вторым ходом, независимо от ходов противника, также равно 23.