Цепочка логических переменных
Сколько существует различных наборов значений логических переменных $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)$.
Условие как в банке ФИПИ — открыть и сверить
| Сколько существует различных наборов значений логических переменных x1, x2, ... x8, y1, y2, ... y8, которые удовлетворяют всем перечисленным ниже условиям?
(x1 \/ y1) ≡ (¬x2 /\ ¬y2) (x2 \/ y2) ≡ (¬x3 /\ ¬y3) … (x7 \/ y7) ≡ (¬x8 /\ ¬y8)
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ... x8, y1, y2, ... y8, при которых выполнена данная система равенств.
| |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Рассмотрите каждую пару $(x_i, y_i)$ как одно состояние. Сколько переходов возможно из состояния $(0,0)$ и из любого ненулевого состояния?
2Наводящая — какие числа считатьуровень 2 из 3
Если $x_i \lor y_i = 1$, то следующая пара обязана быть $(0,0)$. Если $x_i \lor y_i = 0$, следующая пара не может быть $(0,0)$.
3Прямая — фактически решениеуровень 3 из 3
Пусть $A_n$ — число цепочек длины $n$, заканчивающихся парой $(0,0)$, а $B_n$ — числом цепочек, заканчивающихся одной из трёх ненулевых пар. Тогда $A_{n+1}=B_n$, $B_{n+1}=3A_n$, начиная с $A_1=1$, $B_1=3$.