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

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

Импликация $\mathrm{ДЕЛ}(x,36)\to\neg\mathrm{ДЕЛ}(x,54)$ ложна, когда число $x$ делится и на $36$, и на $54$.$$36\mid x\ \text{и}\ 54\mid x$$

Такие числа являются кратными наименьшему общему кратному чисел $36$ и $54$.$$\operatorname{НОК}(36,54)=108$$

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

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

Дизъюнкция может быть ложной только тогда, когда оба её выражения ложны. Для $x\notin B$ импликация истинна, поэтому рассмотрим только $x\in B$.

Импликация $(x\in B)\to\neg\mathrm{ДЕЛ}(x,21)$ ложна, если $x\in B$ и $\mathrm{ДЕЛ}(x,21)$ истинно.

От числа 1 до числа 21 нужно увеличить значение на 20.$$21 - 1 = 20$$

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

Дизъюнкция ложна, если ложны все её части одновременно.$$x + 2y \leq A,\quad y \geq x,\quad x \geq 33$$

При условиях $x \geq 33$ и $y \geq x$ минимальное значение выражения $x + 2y$ достигается при $x = 33$ и $y = 33$.$$x + 2y \geq 33 + 2 \cdot 33 = 99$$

Функция принимает значение 1, поэтому каждый множитель равен 1. Из множителя $\neg w=1$ получаем $w=0$.

Из множителя $\neg(x \equiv z)=1$ следует, что значения $x$ и $z$ различаются в каждой строке.

У каждой из 12 логических переменных два возможных значения, поэтому всего существует $2^{12}$ наборов.

Для каждого набора вычисляем значения выражений $x_i \to y_i$, $x_i \equiv y_i$ и проверяем пять условий для соседних пар, а также заключительное условие $x_6 \to y_6 = 1$.

Из условия $\neg(A=B)$ получаем $B \ne 45$.

Если $B<45$, то высказывание $A>B$ истинно, поэтому из импликации $(A>B) \to (B>C)$ следует $B>C$, то есть $B>43$.

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

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