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

Если $x \notin B$, то условие $x \in B$ ложно, поэтому импликация истинна. Рассмотрим только $x \in [50; 60]$.

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

Чтобы выражение могло быть ложным, все три высказывания должны быть ложными. Второе и третье высказывания ложны при условиях:$$y \leq x,\quad x \leq 30$$

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

Дизъюнкция будет ложной только тогда, когда одновременно ложно первое слагаемое и ложно второе слагаемое.

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

Введём динамику: количество способов получить число складывается из количества способов получить его из предыдущего числа командой 1 и из числа, вдвое меньшего, командой 2.

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

Во всех трёх строках значение функции равно нулю. Поэтому оба слагаемых дизъюнкции должны быть равны нулю: $\neg z = 0$, а значит, $z = 1$.$$F = 0 \Rightarrow z = 1$$

Для ложности импликации $(w \to y) \to (x \equiv y)$ необходимо, чтобы её посылка была истинной, а заключение ложным.$$w \to y = 1, \quad x \equiv y = 0$$

Так как все команды увеличивают число, числа 10 и 12 в траектории встречаются именно в таком порядке. Поэтому количество подходящих программ равно произведению числа способов пройти участки $3\to10$, $10\to12$ и $12\to13$.$$N(3,13;\ 10,12)=N(3,10)\cdot N(10,12)\cdot N(12,13)$$

Для участка от 3 до 10 подсчётом по последней команде получаем последовательность количества путей: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$, $f(9)=17$, $f(10)=30$.$$N(3,10)=30$$

Выражение может быть ложным только тогда, когда ложны все три высказывания:$$x \cdot y \geq A,\quad x \geq y,\quad x < 8$$

Так как $x$ и $y$ — неотрицательные целые числа, из условий $x < 8$ и $x \geq y$ следует, что $x \leq 7$ и $y \leq 7$.

Введём $f(n)$ — количество программ, переводящих исходное число 101 в число $n$. Для исходного числа $f(101)=1$.

Переход по команде A возможен из числа $n-1$, поэтому он добавляет $f(n-1)$ способов.

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

Условие $\neg(x\equiv z)=1$ означает, что значения $x$ и $z$ в каждой строке различаются. Перебор оставшихся вариантов размещения переменных с учётом трёх строк таблицы оставляет единственный вариант: первый столбец — $x$, третий — $z$…$$x\ne z$$

Так как значение функции в каждой из трёх строк равно 1, каждый набор должен удовлетворять всем условиям произведения логических выражений.$$w=1,\quad x\ne z,\quad (x=0)\lor(y=0)$$

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

Обозначим пару значений на позиции $i$ как $(x_i,y_i)$. Если эта пара равна $(0,0)$, то левая часть импликации ложна, поэтому следующая пара может быть любой из четырёх.

Если пара не равна $(0,0)$, то $x_i \lor y_i = 1$. Чтобы импликация была истинной, необходимо $x_{i+1} \land y_{i+1}=1$, то есть следующая пара обязана быть $(1,1)$.

Если среди $y_1,\ldots,y_7$ есть хотя бы одна единица, то при наличии единицы среди $x_1,\ldots,x_5$ все значения $x$ от первой такой единицы до $x_6$ должны быть равны единице. Если же среди $x_1,\ldots,x_5$ есть единица, то аналогичное…

Случай 1: в обеих группах есть единицы — среди $x_1,\ldots,x_5$ и среди $y_1,\ldots,y_7$. Последовательность $x$ имеет 5 вариантов расположения первой единицы, а последовательность $y$ — 7 вариантов. Получаем $5\cdot7=35$ наборов.

Представим каждую пару $(x_i,y_j)$ как клетку таблицы. При $x_i \land y_j = 1$ первое условие требует выполнения $x_i \land y_{j+1}$, а второе — $x_{i+1} \land y_j$.

Таким образом, при переборе наборов значений нужно исключать все конфигурации, в которых из клетки $(i,j)$ со значением $1$ можно перейти вправо или вниз в клетку со значением $0$.

Чтобы исходное выражение было ложным, все три высказывания должны быть ложными. Второе и третье высказывания ложны при $x \leq 15$ и $y \leq 30$.$$x \leq 15,\quad y \leq 30$$

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

Импликация $a \to b$ истинна, если $a = 0$ или $b = 1$. Поэтому из условий для каждого $i \geq 2$ следует: если $x_i = 1$, то $x_{i-1} = 1$ и $y_i = 1$; если $y_i = 1$, то $y_{i-1} = 1$.

Следовательно, единицы в каждой последовательности идут только в начале. Последовательность $x$ определяется числом $a$ единиц, а последовательность $y$ — числом $b$ единиц, где $a,b \in \{0,1,\ldots,6\}$.

Так как во всех приведённых строках $F = 1$, конъюнкция $\neg w$ должна быть истинной. Значит, $w = 0$ во всех строках. Единственный столбец, в котором в известных ячейках стоят только нули, — первый.$$w = 0$$

Условие $\neg(y \equiv z)$ означает, что значения $y$ и $z$ различны в каждой строке.

Раскроем импликации: $y \to w = \neg y \lor w$, $x \to z = \neg x \lor z$.$$F = \neg(y \to w) \lor (x \to z) \lor \neg x = (y \land \neg w) \lor \neg x \lor z$$

Чтобы значение функции было равно нулю, должны выполняться условия $x = 1$, $z = 0$, а также $y \land \neg w = 0$.

Для каждого $i=1,\ldots,5$ первое условие означает: если $x_i=1$, то $x_{i+1}=1$ и $y_i=1$. Поэтому после появления первой единицы среди $x_i$ все последующие $x_i$ также равны единице.

Если все $x_i=0$, то все переменные $y_i$ могут принимать произвольные значения. Получаем $2^6=64$ набора.

Во всех трёх строках значение функции равно $0$. Поэтому дизъюнкция равна нулю, а значит, каждое её слагаемое равно нулю. В частности, $w=0$.$$w=0$$

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

Введём динамическое подсчитывание количества программ, ведущих из одного числа в другое. Для попадания в число $x$ последняя команда могла быть одной из трёх: прибавление 2, умножение на 2 или прибавление 3.

Отдельно подсчитываем программы перехода от исходного числа 2 к числу 10 и программы перехода от числа 10 к числу 21. По рекуррентному подсчёту получаем по 9 программ для каждого участка.