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

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

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

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

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

Рассмотрим все допустимые переходы из исходного состояния 100. Команда A увеличивает текущее число на 1, а команда B выполняет перестановку двух последних цифр только при условии, что цифра десятков меньше цифры единиц.

Последовательно перебираем достижимые числа и для каждого числа сохраняем количество программ, которыми оно получено. При переходе по команде A значение увеличивается на 1; при допустимом переходе по команде B добавляется способ перейти к…

Так как во всех трёх строках $F = 0$, обе части дизъюнкции должны быть равны нулю.$$((y \to x) \to z) = 0,\quad \neg w = 0$$

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

Чтобы функция была ложной, первое слагаемое $\neg x$ должно быть ложным, а значит, $x=1$. Поэтому столбец, состоящий из единиц, — это столбец переменной $x$.

Второе слагаемое $y$ также должно быть ложным, следовательно, $y=0$. Поэтому столбец, состоящий из нулей, — это столбец переменной $y$.

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

Для любого числа n переход по команде A приходит из числа n-1. Дополнительный переход по команде B возможен, если перестановка двух последних цифр числа-источника разрешена.

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

Последовательно вычисляем количество способов от 3 до 9: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$, $f(9)=17$.$$f(9)=f(8)+f(7)=11+6=17$$

Посчитаем количество программ, переводящих 4 в каждое число до 11. Для числа $n$ последняя команда может быть прибавлением 1, прибавлением 2 или умножением на 2.$$f(n)=f(n-1)+f(n-2)+f(n/2)\text{ при чётном }n$$

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

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

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

Импликация $\mathrm{ДЕЛ}(x,2) \to \neg\mathrm{ДЕЛ}(x,3)$ ложна только тогда, когда $x$ делится на $2$ и одновременно делится на $3$.

Следовательно, первая часть формулы впервые становится ложной при наименьшем натуральном $x = 6$.

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

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

Рассмотрим первую строку. В ней значения столбцов имеют вид $0,\,\_,\,0,\,1$, а значение функции равно 0. Единственное соответствующее распределение даёт первый столбец $z$, второй $y$, третий $x$, четвёртый $w$.

Проверим полученное соответствие по второй строке: значения переменных равны $z=1$, $y=0$, $x=0$, $w=1$. Тогда $(\neg x \land \neg y) \lor (y \equiv z) \lor \neg w = (1 \land 1) \lor 0 \lor 0 = 1$, поэтому для нулевого результата вторая и…

Если $x_i \land y_j=1$, то обе импликации должны быть истинными, поэтому $x_{i+1}=1$ и $y_{j+1}=1$.

Рассмотрим случай, когда среди $x_1,\ldots,x_9$ нет единиц. Тогда первые девять значений $x$ равны нулю, а $x_{10}$ выбирается двумя способами. Последовательность $y$ произвольна: $2\cdot 2^5=64$ наборов.

Рассматриваем все перестановки переменных $w$, $x$, $y$, $z$ по четырём столбцам и проверяем каждую перестановку по трём строкам таблицы.$$F=(y\land\neg x)\lor(x\equiv z)\lor\neg w$$

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

Функция $F$ ложна, если одновременно $x \to y = 0$ и $\neg(w \to z) = 0$.

Импликация $x \to y$ ложна только при $x = 1$ и $y = 0$. Поэтому столбец с постоянными единицами — это $x$, а столбец с постоянными нулями — $y$.

Если $x \notin D$, внешняя импликация истинна автоматически. Поэтому достаточно рассмотреть $x \in D$.$$x \in D \Rightarrow \neg(x \in C) \land \neg(x \in A) \text{ должно быть ложно}$$

Следовательно, для каждой точки отрезка $D$ должно выполняться $x \in C$ или $x \in A$, то есть $D \subseteq C \cup A$.

Обозначим пару $(x_i,y_i)$ состоянием. Всего возможны четыре состояния: $(0,0)$ и три ненулевых состояния.

Если текущая пара ненулевая, то $x_i \lor y_i=1$. Правая часть следующего равенства должна быть равна 1, поэтому следующая пара единственным образом равна $(0,0)$.

Рассмотрим третью строку: значения в четырёх неизвестных столбцах равны $1,0,1,1$, а значение функции равно 0.

Чтобы выражение $F=(\neg x\land\neg y)\lor(x\equiv z)\lor\neg w$ было равно нулю, необходимо, чтобы $w=1$, $x=1$, $y=1$, $z=0$.

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

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

Введём обозначения $a_i = x_i \lor y_i$. Каждое условие имеет вид $a_i \to a_{i+1} = 1$ и запрещает только случай $a_i = 1$, $a_{i+1} = 0$.$$a_i \leq a_{i+1}$$

Следовательно, допустимая последовательность $a_1, \ldots, a_6$ имеет вид: сначала нули, затем единицы. Возможны $0, 1, \ldots, 6$ единиц.