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

Во всех трёх строках значение функции равно 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$.

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

Последовательно получаем значения до числа 8: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$. Значит, существует 11 способов попасть из 3 в 8.

Импликация ложна только тогда, когда её левая часть истинна, а правая часть ложна.$$K \lor M = 1,\quad M \lor \lnot L \lor N = 0$$

Правая дизъюнкция равна нулю только в том случае, если все её переменные-условия равны нулю: $M=0$, $\lnot L=0$, $N=0$.$$M=0,\quad L=1,\quad N=0$$

Для подсчёта числа программ введём $f(n)$ — количество способов получить число $n$ из числа 2. Переходы к числу $n$ могут выполняться командами A, B и C.$$f(n)=f(n-1)+f(n-3)+\begin{cases}f(n/3),& n\ \text{кратно}\ 3,\\0,&\text{иначе}\end{cases}$$

При подсчёте значений до 16 исключаем число 12: количество путей, проходящих через 12, принимаем равным нулю. Получаем последовательность значений от 2 до 16: $1, 1, 1, 2, 4, 5, 7, 12, 17, 24, 0, 17, 41, 43, 60$.$$f(16)=60$$

Проверяем порядок столбцов $w$, $z$, $y$, $x$.

Во второй строке значения переменных равны $w=1$, $z=1$, $y=1$, $x=0$. Значение функции:$$(0 \land \neg 1) \lor (0 \equiv 1) \lor \neg 1 = 0$$

Так как значение функции во всех трёх строках равно 0, каждое слагаемое дизъюнкции должно быть равно 0. В частности, значение переменной $w$ в каждой строке, где оно известно, должно быть равно 0.

Во второй строке единицы стоят в первом и третьем столбцах. Если им соответствуют $x$ и $y$, а второй и четвёртый столбцы — $w$ и $z$, то получаем набор $x=1$, $w=0$, $y=1$, $z=1$, при котором функция равна 0.

Обозначим пару $(x_i,y_i)$ одним из четырёх состояний: $00$, $01$, $10$, $11$.

Для состояния $00$ импликации истинны независимо от следующей пары, поэтому возможны все четыре перехода. Из состояния $01$ возможны переходы в $01$ и $11$. Из состояния $10$ возможен только переход в $11$. Из состояния $11$ также…

Так как все команды увеличивают число, сначала в траектории встречается 9, затем 11. Поэтому программу можно разделить на три независимых участка.$$N=N_{3\to9}\cdot N_{9\to11}\cdot N_{11\to13}$$

Пусть $f(n)$ — число программ, переводящих число 3 в число $n$. Последней командой могут быть прибавление 1, прибавление 2 или умножение на 3.$$f(n)=f(n-1)+f(n-2)+f(n/3)$$

Во всех трёх строках значение функции равно 0. Дизъюнкция равна 0 только тогда, когда все её части равны 0.$$(x \land y)=0,\quad (y \equiv z)=0,\quad w=0$$

Условие $(y \equiv z)=0$ означает, что значения $y$ и $z$ различны.

Логическое выражение ложно только тогда, когда ложны все три дизъюнкта.$$y + 2x = 99,\quad A \ge x,\quad A \ge y$$

Чтобы найти наибольшее возможное значение $A$, рассмотрим минимально возможное максимальное значение чисел $x$ и $y$ при условии $y+2x=99$. Равенство $x=y$ даёт $3x=99$, поэтому $x=y=33$.