Тапсырма 23 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

Если среди $y_1,\ldots,y_7$ есть хотя бы одна единица, то при наличии единицы среди $x_1,\ldots,x_5$ все значения $x$ от первой такой единицы до $x_6$ должны быть равны единице. Если же среди $x_1,\ldots,x_5$ есть единица, то аналогичное…

Случай 1: в обеих группах есть единицы — среди $x_1,\ldots,x_5$ и среди $y_1,\ldots,y_7$. Последовательность $x$ имеет 5 вариантов расположения первой единицы, а последовательность $y$ — 7 вариантов. Получаем $5\cdot7=35$ наборов.

Представим каждую пару $(x_i,y_j)$ как клетку таблицы. При $x_i \land y_j = 1$ первое условие требует выполнения $x_i \land y_{j+1}$, а второе — $x_{i+1} \land y_j$.

Таким образом, при переборе наборов значений нужно исключать все конфигурации, в которых из клетки $(i,j)$ со значением $1$ можно перейти вправо или вниз в клетку со значением $0$.

Чтобы исходное выражение было ложным, все три высказывания должны быть ложными. Второе и третье высказывания ложны при $x \leq 15$ и $y \leq 30$.$$x \leq 15,\quad y \leq 30$$

При этих ограничениях максимальное значение выражения $y + 2x$ достигается при $x = 15$ и $y = 30$.$$y + 2x = 30 + 2 \cdot 15 = 60$$

Импликация $a \to b$ истинна, если $a = 0$ или $b = 1$. Поэтому из условий для каждого $i \geq 2$ следует: если $x_i = 1$, то $x_{i-1} = 1$ и $y_i = 1$; если $y_i = 1$, то $y_{i-1} = 1$.

Следовательно, единицы в каждой последовательности идут только в начале. Последовательность $x$ определяется числом $a$ единиц, а последовательность $y$ — числом $b$ единиц, где $a,b \in \{0,1,\ldots,6\}$.

Так как во всех приведённых строках $F = 1$, конъюнкция $\neg w$ должна быть истинной. Значит, $w = 0$ во всех строках. Единственный столбец, в котором в известных ячейках стоят только нули, — первый.$$w = 0$$

Условие $\neg(y \equiv z)$ означает, что значения $y$ и $z$ различны в каждой строке.

Раскроем импликации: $y \to w = \neg y \lor w$, $x \to z = \neg x \lor z$.$$F = \neg(y \to w) \lor (x \to z) \lor \neg x = (y \land \neg w) \lor \neg x \lor z$$

Чтобы значение функции было равно нулю, должны выполняться условия $x = 1$, $z = 0$, а также $y \land \neg w = 0$.

Для каждого $i=1,\ldots,5$ первое условие означает: если $x_i=1$, то $x_{i+1}=1$ и $y_i=1$. Поэтому после появления первой единицы среди $x_i$ все последующие $x_i$ также равны единице.

Если все $x_i=0$, то все переменные $y_i$ могут принимать произвольные значения. Получаем $2^6=64$ набора.

Во всех трёх строках значение функции равно $0$. Поэтому дизъюнкция равна нулю, а значит, каждое её слагаемое равно нулю. В частности, $w=0$.$$w=0$$

Четвёртый столбец содержит значение $0$ в первой строке, где первые два значения равны $1$. Если бы четвёртый столбец не был столбцом $w$, условие $w=0$ не выполнялось бы для всех строк. Следовательно, четвёртый столбец — это $w$.

Введём динамическое подсчитывание количества программ, ведущих из одного числа в другое. Для попадания в число $x$ последняя команда могла быть одной из трёх: прибавление 2, умножение на 2 или прибавление 3.

Отдельно подсчитываем программы перехода от исходного числа 2 к числу 10 и программы перехода от числа 10 к числу 21. По рекуррентному подсчёту получаем по 9 программ для каждого участка.

Импликация $A \to B$ равна $1$, если $A=0$ или $B=1$. Поэтому если $(x_i,y_i)=(0,0)$, ограничений на следующую пару нет.

