Question

Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_9, y_1, y_2, \ldots, y_9$, которые удовлетворяют всем перечисленным ниже условиям?

$$(
eg (x_1 \leftrightarrow y_1)) \leftrightarrow (x_2 \leftrightarrow y_2)$$
$$(
eg (x_2 \leftrightarrow y_2)) \leftrightarrow (x_3 \leftrightarrow y_3)$$
$$\ldots$$
$$(
eg (x_8 \leftrightarrow y_8)) \leftrightarrow (x_9 \leftrightarrow y_9)$$

В ответе укажите количество таких наборов.

Accepted Answer

1024

Answer

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

Обозначим $a_i = (x_i \leftrightarrow y_i)$ для каждой пары переменных. Тогда система принимает вид:

$$(
eg a_1) \leftrightarrow a_2$$
$$(
eg a_2) \leftrightarrow a_3$$
$$\ldots$$
$$(
eg a_8) \leftrightarrow a_9$$

Эквиваленция $(
eg a_i) \leftrightarrow a_{i+1}$ истинна тогда и только тогда, когда $
eg a_i = a_{i+1}$, то есть $a_{i+1} = 
eg a_i$.

Это означает, что значения $a_1, a_2, \ldots, a_9$ чередуются: если $a_1 = 0$, то $a_2 = 1$, $a_3 = 0$, $a_4 = 1$, и так далее. Аналогично, если $a_1 = 1$, то $a_2 = 0$, $a_3 = 1$, $a_4 = 0$, и так далее.

Таким образом, существует ровно два допустимых паттерна для последовательности $(a_1, a_2, \ldots, a_9)$:
- Паттерн 1: $(0, 1, 0, 1, 0, 1, 0, 1, 0)$
- Паттерн 2: $(1, 0, 1, 0, 1, 0, 1, 0, 1)$

Для каждого значения $a_i$:
- Если $a_i = 0$, то $x_i \leftrightarrow y_i$ ложно, значит $x_i 
eq y_i$. Возможны 2 набора: $(0, 1)$ или $(1, 0)$.
- Если $a_i = 1$, то $x_i \leftrightarrow y_i$ истинно, значит $x_i = y_i$. Возможны 2 набора: $(0, 0)$ или $(1, 1)$.

Для каждого паттерна имеется 9 пар переменных, и для каждой пары независимо выбирается один из двух допустимых наборов. Следовательно, для одного паттерна количество наборов равно $2^9 = 512$.

Так как паттернов два, общее количество наборов:
$$2 	imes 2^9 = 2 	imes 512 = 1024$$

Задание №23Алгоритмы и исполнителиЕГЭ по информатике