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

Рассмотрим числа как вершины графа. Из каждой вершины проводим переход по команде A к числу, увеличенному на 1.

Переход по команде B добавляем только тогда, когда цифра десятков меньше цифры единиц; при этом две младшие цифры меняются местами.

Дизъюнкция может принимать значение 0 только тогда, когда все три её части равны 0.$$(48 \ne y + 2x) = 0,\quad (A < x) = 0,\quad (A < y) = 0$$

Следовательно, для ложности выражения должны одновременно выполняться условия:$$y + 2x = 48,\quad x \leq A,\quad y \leq A$$

Все команды увеличивают число, поэтому число 14 в траектории встречается не более одного раза. Подсчитаем количество путей от 3 до 14, запрещая число 8.$$f(n)=f(n-1)+f(n-2)+f(n/2),\quad f(8)=0$$

Последовательное вычисление даёт количество путей от 3 до 14 без прохождения через 8:$$f(14)=72$$

Выражение должно быть истинным при любых $x$ и $y$. Найдём условие, при котором оно ложно:$$\neg(x>A) \land \neg(y>A) \land \neg(x+2y<100)$$

С учётом целочисленных значений это означает:$$x \leq A,\quad y \leq A,\quad x+2y \geq 100$$

Если $x \in B$, то выражение $\neg(x \in B)$ ложно, поэтому внешняя импликация истинна независимо от значения второй части.

Если $x \notin B$, внешняя импликация будет истинной только тогда, когда внутренняя импликация истинна. Следовательно, для любого $x \in C$, не принадлежащего $A$, должно выполняться $x \in B$.

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

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

Выражение может быть ложным только тогда, когда все три части дизъюнкции ложны. Из условий $x < 20$ и $y < 20$ получаем $x \geq 20$ и $y \geq 20$.$$x \geq 20,\quad y \geq 20$$

При таких неотрицательных целых $x$ и $y$ минимальное значение левой части первого неравенства достигается при $x = 20$ и $y = 20.$$y + 3x \geq 20 + 3 \cdot 20 = 80$$

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

Последовательно получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=f(5)+f(4)+f(2)=3+2+1=6.

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

Аналогично посчитаем количество программ, переводящих число 11 в число 22. Получаем $g(22)=10$.

Пусть $f(n)$ — количество допустимых программ, переводящих число $n$ в число 3. Базовое значение: из числа 3 можно завершить программу без выполнения команд.$$f(3)=1$$

Для каждого числа $n$ учитываем три последние команды: A переводит в $n-1$, B — в $n-2$, C — в $\lfloor n/3\rfloor$.$$f(n)=f(n-1)+f(n-2)+f(\lfloor n/3\rfloor)$$

Представим числа $42$ и $34$ в двоичной системе:$$42 = 101010_2, \qquad 34 = 100010_2$$

Условие $x \mathbin{\&} 34 = 0$ означает, что в числе $x$ не могут быть установлены разряды, соответствующие единицам числа $34$: разряды $2^1$ и $2^5$.

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

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

Импликация может быть ложной только тогда, когда её заключение ложно. Заключение $\neg\mathrm{ДЕЛ}(x,16) \lor \neg\mathrm{ДЕЛ}(x,24)$ ложно, если $x$ делится и на $16$, и на $24$.$$\operatorname{НОК}(16,24)=48$$

Следовательно, опасными являются все значения $x$, кратные $48$. Для них условие импликации должно быть ложным, то есть $x$ должно делиться на $A$.

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

В первой строке значения в столбцах 2 и 3 равны 1 и 0. Они должны соответствовать $z$ и $y$, поскольку эти значения различны. Сопоставление с другими строками показывает, что столбец 2 — это $z$, а столбец 3 — $y$.

Проверим соответствие столбцов $w$, $y$, $x$, $z$. В первой строке получаем $w=0$, $y=1$, $x=1$, $z=0$.$$(x \land \neg y) \lor (y \equiv z) \lor w = (1 \land \neg 1) \lor (1 \equiv 0) \lor 0 = 0$$

Во второй строке известны $y=1$ и $x=0$. Чтобы значение функции было равно 0, необходимо $w=0$ и $z=0$.$$(0 \land \neg 1) \lor (1 \equiv 0) \lor 0 = 0$$

Преобразуем условие $F = 0$. Дизъюнкция равна нулю только тогда, когда каждый её элемент равен нулю.$$F = (w \land \neg y) \lor (\neg x \lor z) \lor \neg x$$

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

Так как все команды уменьшают число, траектория обязательно проходит через 13 ровно один раз. Поэтому количество подходящих программ равно произведению числа способов попасть из 19 в 13 и числа способов попасть из 13 в 2, избегая числа 7.

Обозначим через $f(n)$ число способов попасть из $n$ в 13. Для $n>13$ учитываем переходы $n\to n-1$, $n\to n-4$ и $n\to \lfloor n/3\rfloor$. Число 7 не может быть промежуточным состоянием.$$f(13)=1,\quad f(14)=1,\quad f(15)=1,\quad f(16)=1,\quad f(17)=2,\quad f(18)=3,\quad f(19)=4$$

Если $x \notin P$, первая импликация истинна автоматически. Поэтому достаточно рассмотреть точки $x \in P$.$$x \in P \Rightarrow (((x \in Q) \land \neg(x \in A)) \to \neg(x \in P))$$

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

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

Последовательно вычисляем количество программ до числа 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$.$$f(10)=f(9)+f(5)=10+4=14$$

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

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