Если $(x_i,y_i)\ne(0,0)$, то $x_i\lor y_i=1$. Тогда необходимо, чтобы $x_{i+1}\land y_{i+1}=1$, то есть следующая пара должна быть $(1,1)$. После этого все последующие пары также обязаны быть $(1,1)$.

Запишем числа 52 и 36 в двоичной системе:$$52 = 110100_2, \quad 36 = 100100_2$$

Условие $x \mathbin{\&} 36 = 0$ запрещает единицы в разрядах $2^2$ и $2^5$ числа $x$. Поэтому из условия $x \mathbin{\&} 52 \ne 0$ может выполняться только единичность разряда $2^4$.$$52 = 2^5 + 2^4 + 2^2, \quad 36 = 2^5 + 2^2$$

Значение функции равно $0$, поэтому каждое из трёх выражений в дизъюнкции должно быть равно $0$: $x \land \neg y = 0$, $x \equiv z = 0$, $\neg w = 0$.

Из условия $\neg w = 0$ следует $w=1$. В первой строке значения столбцов равны $0,1,1,0$, а в третьей — неизвестное значение, $1,0,1$. Проверка всех перестановок переменных показывает, что нулевое значение функции во всех трёх различных…

Рассмотрим функцию $F = (\neg x \lor \neg y) \land \neg(y \equiv z) \land w$. Так как во всех трёх строках значение функции равно 1, в каждой строке должно быть $w=1$.

В первой строке заполненные значения имеют вид $\_,0,0,1$. Следовательно, столбец переменной $w$ должен содержать 1 в этой строке. Аналогично проверяются значения в двух остальных строках.

Чтобы траектория содержала число 10, программа состоит из пути от 30 до 10 и пути от 10 до 1. Эти части можно комбинировать независимо.

Обозначим через $f(n)$ число способов попасть из $n$ в 10. Используем рекуррентное соотношение $f(n)=f(n-1)+f(\lfloor n/2 \rfloor)$ и получаем $f(30)=12$.

Если $x \notin P$, внешняя импликация истинна автоматически. Поэтому достаточно рассмотреть $x \in P$.

При $x \in P$ высказывание $\neg(x \in P)$ ложно. Чтобы внутренняя импликация оставалась истинной, её левая часть должна быть ложной: $(x \in Q) \land \neg(x \in A) = 0$.$$(x \in P) \cap (x \in Q) \subseteq (x \in A)$$

Преобразуем отрицание импликации:$$\neg(y \to x) = y \land \neg x$$

Тогда функция имеет вид:$$F = (y \land \neg x) \lor (\neg z \lor w) \lor \neg z$$

Во всех трёх строках значение функции равно нулю. Поэтому каждое слагаемое выражения должно быть равно нулю, в частности $\neg w=0$. Значит, $w=1$ во всех строках, и переменной $w$ соответствует первый столбец.

Во второй строке значения во втором и четвёртом столбцах равны нулю, а в третьем столбце значение не указано. В третьей строке во втором столбце стоит 0, а в третьем — 1. Чтобы $y \equiv z=0$, переменные $y$ и $z$ должны занимать второй и…

Дизъюнкция истинна автоматически, если истинна первая часть. Первая часть является импликацией, которая ложна только в случае, когда её условие истинно, а заключение ложно.$$\mathrm{ДЕЛ}(x,2)=1 \quad\text{и}\quad \neg\mathrm{ДЕЛ}(x,5)=0$$

Следовательно, импликация ложна для чисел, делящихся одновременно на $2$ и на $5$, то есть для положительных чисел, кратных $10$.$$x=10k,\quad k\in\mathbb{N}$$

Во всех трёх строках значение функции равно 1. Поэтому каждый множитель конъюнкции также должен быть равен 1.

Из условия $\neg w=1$ следует, что $w=0$. Столбец 4 содержит нули в двух заполненных строках, поэтому это столбец переменной $w$.

Подставим значения $C=8$ и $B=18$ в логическое выражение:$$\neg(A=18) \land ((18<A) \to (16>A)) \land ((A<18) \to (A>16))$$

Если $A>18$, то условие $18<A$ истинно, поэтому импликация требует $16>A$. Это невозможно, поскольку $A>18$.