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

Из условий $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$.

Из числа 5 в число 9 можно попасть только последовательным прибавлением единицы: $5 \to 6 \to 7 \to 8 \to 9$. Поэтому начальный участок программы единственный.$$N(5 \to 9)=1$$

Обозначим через $f(x)$ число способов попасть из 9 в $x$, не проходя через 27. Для остальных чисел используем динамическое программирование: последний шаг мог быть прибавлением 1, умножением на 2 или умножением на 3.$$f(x)=f(x-1)+[2\mid x]f\left(\frac{x}{2}\right)+[3\mid x]f\left(\frac{x}{3}\right)$$

Каждому числу сопоставим количество программ, которые переводят исходное число 111 в это число. Для числа 111 начальное количество программ равно 1.

Из каждого состояния добавляем переход по команде A: число увеличивается на 1. Также добавляем переход по команде B, если цифра в разряде десятков меньше цифры в разряде единиц; при этом две последние цифры меняются местами.

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

Последовательно вычисляя значения, получаем количество программ из 2 в 15:$$f(15)=f(13)+f(12)+f(5)=12+10+1=23$$

Импликация ложна только тогда, когда её левая часть истинна, а правая — ложна. Поэтому должно выполняться: $x$ не делится на $35$, $x$ делится на $A$ и $x$ не делится на $21$.$$\neg\mathrm{ДЕЛ}(x,35) \land \mathrm{ДЕЛ}(x,A) \land \neg\mathrm{ДЕЛ}(x,21)$$

Чтобы выражение было тождественно истинным, не должно существовать числа, кратного $A$ и одновременно не кратного ни $35$, ни $21$. В частности, само число $A$ должно делиться на $35$ или на $21$.

Чтобы выражение могло быть ложным, должны быть ложными второе и третье высказывания: $x \geq y$ и $x < 7$.$$0 \leq y \leq x \leq 6$$

В этой области максимальное значение произведения $x \cdot y$ достигается при $x = y = 6$.$$x \cdot y \leq 6 \cdot 6 = 36$$

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

Только первый столбец содержит 0 в первой и третьей строках и не содержит единиц, противоречащих условию $w=0$. Значит, первый столбец — это $w$.

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

Множитель $\neg(y \equiv z)$ равен единице тогда и только тогда, когда значения $y$ и $z$ различаются.$$\neg(y \equiv z)=1 \Rightarrow y\ne z$$

Пусть $f(n)$ — количество программ, переводящих число 2 в число $n$ без появления числа 14 в траектории. Начальное значение: $f(2)=1$, а для запрещённого числа полагаем $f(14)=0$.

Чтобы получить число $n$, последней могла быть команда прибавления 1, умножения на 2 или умножения на 3. Поэтому учитываются значения $f(n-1)$, $f(n/2)$ и $f(n/3)$ только при целочисленном делении.

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

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