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

Поскольку все команды увеличивают число, любая программа, проходящая через 9, сначала достигает 9, а затем движется к 19. Поэтому количество подходящих программ равно произведению числа путей от 2 до 9 и числа путей от 9 до 19, не…$$N = N_{2\to 9} \cdot N_{9\to 19}$$

Обозначим через $f(n)$ количество способов получить число $n$ из 2. Используем переход по последней команде: прибавление 1, прибавление 2 или умножение на 3.$$f(n)=f(n-1)+f(n-2)+\begin{cases}f(n/3),& n\text{ кратно }3\\0,&\text{иначе}\end{cases}$$

Обозначим через $f(n)$ количество программ, переводящих исходное число 1 в число $n$. Последняя команда программы может быть «Прибавь 2» или, если $n$ чётно, «Умножь на 2». Поэтому $f(n)=f(n-2)+f(n/2)$ для чётных $n$ и $f(n)=f(n-2)$ для…$$f(n)=f(n-2)+\begin{cases}f(n/2),& n\text{ чётно},\\0,& n\text{ нечётно}.\end{cases}$$

Последовательно вычисляя значения от 1 до 18, получаем $f(18)=16$. Это число программ, которые переводят 1 в 18.

Функция $F$ ложна, если оба слагаемых дизъюнкции ложны.$$x \to y = 0 \quad \text{и} \quad \neg(w \to z)=0$$

Импликация $x \to y$ ложна только при $x=1$ и $y=0$. Условие $\neg(w \to z)=0$ означает $w \to z=1$.

Так как траектория должна содержать число 8, каждую программу можно однозначно разделить на участок от 1 до 8 и участок от 8 до 18.$$N = N_{1\to 8}\cdot N_{8\to 18}$$

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

Общее уменьшение числа при переходе от 23 к 2 равно 21.$$23 - 2 = 21$$

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

Преобразуем выражение функции:$$F = \neg(w \to x) \mathbin{\lor} (y \to z) \mathbin{\lor} \neg y = (w \mathbin{\land} \neg x) \mathbin{\lor} (\neg y \mathbin{\lor} z) \mathbin{\lor} \neg y$$

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

Рассмотрим количество программ, переводящих число $n$ в число 12. Для последнего действия перед достижением результата $n$ возможны переходы из $n-1$ командой A и из $\lfloor n/2\rfloor$ командой B.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$

При вычислении от 12 до 30 получаем: $f(30)=8$. Это количество программ, которые переводят 30 в 12.

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

При $x \in D$ выражение $(\neg(x \in B) \land \neg(x \in A)) \to \neg(x \in D)$ будет истинным для всех $x$ только в том случае, если не существует элемента $D$, который не принадлежит ни $B$, ни $A$.

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

Число программ, переводящих 4 в 10, равно 13.

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

Последовательно вычисляя значения от 1 до 11, получаем $f(11)=37$.

Вычислим количество программ, переводящих число 2 в каждое число до 9. Обозначим это количество через $f(n)$. Для числа, кратного 3, учитываем также переход из $n/3$.$$f(n)=f(n-1)+f(n-2)+[3\mid n]f(n/3)$$

Получаем значения: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=3$, $f(6)=6$, $f(7)=9$, $f(8)=15$, $f(9)=25$.

Обозначим через $f(n)$ количество программ, переводящих число 2 в число $n$. Для нечётного $n$ последняя команда может быть только «прибавить 1», а для чётного возможны обе команды.$$f(n)=f(n-1)+f\left(\frac{n}{2}\right)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$

Последовательно получаем значения до числа 14: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(6)=3$, $f(8)=5$, $f(10)=7$, $f(12)=10$, $f(14)=13$.

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

В первой строке известны значения $0, 1, \_, 1$. Если первый столбец — это $x$, второй — $w$, третий — $z$, четвёртый — $y$, получаем $x=0$, $w=1$, $y=1$, $z=1$. Тогда все части функции равны 0.

Рассмотрим все допустимые переходы из исходного состояния 100. Команда A увеличивает текущее число на 1, а команда B выполняет перестановку двух последних цифр только при условии, что цифра десятков меньше цифры единиц.

Последовательно перебираем достижимые числа и для каждого числа сохраняем количество программ, которыми оно получено. При переходе по команде A значение увеличивается на 1; при допустимом переходе по команде B добавляется способ перейти к…

Так как во всех трёх строках $F = 0$, обе части дизъюнкции должны быть равны нулю.$$((y \to x) \to z) = 0,\quad \neg w = 0$$

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

Чтобы функция была ложной, первое слагаемое $\neg x$ должно быть ложным, а значит, $x=1$. Поэтому столбец, состоящий из единиц, — это столбец переменной $x$.

Второе слагаемое $y$ также должно быть ложным, следовательно, $y=0$. Поэтому столбец, состоящий из нулей, — это столбец переменной $y$.

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

Для любого числа n переход по команде A приходит из числа n-1. Дополнительный переход по команде B возможен, если перестановка двух последних цифр числа-источника разрешена.

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

Последовательно вычисляем количество способов от 3 до 9: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$, $f(9)=17$.$$f(9)=f(8)+f(7)=11+6=17$$

Посчитаем количество программ, переводящих 4 в каждое число до 11. Для числа $n$ последняя команда может быть прибавлением 1, прибавлением 2 или умножением на 2.$$f(n)=f(n-1)+f(n-2)+f(n/2)\text{ при чётном }n$$

Последовательно получаем: $f(4)=1$, $f(5)=1$, $f(6)=2$, $f(7)=3$, $f(8)=6$, $f(9)=9$, $f(10)=16$, $f(11)=25$.

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

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