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

Если $x < 8$, третье высказывание истинно. Если $x > y$, истинно второе высказывание.$$x < 8 \lor x > y$$

Остаётся случай, когда $x \geq 8$ и $x \leq y$. Тогда $y \geq x \geq 8$, поэтому произведение минимально при $x = y = 8$.$$x \cdot y \geq 8 \cdot 8 = 64$$

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

Во всех строках четвёртый столбец содержит 0, поэтому ему соответствует переменная $w$.

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

Четвёртый столбец содержит 0 во всех строках, поэтому ему соответствует переменная $w$.

Обозначим $a_i = x_i \land y_i$. Тогда каждое равенство системы принимает вид:$$a_i \equiv \lnot a_{i+1}$$

Следовательно, значения $a_1, a_2, \ldots, a_6$ чередуются. Возможны две последовательности: $101010$ и $010101$.

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

Чтобы выражение могло быть ложным, первые два высказывания должны быть ложными:$$\neg(x \ge 12) \land \neg(3x < y) \Rightarrow x < 12,\ y \le 3x$$

Так как $x$ и $y$ неотрицательны, наибольшее значение произведения $xy$ при этих условиях достигается при $x = 11$ и $y = 3 \cdot 11 = 33$.$$xy_{\max} = 11 \cdot 33 = 363$$

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

Рассмотрим точки, для которых $x \notin B$. Тогда внешняя импликация истинна только в том случае, если истинна внутренняя импликация.

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

Вычисляя значения от 3 до 10, получаем: $f(3)=1$, $f(4)=1$, $f(5)=1$, $f(6)=3$, $f(7)=4$, $f(8)=6$, $f(9)=9$, $f(10)=14$.

Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$ без прохождения через 9 и 15. Для разрешённого числа способы попасть в него приходят из $n-1$ командой $A$, из $n-3$ командой $B$, а также из $n/3$ командой $C$…$$f(n)=f(n-1)+f(n-3)+f(n/3)$$

Для запрещённых чисел устанавливаем $f(9)=0$ и $f(15)=0$. Начальное значение: $f(3)=1$.

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

Для перехода из 30 в 8 вычисление рекуррентно даёт: $f(8)=1$, затем $f(9),\ldots,f(15)=1$, $f(16)=2$, и далее $f(30)=16$.

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

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

Рассмотрим каждую пару $(x_i, y_i)$ как одно состояние. Выражение $\neg x_i \lor y_i$ ложно только в состоянии $(1, 0)$.

Выражение $\neg x_{i+1} \land y_{i+1}$ истинно только в состоянии $(0, 1)$. Импликация нарушается, когда её левая часть истинна, а правая ложна.

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

Нулевые значения во второй и третьей строках находятся в первом столбце, поэтому первый столбец соответствует переменной $w$.

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

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

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

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

Обозначим состояние пары $(x_i,y_i)$ одним из четырёх кодов: $00$, $10$, $01$, $11$.

Условия перехода между соседними парами дают следующие возможности: $00 \to 00,10,01,11$; $10 \to 11$; $01 \to 01,11$; $11 \to 11$.

Так как все команды увеличивают число, траектория может содержать число 9 только один раз. Поэтому программу можно разделить на путь от 3 до 9 и путь от 9 до 14.

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

Раскроем отрицание импликации.$$\neg(x \to w) = x \land \neg w$$

Так как во всех трёх строках $F=0$, дизъюнкция равна нулю. Следовательно, каждый её член должен быть равен нулю: $x \land \neg w=0$, $y \equiv z=0$ и $y=0$. Однако при $y=0$ условие $y \equiv z=0$ даёт $z=1$.

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

В этой области максимальное значение выражения $y + 2x$ достигается при $x = 25$ и $y = 25$:$$y + 2x = 25 + 2 \cdot 25 = 75$$

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

При $y \leq x$ и $x \leq 60$ максимальное значение $x + 2y$ достигается при $x = 60$ и $y = 60$.$$x + 2y \leq 60 + 2 \cdot 60 = 180$$