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

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

При условиях $x \geq 30$ и $y \geq x$ минимальные неотрицательные значения переменных равны $x = 30$ и $y = 30$.

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

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

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

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

Чтобы выражение не было тождественно истинным, необходимо найти условия, при которых все три высказывания ложны.$$(3x + 2y \leq A) \land (y \geq x) \land (x \geq 10)$$

Из условий $x \geq 10$ и $y \geq x$ следует, что минимальные возможные значения переменных: $x = 10$, $y = 10$.

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

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

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

Для остальных чисел последняя команда может быть либо вычитанием 1, либо целочисленным делением на 2.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$

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

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

Чтобы функция была равна нулю, каждый член дизъюнкции должен быть равен нулю:$$F=0 \Rightarrow \neg(z\to w)=0,\quad x\to y=0,\quad \neg x=0$$

Из условия $\neg x=0$ получаем $x=1$. Импликация $x\to y$ при $x=1$ равна нулю только при $y=0$.$$x=1,\quad y=0$$

Условие $x_i \lor \neg x_{i+1}=1$ означает, что при $x_{i+1}=1$ обязательно $x_i=1$. Поэтому последовательность $x_1, x_2, \ldots, x_6$ не возрастает. Аналогично последовательность $y_1, y_2, \ldots, y_6$ не возрастает.$$x_i \geq x_{i+1},\quad y_i \geq y_{i+1}$$

Условия $x_i \lor \neg y_i=1$ и $x_6 \lor \neg y_6=1$ означают, что в каждой позиции значение $y_i=1$ возможно только при $x_i=1$.$$x_i \geq y_i\quad (i=1,\ldots,6)$$

Так как значение функции во всех трёх строках равно 1, множитель $w$ должен быть равен 1 во всех строках. Единственный столбец из одних единиц — третий, поэтому третьему столбцу соответствует $w$.$$w = 1$$

Для первых двух строк первые два столбца имеют значения $0,0$ и $0,1$, а четвёртый — значение 1. При $y=0$ условие $\neg(y \equiv z)=1$ требует $z=1$. Значит, первый столбец — $y$, а четвёртый — $z$.

Так как функция принимает значение 1, множитель $\lnot w$ также равен 1. Следовательно, $w = 0$.

Множитель $\lnot(y \equiv z)$ равен 1 только тогда, когда значения $y$ и $z$ различны.

Рассмотрим числа как вершины графа. Из каждой вершины проводим переход по команде A к числу, увеличенному на 1.

Переход по команде B добавляем только тогда, когда цифра десятков меньше цифры единиц; при этом две младшие цифры меняются местами.

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

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

Все команды увеличивают число, поэтому число 14 в траектории встречается не более одного раза. Подсчитаем количество путей от 3 до 14, запрещая число 8.$$f(n)=f(n-1)+f(n-2)+f(n/2),\quad f(8)=0$$

Последовательное вычисление даёт количество путей от 3 до 14 без прохождения через 8:$$f(14)=72$$

Выражение должно быть истинным при любых $x$ и $y$. Найдём условие, при котором оно ложно:$$\neg(x>A) \land \neg(y>A) \land \neg(x+2y<100)$$

С учётом целочисленных значений это означает:$$x \leq A,\quad y \leq A,\quad x+2y \geq 100$$

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

Если $x \notin B$, внешняя импликация будет истинной только тогда, когда внутренняя импликация истинна. Следовательно, для любого $x \in C$, не принадлежащего $A$, должно выполняться $x \in B$.

Если $x \notin P$, внешняя импликация истинна автоматически. Поэтому рассмотрим только $x \in P$.

При $x \in P$ заключение внутренней импликации $\neg(x \in P)$ ложно. Чтобы импликация была истинной, её условие должно быть ложным:$$(x \in Q) \land \neg(x \in A) = 0$$

Выражение может быть ложным только тогда, когда все три части дизъюнкции ложны. Из условий $x < 20$ и $y < 20$ получаем $x \geq 20$ и $y \geq 20$.$$x \geq 20,\quad y \geq 20$$

При таких неотрицательных целых $x$ и $y$ минимальное значение левой части первого неравенства достигается при $x = 20$ и $y = 20.$$y + 3x \geq 20 + 3 \cdot 20 = 80$$

Посчитаем количество программ, переводящих число 2 в число 6. Обозначим через f(n) число способов получить n из 2.$$f(n)=f(n-1)+f(n-2)+f(n/3)\text{ при }3\mid n$$

Последовательно получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=f(5)+f(4)+f(2)=3+2+1=6.

Посчитаем количество программ, переводящих число 2 в число 11. Для числа $n$ учитываем последние команды «прибавить 2», «прибавить 3» и, при чётном $n$, «умножить на 2». Получаем $f(11)=10$.$$f(n)=f(n-2)+f(n-3)+[n\text{ чётно}]f\left(\frac n2\right)$$

Аналогично посчитаем количество программ, переводящих число 11 в число 22. Получаем $g(22)=10$.