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

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

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

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

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

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

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

Если найдено несколько значений S, в ответе запишите минимальное из них.

я.п. Python:

def F(x,p):

    if x >= 129 and (p==5 or p==3): return True

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

    if x>=129: return False

    if p%2 == 1:

        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)

def FF(x,p):

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

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

    if x >= 129: return False

    if p%2==1:

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

    else:

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

for s in range(1, 129):

        if F(s, 1):

            print(s)

print()

for s in range(1,129):

    if FF(s,1):

        print(s)

я.п. C/C++:

#include <bits/stdc++.h>

using namespace std;

bool f(int x,int p)

{

    if(x>=129&&(p==3||p==5))

        return true;

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

        return false;

    if(x>=129)

        return false;

    if(p%2==1)

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

     else

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

}

bool ff(int x,int p)

{

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

        return true;

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

        return false;

    if(x>=129)

        return false;

    if(p%2==1)

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

     else

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

}

int main()

{

    int s;

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

        if(f(s,1))

            cout<<s<<' ';

    cout<<'\n';

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

        if(ff(s,1))

            cout<<s<<' ';

    return 0;

}

я.п. PascalABC.net:

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

begin

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

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

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

  if p mod 2 = 1 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;

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

begin

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

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

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

  if p mod 2 = 1 then

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

  else

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

end;

begin

  for var s:=1 to 129 do

    if f(s,1) then

          println(s);

 println();

  for var s:=1 to 129 do

    if f1(s,1) then

      println(s);    

end.

Ответ: 62

Решения задания № 21 ЕГЭ прошлых лет

Решение.

В предыдущем разборе мы определились с минимальным число камней во второй куче, когда еще возможен выигрыш Пети первым ходом. Следовательно, для выигрыша Вани первым или вторым ходом рассмотрим ситуацию, когда во второй куче будет 30 камней. Решение можно представить как в таблице, так и деревом. Покажем решение данной задачи через построение дерева.

Так как мы показываем выигрышную стратегию Вани, следовательно, при построении дерева будем отображать все ходы Пети и только выигрышные ходы Вани. Наше построение - это только обоснование найденного решения. Советую всегда проверять найденные решения.

Ситуация: (14, 30) - первый ход Пети, на дереве не отражена. Дополните дерево самостоятельным достроением. Вписывается ли данная ситуация в описанную? Ведь, как видно из дерева, у Пети есть только максимальное количество камней - 70, которых не хватит, чтобы победить.

Построенное дерево неполно. Не обозначены действия. Но и так видно, что в данном случае выигрывает Ваня.

Ответ на задачу: 30