Задание 23 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

Импликация $\mathrm{ДЕЛ}(x,36)\to\neg\mathrm{ДЕЛ}(x,54)$ ложна, когда число $x$ делится и на $36$, и на $54$.$$36\mid x\ \text{и}\ 54\mid x$$

Такие числа являются кратными наименьшему общему кратному чисел $36$ и $54$.$$\operatorname{НОК}(36,54)=108$$

Дизъюнкция ложна только тогда, когда все её части ложны. Поэтому из $\neg x=0$ и $y=0$ получаем $x=1$ и $y=0$.$$\neg x = 0,\quad y = 0$$

В первых двух столбцах во всех строках стоят соответственно $1$ и $0$. Следовательно, первый столбец — это $x$, а второй — $y$.

Дизъюнкция может быть ложной только тогда, когда оба её выражения ложны. Для $x\notin B$ импликация истинна, поэтому рассмотрим только $x\in B$.

Импликация $(x\in B)\to\neg\mathrm{ДЕЛ}(x,21)$ ложна, если $x\in B$ и $\mathrm{ДЕЛ}(x,21)$ истинно.

От числа 1 до числа 21 нужно увеличить значение на 20.$$21 - 1 = 20$$

Пусть $a$ — количество команд «прибавить 2», а $b$ — количество команд «прибавить 5». Тогда$$2a + 5b = 20$$

Дизъюнкция ложна, если ложны все её части одновременно.$$x + 2y \leq A,\quad y \geq x,\quad x \geq 33$$

При условиях $x \geq 33$ и $y \geq x$ минимальное значение выражения $x + 2y$ достигается при $x = 33$ и $y = 33$.$$x + 2y \geq 33 + 2 \cdot 33 = 99$$

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

Из множителя $\neg(x \equiv z)=1$ следует, что значения $x$ и $z$ различаются в каждой строке.

У каждой из 12 логических переменных два возможных значения, поэтому всего существует $2^{12}$ наборов.

Для каждого набора вычисляем значения выражений $x_i \to y_i$, $x_i \equiv y_i$ и проверяем пять условий для соседних пар, а также заключительное условие $x_6 \to y_6 = 1$.

Из условия $\neg(A=B)$ получаем $B \ne 45$.

Если $B<45$, то высказывание $A>B$ истинно, поэтому из импликации $(A>B) \to (B>C)$ следует $B>C$, то есть $B>43$.

Логическое выражение ложно только тогда, когда ложны все три части дизъюнкции.$$(39 \ne y+2x)=0,\quad (A<x)=0,\quad (A<y)=0$$

Следовательно, для потенциального опровержения должны выполняться условия:$$y+2x=39,\quad x\leq A,\quad y\leq A$$

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

Единственный столбец, в котором уже стоят нули в первой и третьей строках, — второй. Следовательно, второй столбец соответствует переменной $w$.

Функция равна нулю, поэтому все части дизъюнкции должны быть равны нулю. Из слагаемого $y$ получаем $y=0$.$$y=0$$

Тогда условие $y \equiv w=0$ возможно только при $w=1$.$$y \ne w$$

Так как функция принимает значение $0$, каждое выражение в её дизъюнкции должно быть равно нулю. Поэтому $w=0$, $y \ne z$, а $x \land \neg y=0$.$$w=0,\quad y\ne z,\quad x\land\neg y=0$$

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

Рассмотрим сначала программы, переводящие число 38 в число 16. Обозначим через $f(n)$ количество способов попасть из $n$ в 16. Для каждого числа учитываем переходы $n \to n-2$ и $n \to \lfloor n/2 \rfloor$.$$f(n)=f(n-2)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$$

Последовательное вычисление значений от 16 до 38 даёт: $f(18)=1$, $f(20)=1$, $f(22)=1$, $f(24)=1$, $f(26)=1$, $f(28)=1$, $f(30)=1$, $f(32)=2$, $f(34)=2$, $f(36)=3$, $f(38)=3$. Значит, из 38 в 16 можно попасть 3 способами.

Из условия $x_i \lor y_i=1$ каждая пара $(x_i,y_i)$ может быть одной из трёх: $(0,1)$, $(1,0)$ или $(1,1)$.

Для пар $(0,1)$ и $(1,0)$ значение $x_i \equiv y_i$ равно 0, а для пары $(1,1)$ — 1.

Функция равна нулю только тогда, когда каждое из трёх слагаемых дизъюнкции равно нулю.$$F = 0 \Rightarrow \neg x = 0,\ y = 0,\ \neg z \land w = 0$$

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

Чтобы исходная дизъюнкция была ложной, все три её части должны быть ложными одновременно.$$(2x+y\ne70)=0,\quad (x<y)=0,\quad (A<x)=0$$

Это равносильно системе условий:$$2x+y=70,\quad x\ge y,\quad A\ge x$$

Дизъюнкция будет истинной автоматически, если импликация истинна. Импликация $(x \in B) \to \neg\mathrm{ДЕЛ}(x, 16)$ ложна только тогда, когда $x$ принадлежит отрезку $B$ и делится на $16$.$$(x \in B) \land \mathrm{ДЕЛ}(x,16)$$

Среди натуральных чисел от $50$ до $70$ только $64$ делится на $16: $64 = 16 \cdot 4$.$$x = 64$$

Внутренняя импликация $\mathrm{ДЕЛ}(x,12)\to\neg\mathrm{ДЕЛ}(x,14)$ нарушается, когда число $x$ делится одновременно на $12$ и на $14$.

Найдём наименьшее общее кратное чисел $12$ и $14$:$$\mathrm{НОК}(12,14)=2\cdot 6\cdot 7=84$$

Проверяем возможные перестановки переменных по четырём столбцам. Для каждой перестановки подставляем значения из трёх строк в выражение.$$(x \land \neg y) \lor (y \equiv z) \lor \neg w = 0$$

Условие выполняется одновременно для всех трёх строк только при соответствии: столбец 1 — $x$, столбец 2 — $w$, столбец 3 — $z$, столбец 4 — $y$.

Так как обе команды уменьшают число, любую подходящую программу можно разделить в момент появления числа 14 на две независимые части: путь от 30 до 14 и путь от 14 до 1.$$N(30 \to 1\text{ через }14)=N(30 \to 14)\cdot N(14 \to 1)$$

Для каждого числа последовательно подсчитываем количество способов попасть из него в нужное целевое число. При этом учитываются переходы $n \to n-2$ и $n \to \lfloor n/2 \rfloor$.