Тапсырма 23 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

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

Последнее слагаемое учитывается только для чётных $n$. Получаем значения до числа 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$$

Введём динамическое программирование: для каждого числа считаем количество программ, которые приводят к нему. Последний шаг в такую точку мог быть выполнен командами $+1$, $\times 2$ или $\times 3$.

Посчитаем количество способов попасть из 1 в 11. Для числа $n$ учитываются переходы из $n-1$, $n/2$ и $n/3$, если соответствующие значения являются целыми.

Проверим вариант, при котором окно разбила Аня. Тогда высказывание Сони ложно, поскольку разбивал не Володя.

Высказывание Миши истинно: утверждение Сони действительно является ложью.

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

Следовательно, значения $a_1, a_2, \ldots, a_9$ должны чередоваться. Возможны два варианта последовательности: начинающаяся с $1$ и начинающаяся с $0$.

Импликация ложна, когда её левая часть истинна, а правая — ложна.

Так как при истинности условия $\mathrm{ДЕЛ}(x,A)$ выражение $\neg\mathrm{ДЕЛ}(x,A)$ ложно, правая часть требует выполнения $\mathrm{ДЕЛ}(x,39)$.

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

Последовательно получаем значения: $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$.

Поскольку каждая команда увеличивает число, программа, содержащая в траектории числа 9 и 11, сначала должна попасть в 9, затем в 11.

Посчитаем динамически число способов попасть из 3 в каждое число с помощью команд «+1», «+2» и «×2». Для чисел от 3 до 9 получаем: $1, 1, 2, 4, 6, 11, 17$. Значит, $N(3 \to 9)=17$.$$N(x)=N(x-1)+N(x-2)+[x\ \text{чётно}]N\left(\frac{x}{2}\right)$$

Обозначим через $f(n)$ число способов получить число $n$ из 4, не попадая в 6. Для числа 6 полагаем $f(6)=0$, так как траектория не должна содержать 6.

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

Так как траектория должна содержать число 8, каждую подходящую программу можно единственным образом разделить на путь от 36 до 8 и путь от 8 до 2.

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

Обозначим через $f(n)$ количество программ, переводящих число 2 в число $n$ без попадания в 11. Для числа 2 имеем $f(2)=1$.

Число $n$ можно получить командой A из $n-1$, командой B из $n/2$ при чётном $n$ и командой C из $\sqrt{n}$, если $n$ является полным квадратом.

Так как функция истинна, конъюнктивный множитель $x$ должен быть равен 1, а множитель $\neg y$ — также равен 1. Поэтому $x=1$, $y=0$ во всех строках.$$x=1,\quad y=0$$

Для оставшихся переменных рассмотрим условие $\neg z \lor w$. Оно ложно только при $z=1$ и $w=0$. Поэтому допустимые пары значений имеют вид $(z,w)=(0,0),(0,1),(1,1)$.

Во всех трёх строках значение функции равно 0. Так как функция является дизъюнкцией, каждое слагаемое должно быть равно 0. В частности, $w=0$ и $x \ne z$.

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

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

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

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

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

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

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

Для каждой пары индексов $i<6$, $j<10$ условие является конъюнкцией двух импликаций. Оно нарушается только в случае, когда $x_i=y_j=1$, но $x_{i+1}=0$ или $y_{j+1}=0$.$$(x_i \land y_j) \Rightarrow (x_{i+1} \land y_{j+1})$$

Следовательно, перебираем двоичные наборы для переменных $x_1,\ldots,x_6$ и $y_1,\ldots,y_{10}$ и оставляем только те, в которых для всех $i=1,\ldots,5$ и $j=1,\ldots,9$ выполняется указанное условие.

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

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

Дизъюнкция ложна только тогда, когда ложны все три её части.$$(2x+y=80)\land(x\ge y)\land(A\ge x)$$

Из равенства $2x+y=80$ выражаем $y$ и учитываем неотрицательность переменных.$$y=80-2x\ge0\Rightarrow x\le40$$

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

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

Так как все команды увеличивают число, любую подходящую программу можно однозначно разделить в точке, где впервые получается число 10.

Количество способов получения каждого числа вычисляем рекуррентно: число способов попасть в $x$ равно сумме количеств способов попасть в $x-2$, $x-3$ и $x/2$, если $x$ чётно. При подсчёте программ от 10 до 25 способы, проходящие через 17…