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

Пусть $f(n)$ — количество допустимых программ, переводящих число $n$ в число 3. Базовое значение: из числа 3 можно завершить программу без выполнения команд.$$f(3)=1$$

Для каждого числа $n$ учитываем три последние команды: A переводит в $n-1$, B — в $n-2$, C — в $\lfloor n/3\rfloor$.$$f(n)=f(n-1)+f(n-2)+f(\lfloor n/3\rfloor)$$

Представим числа $42$ и $34$ в двоичной системе:$$42 = 101010_2, \qquad 34 = 100010_2$$

Условие $x \mathbin{\&} 34 = 0$ означает, что в числе $x$ не могут быть установлены разряды, соответствующие единицам числа $34$: разряды $2^1$ и $2^5$.

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

Последовательно вычисляя значения, получаем:$$f(1),\ldots,f(10)=1,2,3,5,7,10,13,18,23,30$$

Импликация может быть ложной только тогда, когда её заключение ложно. Заключение $\neg\mathrm{ДЕЛ}(x,16) \lor \neg\mathrm{ДЕЛ}(x,24)$ ложно, если $x$ делится и на $16$, и на $24$.$$\operatorname{НОК}(16,24)=48$$

Следовательно, опасными являются все значения $x$, кратные $48$. Для них условие импликации должно быть ложным, то есть $x$ должно делиться на $A$.

Во всех трёх строках значение функции равно 0. Следовательно, $w=0$, $x \land y=0$, а $y \equiv z=0$, то есть $y$ и $z$ имеют разные значения.$$(x \land y) \lor (y \equiv z) \lor w = 0$$

В первой строке значения в столбцах 2 и 3 равны 1 и 0. Они должны соответствовать $z$ и $y$, поскольку эти значения различны. Сопоставление с другими строками показывает, что столбец 2 — это $z$, а столбец 3 — $y$.

Проверим соответствие столбцов $w$, $y$, $x$, $z$. В первой строке получаем $w=0$, $y=1$, $x=1$, $z=0$.$$(x \land \neg y) \lor (y \equiv z) \lor w = (1 \land \neg 1) \lor (1 \equiv 0) \lor 0 = 0$$

Во второй строке известны $y=1$ и $x=0$. Чтобы значение функции было равно 0, необходимо $w=0$ и $z=0$.$$(0 \land \neg 1) \lor (1 \equiv 0) \lor 0 = 0$$

Преобразуем условие $F = 0$. Дизъюнкция равна нулю только тогда, когда каждый её элемент равен нулю.$$F = (w \land \neg y) \lor (\neg x \lor z) \lor \neg x$$

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

Так как все команды уменьшают число, траектория обязательно проходит через 13 ровно один раз. Поэтому количество подходящих программ равно произведению числа способов попасть из 19 в 13 и числа способов попасть из 13 в 2, избегая числа 7.

Обозначим через $f(n)$ число способов попасть из $n$ в 13. Для $n>13$ учитываем переходы $n\to n-1$, $n\to n-4$ и $n\to \lfloor n/3\rfloor$. Число 7 не может быть промежуточным состоянием.$$f(13)=1,\quad f(14)=1,\quad f(15)=1,\quad f(16)=1,\quad f(17)=2,\quad f(18)=3,\quad f(19)=4$$

Если $x \notin P$, первая импликация истинна автоматически. Поэтому достаточно рассмотреть точки $x \in P$.$$x \in P \Rightarrow (((x \in Q) \land \neg(x \in A)) \to \neg(x \in P))$$

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

Обозначим через $f(n)$ количество программ, переводящих число 1 в число $n$. Последняя команда может быть прибавлением 1 или умножением на 2.$$f(n)=f(n-1)+f(n/2)\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$.$$f(10)=f(9)+f(5)=10+4=14$$

Чтобы дизъюнкция могла быть ложной, второе и третье высказывания должны быть ложными: $x \leq 25$ и $y \leq 30$.

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

Чтобы функция $\neg(y \to (x \equiv w)) \land (z \to x)$ была равна 1, оба множителя должны быть равны 1. Условие $\neg(y \to (x \equiv w))=1$ означает $y=1$ и $x \ne w$.

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

Преобразуем отрицание импликации и импликацию $y \to w$: $\neg(x \to z) = x \mathbin{\land} \neg z$, $y \to w = \neg y \mathbin{\lor} w$.$$\ F = (x \mathbin{\land} \neg z) \mathbin{\lor} \neg y \mathbin{\lor} w$$

Чтобы значение функции было равно нулю, необходимо, чтобы все три дизъюнкта были ложны. Поэтому $y = 1$, $w = 0$, а $x \mathbin{\land} \neg z = 0$, то есть $x = 0$ или $z = 1$.

Во всех указанных строках значение функции равно нулю. Обозначим $A = (w \to z) \to x$. Тогда $A \lor \lnot y = 0$ возможно только при $A = 0$ и $y = 1$.$$y = 1$$

Импликация $(w \to z) \to x$ равна нулю только тогда, когда её левая часть равна единице, а $x = 0$. Следовательно, в каждой из строк $x = 0$.$$w \to z = 1,\quad x = 0$$

Во всех трёх строках значение функции равно 0. Дизъюнкция может быть равна 0 только тогда, когда каждый её компонент равен 0.$$(\neg x \land \neg y)=0,\quad (y\equiv z)=0,\quad w=0$$

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

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

Условие $\neg(y\equiv z)=1$ означает, что значения $y$ и $z$ различаются. В первой строке после учёта $w=1$ имеем $x=0$, $y=0$, поэтому $z=0$. Во второй строке $z=1$, $y=0$, а в третьей строке $z=0$, $y=1$.$$\neg(y\equiv z)=1\iff y\ne z$$

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

Из $\neg(y \equiv z)=1$ следует, что значения $y$ и $z$ различаются.

Так как обе команды уменьшают число, траектория может содержать число 12 только один раз. Поэтому любую подходящую программу можно однозначно разделить на путь от 30 до 12 и путь от 12 до 1.

Обозначим через $f(n)$ количество способов получить число 12 из числа $n$. Для $n > 12$ имеем $f(n)=f(n-2)+f(\lfloor n/2\rfloor)$, поскольку последней выполненной командой может быть A или B. Последовательное вычисление даёт $f(30)=3$.$$f(30)=f(28)+f(15)=3$$

Так как все команды увеличивают число, сначала траектория проходит через 8, затем через 10.$$N = N_{2\to 8} \cdot N_{8\to 10} \cdot N_{10\to 12}$$

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

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

Это равносильно системе условий:$$2x+y=50,\quad x\ge y,\quad A\ge x$$