28.6.Ещё пример задания

Сколько различных решений имеет система уравнений

X₁  X₂  X₃ = 1

X₂  X₃  X₄ = 1

...

X₈  X₉  X₁₀ = 1

где x₁, x₂, …, x₁₀ – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение (последовательное подключение уравнений):

1. рассмотрим сначала все решения первого уравнения; его левая части истинна, когда X₁=1 (при этом X₂ и X₃ могут быть любыми), а также когда X₁=0 и X₂=X₃=1:

   X1	X2	X3
   0	1	1
   1	0	0
   1	0	1
   1	1	0
   1	1	1

2. заметим, что первое и второе уравнения связаны через последние две переменных, в данном случае это X₂ и X₃

3. пусть i – число переменных в уравнениях; введем обозначения:

K_i – количество решений, в которых последние две переменные принимают
значения (0,0)

L_i – количество решений, в которых последние две переменные принимают
значения (0,1)

M_i – количество решений, в которых последние две переменные принимают
значения (1,0)

N_i – количество решений, в которых последние две переменные принимают
значения (1,1)

1. из таблицы видим, что K₃=1, L₃=1, M₃=1 и N₃=2

2. теперь подключаем второе уравнение; посмотрим, к чему приводят разные комбинации последних двух переменных:

   X1	X2	X3	X4
   0	1	1	0
   			1
   1	0	0	×
   1	0	1	1
   1	1	0	0
   			1
   1	1	1	0
   			1

3. находим, что
   комбинация (0,0) не дает ни одного решения,
   комбинация (0,1) дает одно решение, и при этом (X₃,X₄)=(1,1)

комбинация (1,0) дает два решения, причем (X₃,X₄)=(0,0) или (0,1)

комбинация (1,1) дает два решения, причем (X₃,X₄)=(1,0) или (1,1)

1. из предыдущего пункта делаем вывод, что

K_i+1 = M_i (комбинация (0,0) появилась из (1,0) на предыдущем шаге)

L_i+1 = M_i (комбинация (0,1) появилась из (1,0) на предыдущем шаге)

M_i+1 = N_i (комбинация (1,0) появилась из (1,1) на предыдущем шаге)

N_i+1 = L_i+N_i (комбинация (1,1) появляется из (0,1) и (1,1))

1. используя эти рекуррентные формулы, заполняем таблицу для i=4,…,10

   i	Ki	Li	Mi	Ni	Всего
   3	1	1	1	2	5
   4	1	1	2	3	7
   5	2	2	3	4	11
   6	3	3	4	6	16
   7	4	4	6	9	23
   8	6	6	9	13	34
   9	9	9	13	19	50
   10	13	13	19	28	73

2. таким образом, ответ: 13 + 13 + 19 + 28 = 73 решения.

Решение (метод отображений¹, решение А.Н. Носкина):

1. построим таблицу, в которой переберем все варианты x₁, x₂, x₃, поскольку в первом логическом уравнении три переменных, то таблица будет иметь 8 строк (8 = 2³); уберем из таблицы (желтая заливка) такие значения x₂ и x₃, при которых первое уравнение не имеет решения.

1. анализируя таблицу, строим правило отображения пар переменных

(например, паре x₁x₂ = 00 не соответствуют ни одной пары x₂x₃ , и наоборот паре x₁x₂ = 01 соответствует только пара x₃x₄ = 11).

1. Заполняем таблицу, вычисляя количество пар переменных, при котором система имеет решение.

1. таким образом, ответ: 13 + 13 + 19 + 28 = 73 решения.

1^ Метод отображений предложен Ел.А. Мирончик и Ек.А. Мирончик (http://kpolyakov.spb.ru/download/b15mirn.zip).