Шешімі: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_9, y_1, y_2, \ldots, y_9$, удовлетворяющих всем условиям системы: для каждого $i$ от $1$ до $8$ выполняется $(x_i \lor y_i) \to (x_{i+1} \land y_{i+1}) = 1$?
Шешім по шагам
6 қадамОбозначим пару значений на позиции $i$ как $(x_i,y_i)$. Если эта пара равна $(0,0)$, то левая часть импликации ложна, поэтому следующая пара может быть любой из четырёх.
Если пара не равна $(0,0)$, то $x_i \lor y_i = 1$. Чтобы импликация была истинной, необходимо $x_{i+1} \land y_{i+1}=1$, то есть следующая пара обязана быть $(1,1)$.
Рассмотрим положение первой ненулевой пары. Если все тоғыз пар равны $(0,0)$, получаем один набор.
Если первая ненулевая пара находится на одной из первых восьми позиций, её можно выбрать тремя способами: $(0,1)$, $(1,0)$ или $(1,1)$. Все последующие пары тогда однозначно равны $(1,1)$. Это даёт $8 \cdot 3$ наборов.
Если первая ненулевая пара находится на девятой позиции, она также выбирается тремя способами, и ограничений после неё уже нет.
Итого число наборов равно $1 + 8 \cdot 3 + 3 = 28$.
Где здесь ошибаются
Считать, что из ненулевой пары следующая пара может быть любой.
Не учитывать случай, когда все пары равны $(0,0)$.
Забывать, что первая ненулевая пара на девятой позиции не задаёт ограничений на последующие пары.