Шешімі: Цепочка логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_8, y_1, y_2, \ldots, y_8$, которые удовлетворяют всем условиям:
$(x_1 \lor y_1) \equiv (\lnot x_2 \land \lnot y_2)$;
$(x_2 \lor y_2) \equiv (\lnot x_3 \land \lnot y_3)$;
$\ldots$
$(x_7 \lor y_7) \equiv (\lnot x_8 \land \lnot y_8)$.
Шешім по шагам
7 қадамОбозначим пару $(x_i,y_i)$ состоянием. Всего возможны четыре состояния: $(0,0)$ и три ненулевых состояния.
Если текущая пара ненулевая, то $x_i \lor y_i=1$. Правая часть следующего равенства должна быть равна 1, поэтому следующая пара единственным образом равна $(0,0)$.
Если текущая пара равна $(0,0)$, то $x_i \lor y_i=0$. Правая часть должна быть равна 0, поэтому следующая пара может быть любой из трёх ненулевых состояний.
Пусть $A_n$ — число цепочек длины $n$, заканчивающихся состоянием $(0,0)$, а $B_n$ — число цепочек, заканчивающихся ненулевым состоянием. Для одной пары $A_1=1$, $B_1=3$.
Переходы между состояниями задаются соотношениями:
$$A_{n+1}=B_n,\quad B_{n+1}=3A_n$$Последовательно получаем:
$$(A_1,B_1)=(1,3),\ (A_2,B_2)=(3,3),\ (A_3,B_3)=(3,9),\ (A_4,B_4)=(9,9),\ (A_5,B_5)=(9,27),\ (A_6,B_6)=(27,27),\ (A_7,B_7)=(27,81),\ (A_8,B_8)=(81,81)$$Общее количество цепочек длины 8 равно сумме числа цепочек обоих типов.
$$A_8+B_8=81+81=162$$Где здесь ошибаются
Считать, что из состояния $(0,0)$ доступны все төрт следующие пары.
Забыть, что из ненулевого состояния следующая пара определяется единственным образом.
Учитывать только цепочки, заканчивающиеся состоянием $(0,0)$.