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

Чтобы функция $\neg(y \to (x \equiv w)) \land (z \to x)$ была равна 1, оба множителя должны быть равны 1. Условие $\neg(y \to (x \equiv w))=1$ означает $y=1$ и $x \ne w$.

Рассмотрим третью строку фрагмента: значения во втором, третьем и четвёртом столбцах равны $0$, $1$, $0$. Так как $y=1$, третий столбец соответствует $y$. При этом второй столбец со значением $0$ должен соответствовать $x$, а первый…

Преобразуем отрицание импликации и импликацию $y \to w$: $\neg(x \to z) = x \mathbin{\land} \neg z$, $y \to w = \neg y \mathbin{\lor} w$.$$\ F = (x \mathbin{\land} \neg z) \mathbin{\lor} \neg y \mathbin{\lor} w$$

Чтобы значение функции было равно нулю, необходимо, чтобы все три дизъюнкта были ложны. Поэтому $y = 1$, $w = 0$, а $x \mathbin{\land} \neg z = 0$, то есть $x = 0$ или $z = 1$.

Во всех указанных строках значение функции равно нулю. Обозначим $A = (w \to z) \to x$. Тогда $A \lor \lnot y = 0$ возможно только при $A = 0$ и $y = 1$.$$y = 1$$

Импликация $(w \to z) \to x$ равна нулю только тогда, когда её левая часть равна единице, а $x = 0$. Следовательно, в каждой из строк $x = 0$.$$w \to z = 1,\quad x = 0$$

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

Переменная $w$ должна иметь значение 0 во всех трёх строках. Только второй столбец содержит известные нули во всех строках, значит, второй столбец соответствует $w$.$$w=0$$

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

Условие $\neg(y\equiv z)=1$ означает, что значения $y$ и $z$ различаются. В первой строке после учёта $w=1$ имеем $x=0$, $y=0$, поэтому $z=0$. Во второй строке $z=1$, $y=0$, а в третьей строке $z=0$, $y=1$.$$\neg(y\equiv z)=1\iff y\ne z$$

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

Из $\neg(y \equiv z)=1$ следует, что значения $y$ и $z$ различаются.

Так как обе команды уменьшают число, траектория может содержать число 12 только один раз. Поэтому любую подходящую программу можно однозначно разделить на путь от 30 до 12 и путь от 12 до 1.

Обозначим через $f(n)$ количество способов получить число 12 из числа $n$. Для $n > 12$ имеем $f(n)=f(n-2)+f(\lfloor n/2\rfloor)$, поскольку последней выполненной командой может быть A или B. Последовательное вычисление даёт $f(30)=3$.$$f(30)=f(28)+f(15)=3$$

Так как все команды увеличивают число, сначала траектория проходит через 8, затем через 10.$$N = N_{2\to 8} \cdot N_{8\to 10} \cdot N_{10\to 12}$$

Обозначим через $f(n)$ количество программ, переводящих 2 в $n$. Для чисел от 2 до 8 получаем: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=3$, $f(6)=6$, $f(7)=9$, $f(8)=15$.$$f(n)=f(n-1)+f(n-2)+f(n/3)\text{, если }3\mid n$$

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

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

Функция равна 1 во всех трёх строках. Поэтому множитель $w$ должен быть равен 1 во всех строках. Единственный подходящий столбец — второй.

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

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

Импликация ложна только тогда, когда её первый аргумент равен $1$, а второй — $0$. Следовательно, $w = 1$ и $\neg(z \to x) = 0$, то есть $z \to x = 1$.$$w \to \neg(z \to x) = 0 \Rightarrow w = 1,\ z \to x = 1$$

Так как во всех трёх строках $F = 1$, каждый множитель функции должен быть равен 1. В частности, $w = 1$ во всех строках.

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

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

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

Обозначим состояние на шаге $i$ парой $(x_i,y_i)$. Возможны состояния $00$, $01$, $10$, $11$.

Из условия $\bigl(x_i \to (x_{i+1} \land y_i)\bigr) \land (y_i \to y_{i+1})=1$ получаем переходы между состояниями: $00\to00,01,10,11$; $01\to01,11$; $10\to11$; $11\to11$.

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

Первый столбец содержит 1 в обеих заполненных строках и не противоречит третьей строке, поэтому ему соответствует переменная $w$.

Так как обе команды уменьшают число, траектория может содержать число 13 не более одного раза. Поэтому программы можно однозначно разделить на часть от 30 до 13 и часть от 13 до 1.

Подсчитаем количество способов попасть из 30 в 13. Возможны последовательные вычитания, а также переходы делением на 2 из чисел 30, 29, 28, 27 и 26. Динамическим подсчётом получаем 6 способов.$$N_{30\to13}=6$$

Раскроем импликации в логическом выражении.$$F = (x \land \neg y) \vee (\neg z \vee w) \vee \neg z$$

Проверим возможные соответствия переменных столбцам. Для каждой строки из фрагмента значение функции должно быть равно нулю, поэтому все указанные значения в строке должны согласовываться с выражением функции.

Внешняя импликация может быть ложной только при $x \in P$. Поэтому для всех $x \in P$ внутренняя импликация должна быть истинной.

Если одновременно $x \in P$ и $x \in Q$, то высказывание $\neg(x \in P)$ ложно. Чтобы внутренняя импликация оставалась истинной, должно выполняться $x \in A$.

Так как все команды увеличивают число, числа 10 и 12 в траектории встречаются именно в указанном порядке. Поэтому искомое количество программ является произведением числа способов пройти три участка.$$N(4,14;10,12)=N(4,10)\cdot N(10,12)\cdot N(12,14)$$

Посчитаем количество способов попасть из 4 в 10. Для каждого числа учитываются переходы из чисел на 1 и 2 меньше, а также из числа вдвое меньшего, если оно целое.$$N(4,10)=16$$

Обозначим через $f(n)$ число программ, переводящих число $n$ в число 1. Для каждого $n > 1$ последняя команда является либо вычитанием 1, либо делением на 2.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor),\quad f(1)=1$$

Последовательно вычисляя значения, получаем число программ от 9 до 1:$$f(2)=2,\ f(3)=3,\ f(4)=5,\ f(5)=7,\ f(6)=10,\ f(7)=13,\ f(8)=18,\ f(9)=23$$