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

Если $x \notin B$, то внешняя импликация должна быть истинной. Поэтому внутренняя импликация также должна быть истинной.$$\bigl((x \in C) \land \neg(x \in A)\bigr) \to (x \in B)$$

При $x \notin B$ заключение внутренней импликации ложно. Значит, её условие не должно выполняться: все точки множества $C$, не принадлежащие $B$, должны принадлежать $A$.$$C \setminus B = [140;199] \setminus [133;175] = (175;199]$$

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

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

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

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

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

Проверка возможных соответствий четырёх столбцов переменным показывает, что единственный вариант, согласующийся со всеми тремя строками таблицы, имеет вид: столбцы $y$, $x$, $w$, $z$.

Обозначим значения в столбцах строк через $a$, $b$, $c$, $d$. Во всех трёх строках значение функции равно 0.$$F=(x \land \neg y) \lor (x \equiv z) \lor \neg w=0$$

В первой строке значения столбцов равны $0,1,1,0$. При соответствии первый столбец — $x$, второй — $w$, третий — $z$, четвёртый — $y$ получаем $x=0$, $w=1$, $z=1$, $y=0$, поэтому $F=0$.

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

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

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

В третьей строке первый столбец содержит 1, а второй — 0. Так как $w=1$, первый столбец соответствует $w$.

Обозначим через $f(n)$ количество программ, переводящих число 4 в число $n$. Для последнего шага в число $n$ могли использоваться команды A, B или C, поэтому учитываются переходы из $n-1$, $n-2$ и, если $n$ чётно, из $n/2$.

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

Так как все команды уменьшают число, каждую программу можно рассматривать как путь от 19 к 3. Условие о наличии числа 12 позволяет разделить путь на участок от 19 до 12 и участок от 12 до 3.

Для каждого числа вычисляем количество способов попасть в него командами A, B и C. Переходы, приводящие в число 9, исключаем; переход C из числа n приводит в число $\lfloor n/2 \rfloor$.

Поскольку все команды увеличивают число, любая программа, проходящая через 9, сначала достигает 9, а затем движется к 19. Поэтому количество подходящих программ равно произведению числа путей от 2 до 9 и числа путей от 9 до 19, не…$$N = N_{2\to 9} \cdot N_{9\to 19}$$

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

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

Последовательно вычисляя значения от 1 до 18, получаем $f(18)=16$. Это число программ, которые переводят 1 в 18.

Функция $F$ ложна, если оба слагаемых дизъюнкции ложны.$$x \to y = 0 \quad \text{и} \quad \neg(w \to z)=0$$

Импликация $x \to y$ ложна только при $x=1$ и $y=0$. Условие $\neg(w \to z)=0$ означает $w \to z=1$.

Так как траектория должна содержать число 8, каждую программу можно однозначно разделить на участок от 1 до 8 и участок от 8 до 18.$$N = N_{1\to 8}\cdot N_{8\to 18}$$

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

Общее уменьшение числа при переходе от 23 к 2 равно 21.$$23 - 2 = 21$$

Пусть команда «вычесть 2» выполняется $a$ раз, а команда «вычесть 5» — $b$ раз. Тогда количество вариантов команд удовлетворяет уравнению:$$2a + 5b = 21$$

Преобразуем выражение функции:$$F = \neg(w \to x) \mathbin{\lor} (y \to z) \mathbin{\lor} \neg y = (w \mathbin{\land} \neg x) \mathbin{\lor} (\neg y \mathbin{\lor} z) \mathbin{\lor} \neg y$$

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

Рассмотрим количество программ, переводящих число $n$ в число 12. Для последнего действия перед достижением результата $n$ возможны переходы из $n-1$ командой A и из $\lfloor n/2\rfloor$ командой B.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$

При вычислении от 12 до 30 получаем: $f(30)=8$. Это количество программ, которые переводят 30 в 12.

Внешняя импликация автоматически истинна при $x \notin D$. Поэтому рассмотрим только значения $x \in D$.

При $x \in D$ выражение $(\neg(x \in B) \land \neg(x \in A)) \to \neg(x \in D)$ будет истинным для всех $x$ только в том случае, если не существует элемента $D$, который не принадлежит ни $B$, ни $A$.

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

Число программ, переводящих 4 в 10, равно 13.

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

Последовательно вычисляя значения от 1 до 11, получаем $f(11)=37$.

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

Получаем значения: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=3$, $f(6)=6$, $f(7)=9$, $f(8)=15$, $f(9)=25$.