РЕШУ ЕГЭ — информатика

Задания

Сколько существует различных наборов значений логических переменных x₁, x₂, ... x₉, y₁, y₂, ... y₉, которые удовлетворяют всем перечисленным ниже условиям:

$левая круглая скобка левая круглая скобка x_1\equiv y_1 правая круглая скобка arrow левая круглая скобка x_2 \equiv y_2 правая круглая скобка правая круглая скобка \wedge левая круглая скобка x_1 arrow x_2 правая круглая скобка \wedge левая круглая скобка y_1 arrow y_2 правая круглая скобка =1;$

$левая круглая скобка левая круглая скобка x_2\equiv y_2 правая круглая скобка arrow левая круглая скобка x_3 \equiv y_3 правая круглая скобка правая круглая скобка \wedge левая круглая скобка x_2 arrow x_3 правая круглая скобка \wedge левая круглая скобка y_2 arrow y_3 правая круглая скобка =1;$

$...$

$левая круглая скобка левая круглая скобка x_8\equiv y_8 правая круглая скобка arrow левая круглая скобка x_9 \equiv y_9 правая круглая скобка правая круглая скобка \wedge левая круглая скобка x_8 arrow x_9 правая круглая скобка \wedge левая круглая скобка y_8 arrow y_9 правая круглая скобка =1?$

Решение. Будем обозначать набор входных переменных уравнения кортежем из четырёх чисел $левая круглая скобка x_1, y_1, x_2, y_2 правая круглая скобка .$

Рассмотрим первое уравнение. Переберём все 16 наборов переменных, подойдут 7 из них:

$левая круглая скобка 0, 0, 0, 0 правая круглая скобка , левая круглая скобка 0, 0, 1, 1 правая круглая скобка , левая круглая скобка 0, 1, 0, 1 правая круглая скобка , левая круглая скобка 0, 1, 1, 1 правая круглая скобка , левая круглая скобка 1, 0, 1, 0 правая круглая скобка , левая круглая скобка 1, 0, 1, 1 правая круглая скобка , левая круглая скобка 1, 1, 1, 1 правая круглая скобка .$

Так как в следующем уравнении встречаются $x_2, y_2,$ посчитаем, какие пары $левая круглая скобка x_2,y_2 правая круглая скобка$ и сколько раз вошли в наборы, удовлетворяющие первому уравнению: (0, 0) - 1, (0, 1) - 1, (1, 0) - 1, (1, 1) - 4.

Будем подставлять эти $левая круглая скобка x_2, y_2 правая круглая скобка$ на место $x_3,y_3$ во второе уравнение. Так как оно эквивалентно первому уравнению, то можно просто брать $x_2,y_2$ и находить среди решений первого уравнения кортежи, который начинаются так же.

То есть (0, 0) даст решения (0, 0, 0, 0) и (0, 0, 1, 1). (0, 1) - (0, 1, 0, 1), (0, 1, 1, 1). (1, 0) - (1, 0, 1, 0), (1, 0, 1, 1). (1, 1) - (1, 1, 1, 1).

Посчитаем, сколько каких пар $x_3,y_3$ получилось среди всех решений системы из первых двух уравнений. Так как (1, 1) ставился на место 4 раза, он породил 4 кортежа с (1, 1) на конце. В общем получилось (0, 0) - 1, (0, 1) - 1, (1, 0) - 1, (1, 1) - 7.

Перейдя к следующему уравнению, получим (0, 0) - 1, (0, 1) - 1, (1, 0) - 1, (1, 1) - 10.

И так далее, с каждым уравнением количество решений будет увеличиваться на 3.

Изначально было 7 решений, плюс ещё 7 уравнений, каждое из которых добавляет по 3 решения.

Итого $7 плюс 7 умножить на 3 = 28.$

№ п/п	№ задания	Ответ
1	10299	28

Ключ