Информатика ЕГЭ — решения заданий ФИПИ с ответами

Импликация $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$.

Обозначим $z_i = x_i \land y_i$. Правая часть каждого равенства преобразуется по закону де Моргана:$$\lnot x_{i+1} \lor \lnot y_{i+1} \equiv \lnot(x_{i+1} \land y_{i+1}) = \lnot z_{i+1}$$

Следовательно, система требует, чтобы соседние значения $z_i$ и $z_{i+1}$ были противоположными. Поэтому возможны только два чередующихся набора значений: $0101010$ и $1010101$.

Обозначим через $f(n)$ число программ, переводящих число 1 в число $n$. В число $n$ можно попасть командами «прибавить 1» и «прибавить 2», а также командой умножения на 3, если $n$ делится на 3.$$f(n)=f(n-1)+f(n-2)+\begin{cases}f(n/3),& n\mathbin{\vdots}3\\0,& n\text{ не делится на }3\end{cases}$$

Последовательно вычисляя значения, получаем: $f(1)=1$, $f(2)=1$, $f(3)=3$, $f(4)=4$, $f(5)=7$, $f(6)=12$, $f(7)=19$, $f(8)=31$, $f(9)=53$.

Функция равна 0, поэтому каждое слагаемое дизъюнкции должно быть равно 0.$$(\neg x \land \neg y)=0,\quad (x\equiv z)=0,\quad w=0$$

Из условия $(x\equiv z)=0$ следует, что значения переменных $x$ и $z$ в каждой строке различаются. Условие $w=0$ позволяет найти столбец, содержащий нулевые значения во всех строках с учётом пропущенных ячеек.

Если $x \notin D$, внешняя импликация истинна автоматически. Рассмотрим значения $x \in D$.$$x \in D \Rightarrow \neg(x \in D) = 0$$

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

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

Множитель $\neg(x \equiv z)$ равен $1$ только тогда, когда значения $x$ и $z$ различаются.$$\neg(x \equiv z)=1 \Rightarrow x \ne z$$

Импликация $P \to Q$ ложна только тогда, когда $P=1$, а $Q=0$. Внутренняя импликация ложна при одновременном выполнении условий $\mathrm{ДЕЛ}(x,14)$ и $\mathrm{ДЕЛ}(x,4)$.$$\mathrm{ДЕЛ}(x,14) \land \mathrm{ДЕЛ}(x,4)$$

Число $x$ должно делиться на наименьшее общее кратное чисел $14$ и $4$.$$\operatorname{НОК}(14,4)=28$$

Импликация $P \to Q$ ложна только при истинном $P$ и ложном $Q$. Поэтому первая часть формулы ложна, если $x$ делится на $3$ и одновременно делится на $5$.$$\mathrm{ДЕЛ}(x,3) \land \mathrm{ДЕЛ}(x,5)$$

Значит, $x$ должно быть кратно $15$. Наименьшее натуральное проблемное значение — $x=15$.

Поскольку все команды увеличивают число, число 12 в траектории может встретиться только один раз. Поэтому число искомых программ равно произведению числа программ из 2 в 12 и числа программ из 12 в 21.$$N = N_{2\to12} \cdot N_{12\to21}$$

Для подсчёта используем динамическое программирование. Для каждой точки складываем количества способов попасть в неё командами «прибавить 2», «прибавить 3» и «умножить на 3», если соответствующий переход возможен.$$f(x)=f(x-2)+f(x-3)+\begin{cases}f(x/3),&x\mathrel{\vdots}3\\0,&\text{иначе}\end{cases}$$

Проверим соответствие столбцов порядку $x$, $w$, $z$, $y$. В первой строке имеем $x=0$, $w=1$, $z=1$, $y=1$.$$(\neg 0 \land \neg 1) \lor (0 \equiv 1) \lor \neg 1 = 0$$

Во второй строке при таком порядке получаем $x=1$, $w=1$, $z=0$, $y=0$.$$(\neg 1 \land \neg 0) \lor (1 \equiv 0) \lor \neg 1 = 0$$