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

Из числа 5 в число 9 можно попасть только последовательным прибавлением единицы: $5 \to 6 \to 7 \to 8 \to 9$. Поэтому начальный участок программы единственный.$$N(5 \to 9)=1$$

Обозначим через $f(x)$ число способов попасть из 9 в $x$, не проходя через 27. Для остальных чисел используем динамическое программирование: последний шаг мог быть прибавлением 1, умножением на 2 или умножением на 3.$$f(x)=f(x-1)+[2\mid x]f\left(\frac{x}{2}\right)+[3\mid x]f\left(\frac{x}{3}\right)$$

Каждому числу сопоставим количество программ, которые переводят исходное число 111 в это число. Для числа 111 начальное количество программ равно 1.

Из каждого состояния добавляем переход по команде A: число увеличивается на 1. Также добавляем переход по команде B, если цифра в разряде десятков меньше цифры в разряде единиц; при этом две последние цифры меняются местами.

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

Последовательно вычисляя значения, получаем количество программ из 2 в 15:$$f(15)=f(13)+f(12)+f(5)=12+10+1=23$$

Импликация ложна только тогда, когда её левая часть истинна, а правая — ложна. Поэтому должно выполняться: $x$ не делится на $35$, $x$ делится на $A$ и $x$ не делится на $21$.$$\neg\mathrm{ДЕЛ}(x,35) \land \mathrm{ДЕЛ}(x,A) \land \neg\mathrm{ДЕЛ}(x,21)$$

Чтобы выражение было тождественно истинным, не должно существовать числа, кратного $A$ и одновременно не кратного ни $35$, ни $21$. В частности, само число $A$ должно делиться на $35$ или на $21$.

Чтобы выражение могло быть ложным, должны быть ложными второе и третье высказывания: $x \geq y$ и $x < 7$.$$0 \leq y \leq x \leq 6$$

В этой области максимальное значение произведения $x \cdot y$ достигается при $x = y = 6$.$$x \cdot y \leq 6 \cdot 6 = 36$$

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

Только первый столбец содержит 0 в первой и третьей строках и не содержит единиц, противоречащих условию $w=0$. Значит, первый столбец — это $w$.

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

Множитель $\neg(y \equiv z)$ равен единице тогда и только тогда, когда значения $y$ и $z$ различаются.$$\neg(y \equiv z)=1 \Rightarrow y\ne z$$

Пусть $f(n)$ — количество программ, переводящих число 2 в число $n$ без появления числа 14 в траектории. Начальное значение: $f(2)=1$, а для запрещённого числа полагаем $f(14)=0$.

Чтобы получить число $n$, последней могла быть команда прибавления 1, умножения на 2 или умножения на 3. Поэтому учитываются значения $f(n-1)$, $f(n/2)$ и $f(n/3)$ только при целочисленном делении.

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

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

Если $x < 8$, третье высказывание истинно. Если $x > y$, истинно второе высказывание.$$x < 8 \lor x > y$$

Остаётся случай, когда $x \geq 8$ и $x \leq y$. Тогда $y \geq x \geq 8$, поэтому произведение минимально при $x = y = 8$.$$x \cdot y \geq 8 \cdot 8 = 64$$

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

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

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

Четвёртый столбец содержит 0 во всех строках, поэтому ему соответствует переменная $w$.

Обозначим $a_i = x_i \land y_i$. Тогда каждое равенство системы принимает вид:$$a_i \equiv \lnot a_{i+1}$$

Следовательно, значения $a_1, a_2, \ldots, a_6$ чередуются. Возможны две последовательности: $101010$ и $010101$.

Сначала подсчитаем количество программ, переводящих число 4 в число 10. Обозначим через f(n) число способов получить n из 4.$$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(10)=f(9)+f(8)+f(5)=9+6+1=16$$

Чтобы выражение могло быть ложным, первые два высказывания должны быть ложными:$$\neg(x \ge 12) \land \neg(3x < y) \Rightarrow x < 12,\ y \le 3x$$

Так как $x$ и $y$ неотрицательны, наибольшее значение произведения $xy$ при этих условиях достигается при $x = 11$ и $y = 3 \cdot 11 = 33$.$$xy_{\max} = 11 \cdot 33 = 363$$

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

Рассмотрим точки, для которых $x \notin B$. Тогда внешняя импликация истинна только в том случае, если истинна внутренняя импликация.

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

Вычисляя значения от 3 до 10, получаем: $f(3)=1$, $f(4)=1$, $f(5)=1$, $f(6)=3$, $f(7)=4$, $f(8)=6$, $f(9)=9$, $f(10)=14$.

Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$ без прохождения через 9 и 15. Для разрешённого числа способы попасть в него приходят из $n-1$ командой $A$, из $n-3$ командой $B$, а также из $n/3$ командой $C$…$$f(n)=f(n-1)+f(n-3)+f(n/3)$$

Для запрещённых чисел устанавливаем $f(9)=0$ и $f(15)=0$. Начальное значение: $f(3)=1$.

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

Для перехода из 30 в 8 вычисление рекуррентно даёт: $f(8)=1$, затем $f(9),\ldots,f(15)=1$, $f(16)=2$, и далее $f(30)=16$.

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

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