Информатика ЕГЭ — решения заданий ФИПИ с ответами

Так как все команды увеличивают число, число 9 в траектории достигается ровно один раз. Поэтому программы можно разбить на две независимые части: от 2 до 9 и от 9 до 17.

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

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

Из равенства $2x+y=100$ выразим $y$ и подставим в условие $x\ge y$:$$y=100-2x,\quad x\ge100-2x$$

Импликация ложна только тогда, когда её первое высказывание истинно, а второе ложно. Значит, $x$ должно делиться на $2$ и на $5 одновременно.$$10 \mid x$$

Наименьшее положительное значение $x$, кратное $10$, равно $10$.

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

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

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

В третьей строке значения в столбцах 2, 3 и 4 равны соответственно $1$, $0$, $0$, а во второй строке значение в столбце 2 равно $0$. Единственным возможным столбцом для $z$ является первый столбец.$$z = \text{столбец 1}$$

Каждую пару $(x_i,y_i)$ можно рассматривать как одно из четырёх состояний: $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$.

Импликация $(\neg x_i \lor y_i) \to (\neg x_{i+1} \land y_{i+1})$ ложна только при $x_i=1$ и $y_i=0$, когда первая часть истинна, а вторая часть для следующей пары должна быть истинной. Поэтому из состояний $(0,0)$, $(0,1)$ и $(1,1)$…

Так как значение функции равно 0, каждое слагаемое дизъюнкции должно быть равно 0: $x\land\neg y=0$, $y\equiv z=0$ и $w=0$.

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

Дизъюнкция может быть ложной только тогда, когда оба её выражения ложны. Первое выражение $\mathrm{ДЕЛ}(x,3) \to \neg\mathrm{ДЕЛ}(x,5)$ ложно, если $x$ делится на $3$ и одновременно делится на $5$.$$\mathrm{ДЕЛ}(x,3) \land \mathrm{ДЕЛ}(x,5)$$

Следовательно, достаточно рассмотреть положительные числа, кратные $15$. Наименьшее такое число — $x=15$.

Всего логических переменных двенадцать: $x_1,\ldots,x_7$ и $y_1,\ldots,y_5$. Поэтому полный перебор содержит $2^{12}=4096$ наборов.$$2^{7+5}=2^{12}=4096$$

Для каждого набора значений проверяем условия для всех $i=1,\ldots,6$ и $j=1,\ldots,4$. Всего проверяется $6\cdot4=24$ выражения.

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

Последовательно вычисляя значения от 3 до 14, получаем количество программ, переводящих 3 в 14:$$f(14)=46$$

Внешняя импликация может быть ложной только при $x \in P$, когда её правая часть ложна.

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

Если $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$.