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

Рассмотрим каждую пару $(x_i, y_i)$ как одно состояние. Выражение $\neg x_i \lor y_i$ ложно только в состоянии $(1, 0)$.

Выражение $\neg x_{i+1} \land y_{i+1}$ истинно только в состоянии $(0, 1)$. Импликация нарушается, когда её левая часть истинна, а правая ложна.

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

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

Сначала подсчитаем количество программ, переводящих число 2 в число 14. Обозначим это количество через $f(n)$. Для команды «Прибавить 1» используется переход из $n-1$, а для команды «Умножить на 2» — из $n/2$, если $n$ чётно.$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$

Последовательно получаем: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=2$, $f(6)=3$, $f(7)=3$, $f(8)=5$, $f(9)=5$, $f(10)=7$, $f(11)=7$, $f(12)=10$, $f(13)=10$, $f(14)=13$.

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

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

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

Условия перехода между соседними парами дают следующие возможности: $00 \to 00,10,01,11$; $10 \to 11$; $01 \to 01,11$; $11 \to 11$.

Так как все команды увеличивают число, траектория может содержать число 9 только один раз. Поэтому программу можно разделить на путь от 3 до 9 и путь от 9 до 14.

Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для $n$ от 4 до 9 учитываем последние команды: прибавление 1, прибавление 2 и умножение на 3.$$f(n)=f(n-1)+f(n-2)+[3\mid n]f(n/3)$$

Раскроем отрицание импликации.$$\neg(x \to w) = x \land \neg w$$

Так как во всех трёх строках $F=0$, дизъюнкция равна нулю. Следовательно, каждый её член должен быть равен нулю: $x \land \neg w=0$, $y \equiv z=0$ и $y=0$. Однако при $y=0$ условие $y \equiv z=0$ даёт $z=1$.

Чтобы дизъюнкция могла быть ложной, второе и третье высказывания должны быть ложными одновременно. Значит, $x \le 25$ и $y \le 25$.

В этой области максимальное значение выражения $y + 2x$ достигается при $x = 25$ и $y = 25$:$$y + 2x = 25 + 2 \cdot 25 = 75$$

Чтобы дизъюнкция была ложной, все три её части должны быть ложными. Значит, должны выполняться условия $x + 2y \geq A$, $y \leq x$ и $x \leq 60$.

При $y \leq x$ и $x \leq 60$ максимальное значение $x + 2y$ достигается при $x = 60$ и $y = 60$.$$x + 2y \leq 60 + 2 \cdot 60 = 180$$

Если $x \notin B$, то условие $x \in B$ ложно, поэтому импликация истинна. Рассмотрим только $x \in [50; 60]$.

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

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

Так как $x$ и $y$ — неотрицательные целые числа, при этих условиях максимальное значение выражения $x + 2y$ достигается при $x = 30$ и $y = 30$.$$x + 2y \leq 30 + 2 \cdot 30 = 90$$

Дизъюнкция будет ложной только тогда, когда одновременно ложно первое слагаемое и ложно второе слагаемое.

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

Введём динамику: количество способов получить число складывается из количества способов получить его из предыдущего числа командой 1 и из числа, вдвое меньшего, командой 2.

Так как траектория должна содержать число 15, разбиваем каждую программу на две части: путь от исходного числа 2 до числа 15 и путь от числа 15 до числа 45.

Во всех трёх строках значение функции равно нулю. Поэтому оба слагаемых дизъюнкции должны быть равны нулю: $\neg z = 0$, а значит, $z = 1$.$$F = 0 \Rightarrow z = 1$$

Для ложности импликации $(w \to y) \to (x \equiv y)$ необходимо, чтобы её посылка была истинной, а заключение ложным.$$w \to y = 1, \quad x \equiv y = 0$$

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

Для участка от 3 до 10 подсчётом по последней команде получаем последовательность количества путей: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$, $f(9)=17$, $f(10)=30$.$$N(3,10)=30$$

Выражение может быть ложным только тогда, когда ложны все три высказывания:$$x \cdot y \geq A,\quad x \geq y,\quad x < 8$$

Так как $x$ и $y$ — неотрицательные целые числа, из условий $x < 8$ и $x \geq y$ следует, что $x \leq 7$ и $y \leq 7$.

Введём $f(n)$ — количество программ, переводящих исходное число 101 в число $n$. Для исходного числа $f(101)=1$.

Переход по команде A возможен из числа $n-1$, поэтому он добавляет $f(n-1)$ способов.

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

Условие $\neg(x\equiv z)=1$ означает, что значения $x$ и $z$ в каждой строке различаются. Перебор оставшихся вариантов размещения переменных с учётом трёх строк таблицы оставляет единственный вариант: первый столбец — $x$, третий — $z$…$$x\ne z$$

Так как значение функции в каждой из трёх строк равно 1, каждый набор должен удовлетворять всем условиям произведения логических выражений.$$w=1,\quad x\ne z,\quad (x=0)\lor(y=0)$$

Во второй строке единицы стоят в третьем и четвёртом столбцах. Эти столбцы должны соответствовать $w$ и одной из переменных $x,z$. Сопоставление всех трёх строк с условием $x\ne z$ даёт третий столбец $w$, а второй и четвёртый — $x$ и $z$.

Обозначим пару значений на позиции $i$ как $(x_i,y_i)$. Если эта пара равна $(0,0)$, то левая часть импликации ложна, поэтому следующая пара может быть любой из четырёх.

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