ЕГЭ-2023. Задание 20

Тема: Умение найти выигрышную стратегию игры. Время выполнения 8 минут.

Решение задания № 20 ЕГЭ-2023. Демо.

Условие задачи:

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

– Петя не может выиграть за один ход;

– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

я.п. Python:

def F(x,p):

    if x >= 129 and p==4: return True

    if x < 129 and p==4: return False

    if x>=129: return False

    if p%2 == 0:

        return F(x+1,p+1) and F(x*2, p+1)

    else:

        return F(x+1,p+1) or F(x*2, p+1)

for s in range(1, 129):

        if F(s, 1):

            print(s)

я.п. C/C++:

#include <bits/stdc++.h>

using namespace std;

bool f(int x,int p)

{

    if(x>=129&&p==4)

        return true;

    if(x<129&&p==4)

        return false;

    if(x>=129)

        return false;

    if(p%2==0)

        return f(x+1,p+1)&&f(x*2,p+1);

     else

        return f(x+1,p+1)||f(x*2,p+1);

}

int main()

{

    for(int s=1;s<129;++s)

        if(f(s,1))

            cout<<s<<' ';

    return 0;

}

я.п. PascalABC.net:

function f(x,p: integer):boolean;

begin

  if (x>=129) and (p=4) then begin f:=true;exit end;

  if (x<129) and (p=4) then begin f:= false;exit end;

  if (x>=129) then begin f:= false;exit end;

  if p mod 2 = 0 then

    f:=f(x+1,p+1) and f(x*2,p+1)

  else

    f:=f(x+1,p+1) or f(x*2,p+1);

end;

begin

  for var s:=1 to 129 do

    if f(s,1) then

    begin

      print(s);

      end;

end.

Ответ: 32 63

Задания № 20 ЕГЭ прошлых лет

Решение.

Прежде, чем ответить на вопрос задачи, разберемся с ситуацией, когда Петя выигрывает первым ходом.

1. При S = [35 . . 68] Петя выигрывает первым ходом удваивая количество камней во второй куче. И суммарное количество камней будет >=77.

2. При S = 69 Петя выигрывает первым ходом добавляя один камень во вторую кучу. При этом суммарное количество камней становится равным 77.

Если во второй куче количество камней будет меньше 35 (даже на 1 камень), то Петя выиграть первым ходом не может. Посмотрим, сможет ли выиграть Ваня первым ходом. Допустим, камней во второй куче будет 34. Удваивая количество камней во второй куче Петя не может получить 77 камней (34*2 + 7 = 75). Следовательно, Петя должен сходить так, чтобы Ваня не смог выиграть первым ходом.

Итак, исходный вариант состояния куч: (7, 34). Петя делает ход, увеличивая количество камней в первой куче на 1 камень - (8, 34). В ответ Ваня может создать четыре варианта ситуаций: (16, 34), (9, 34), (8, 68) и (8, 35). В каждой из этих ситуаций суммарное количество камней составит: 50, 43, 76, 43. То есть, Ваня не может выиграть своим первым ходом. Максимальное количество камней, которое он может получить - 76. Петя своим вторым ходом, увеличивая вдвое количество камней в куче с большим количеством камней - выигрывает. Итак, первое число найдено: это 34.

Второе число найдем из следующего предположения: это должно быть такое значение камней во второй куче, когда Петя еще может выиграть своим вторым ходом. В этом случае к моменту хода Пети - второй ход, - количество камней в первой куче должен быть 14. Тогда, для выигрыша Пети перед его ходом, суммарное количество камней должно быть 76, вследствие чего, количество камней во второй куче должно быть: (76 - 14)/2 = 62 / 2 = 31.

Исходной состояние: (7, 31). Первый ход Пети: (14, 31) - удвоение количества камней в первой куче.

Ответный ход Вани (все его ходы): (15, 31), (28, 31), (14, 62), (14, 32). Суммарное количество камней в этих ситуациях составляет: 46, 59, 76, 46. То есть, Ваня выиграть первым ходом не может.

Второй ход Пети: удвоение количества камней в куче, содержащей большее количество камней. Итак, найдено второе число: 31.

Ответ: 31, 34.