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

Обозначим через $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$.

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

При условиях $x \geq 30$ и $y \geq x$ минимальные неотрицательные значения переменных равны $x = 30$ и $y = 30$.

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

При ограничениях $x \leq A$ и $y \leq A$ наибольшее возможное значение суммы $x+2y$ достигается при $x=A$ и $y=A$:$$x+2y \leq A+2A=3A$$

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

Из условия $\neg x=0$ следует $x=1$. Поэтому столбец со значениями $1,1,1$ — это переменная $x$.

Чтобы выражение не было тождественно истинным, необходимо найти условия, при которых все три высказывания ложны.$$(3x + 2y \leq A) \land (y \geq x) \land (x \geq 10)$$

Из условий $x \geq 10$ и $y \geq x$ следует, что минимальные возможные значения переменных: $x = 10$, $y = 10$.

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

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

Обозначим через $f(n)$ число программ, переводящих число $n$ в число 1. Для числа 1 программа может быть пустой, поэтому $f(1)=1$.$$f(1)=1$$

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

При значении функции, равном 1, каждый множитель конъюнкции должен быть равен 1. Поэтому $w=1$, $x \ne z$ и $x \lor \neg y=1$.$$(x \lor \neg y) \land \neg(x \equiv z) \land w = 1$$

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

Чтобы функция была равна нулю, каждый член дизъюнкции должен быть равен нулю:$$F=0 \Rightarrow \neg(z\to w)=0,\quad x\to y=0,\quad \neg x=0$$

Из условия $\neg x=0$ получаем $x=1$. Импликация $x\to y$ при $x=1$ равна нулю только при $y=0$.$$x=1,\quad y=0$$

Условие $x_i \lor \neg x_{i+1}=1$ означает, что при $x_{i+1}=1$ обязательно $x_i=1$. Поэтому последовательность $x_1, x_2, \ldots, x_6$ не возрастает. Аналогично последовательность $y_1, y_2, \ldots, y_6$ не возрастает.$$x_i \geq x_{i+1},\quad y_i \geq y_{i+1}$$

Условия $x_i \lor \neg y_i=1$ и $x_6 \lor \neg y_6=1$ означают, что в каждой позиции значение $y_i=1$ возможно только при $x_i=1$.$$x_i \geq y_i\quad (i=1,\ldots,6)$$

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

Для первых двух строк первые два столбца имеют значения $0,0$ и $0,1$, а четвёртый — значение 1. При $y=0$ условие $\neg(y \equiv z)=1$ требует $z=1$. Значит, первый столбец — $y$, а четвёртый — $z$.

Так как функция принимает значение 1, множитель $\lnot w$ также равен 1. Следовательно, $w = 0$.

Множитель $\lnot(y \equiv z)$ равен 1 только тогда, когда значения $y$ и $z$ различны.