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

От числа 17 до числа 1 нужно уменьшить значение на 16.$$17 - 1 = 16$$

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

Каждая дизъюнкция равна нулю, значит все её конъюнкции равны нулю. Из условий $x_i \land \neg x_{i+1}=0$ следует $x_i \le x_{i+1}$, поэтому последовательность $x$ неубывает.$$x_1 \le x_2 \le \ldots \le x_6$$

Из условий $\neg y_i \land y_{i+1}=0$ следует $y_i \ge y_{i+1}$, поэтому последовательность $y$ невозрастает.$$y_1 \ge y_2 \ge \ldots \ge y_6$$

Так как обе команды уменьшают число, любая программа, траектория которой содержит 9, однозначно разбивается на путь от 30 до 9 и путь от 9 до 1.

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

Чтобы дизъюнкция была тождественно истинной, не должно существовать таких $x$ и $y$, при которых все её части ложны.$$\neg(x + 2y < A) \land \neg(y > x) \land \neg(x > 20)$$

Все части одновременно ложны при условиях:$$x + 2y \geq A,\quad y \leq x,\quad x \leq 20$$

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

Посчитаем количество программ из 2 в каждое число до 9. Для числа $n$ учитываем переходы из $n-1$, из $n-2$ и, если $n$ кратно 3, из $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)=15+9+1=25$$

Функция $F$ равна нулю, только если каждый член дизъюнкции равен нулю.$$\neg x = 0,\quad y=0,\quad \neg z \wedge w=0$$

Из условия $\neg x=0$ получаем $x=1$, а из условия $y=0$ — $y=0$. Поэтому столбец с постоянными единицами — четвёртый, а столбец с постоянными нулями — третий.

Во второй строке значения в первых трёх столбцах равны $1$, $0$, $0$, а значение функции равно 0. Поэтому все три части дизъюнкции должны быть равны 0. Это возможно, если неизвестное значение в четвёртом столбце равно 1, а столбцы имеют…

Проверим вторую строку при $w=1$, $z=0$, $y=0$, $x=1$:$$(\neg 1 \land \neg 0) \lor (1 \equiv 0) \lor \neg 1 = 0 \lor 0 \lor 0 = 0$$

Дизъюнкция ложна только тогда, когда ложны все три высказывания:$$x \geq A,\quad y \geq A,\quad x + 2y \leq 50$$

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

Из каждого текущего числа рассматриваем три возможных перехода: вычитание 1, вычитание 4 и деление на 3 с взятием целой части. Переходы, после которых получается 9, не учитываем.$$A(n)=n-1,\quad B(n)=n-4,\quad C(n)=\left\lfloor\frac{n}{3}\right\rfloor$$

Для каждого числа храним два значения: количество способов попасть в него без числа 9 и количество способов попасть в него с уже встречавшимся числом 15. При переходе в 15 способ переносится во вторую группу.

Из условий $x_i \to x_{i+1}$ следует, что последовательность $x_1,\ldots,x_7$ не может переходить от единицы к нулю. Поэтому она имеет вид нескольких нулей, за которыми следуют единицы. Обозначим через $a$ позицию первой единицы; возможны…

Аналогично, из условий $y_i \to y_{i+1}$ последовательность $y_1,\ldots,y_7$ имеет вид нескольких нулей, за которыми следуют единицы. Обозначим через $k$ позицию первой единицы; значение $k=8$ соответствует полностью нулевой…

Всего имеется $5+9=14$ логических переменных, поэтому без ограничений существует $2^{14}=16384$ наборов.

Условие необходимо проверить для всех $i=1,2,3,4,5$ и $j=1,2,\ldots,9$, для которых $i<5$ и $j<9$. Всего таких пар $4\cdot 8=32$.

Введём обозначения $a_i = (x_i \equiv y_i)$. Тогда каждое условие имеет вид $\neg a_i \equiv a_{i+1}$, то есть соседние значения чередуются.$$a_{i+1} = \neg a_i$$

Последовательность $a_1, a_2, \ldots, a_8$ полностью определяется значением $a_1$. Поэтому возможны ровно две последовательности: начинающаяся с 0 и начинающаяся с 1.$$2$$

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

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

Если $x\notin B$, то условие импликации $x\in B$ ложно, поэтому вся импликация истинна.

Рассмотрим числа $x$ на отрезке $[60;80]$, делящиеся на 22. Единственное такое число — 66.

Введём обозначение $a_i = x_i \land y_i$. Тогда по закону де Моргана каждое условие принимает вид:$$a_i \equiv \neg(x_{i+1} \land y_{i+1}) = \neg a_{i+1}$$

Следовательно, значения $a_i$ должны чередоваться. Возможны только два шаблона:$$1,0,1,0,1,0,1,0 \quad \text{или} \quad 0,1,0,1,0,1,0,1$$

Дизъюнкция ложна только тогда, когда все её части ложны. Поэтому для всех приведённых строк должно выполняться $\neg x = 0$ и $y = 0$.$$x = 1,\quad y = 0$$

В таблице третий столбец во всех строках равен $1$, а второй — $0$. Следовательно, третий столбец соответствует $x$, второй — $y$.

Логическое выражение может быть ложным только тогда, когда ложны все три высказывания:$$x \geq A,\quad y \geq A,\quad x + 2y \leq 40$$

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

Обозначим через $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$$

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

Так как все команды увеличивают число, в каждой подходящей программе число 15 встречается один раз. Поэтому программу можно разделить на путь от 3 до 15 и путь от 15 до 25.$$N = N_{3\to15}\cdot N_{15\to25}$$

Для первой части применяем динамический подсчёт числа программ, исключая состояние 9. Получаем число допустимых путей от 3 до 15.

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

Так как $y$ — положительное целое число и $y \leq 2x - 10$, необходимо $x \geq 6$. Проверим возможные значения $x$ при $A = 7$.