Задание 23. Пример из открытого банка заданий ФИПИ

1. Условие задачи.

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

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

            2. Набросок решения.  

Решение состоит из двух этапов. Сначала попытаемся описать, как устроены все наборы значений переменных, удовлетворяющие данной системе. Далее   подсчитаем число таких наборов.

            2.1. Как устроено множество решений

А. Предварительный этап – упрощаем уравнения.

Заметим, что выражение (a \/ b) /\ (¬a \/ ¬b) равносильно тому, что ровно одна из переменных a и b равна 1, то есть равносильно выражению ¬(a ≡ b). Поэтому каждое выражение вида

(x_k \/ x_k+2) /\ (¬x_k \/ ¬x_k+2),

где k=1, …, 8, в наших уравнениях можно заменить выражением  

 ¬(x_k ≡ x_k+2).

Таким образом, наша система эквивалентна системе

Далее,  ¬a  /\  ¬b = 0 означает, что, если  ¬a   истинно, то ¬b  истинным быть не может. Т.е. ¬a  /\  ¬b = 0 эквивалентно ¬a  → b = 1.

Поэтому систему можно записать в следующем виде

          Б. Анализ системы.

Каждое из уравнений полученной системы имеет вид (k = 1, …, 8):

¬(x_k ≡ x_k+1)  → (x_k ≡ x_k+2) =1

            Иными словами, если два соседних элемента набора x_k и x_k+1 не равны между собой, то x_k=x_k+2, то есть элементы x_k+1 и x_k+2 также не равны между собой. Таким образом, набор удовлетворяет системе, тогда и только тогда, когда он обладает следующими свойствами.

В начале набора стоит несколько (может быть, одно) одинаковых значений (назовем это"головой" набора). Затем (после первого появления нового числа) значения в наборе чередуются ("хвост" набора).

Пример решения: 1111010101 (в  этой последовательности первая цифра – значение переменной x₁, вторая цифра – значение переменной x₂, и т.д.). Здесь голова набора состоит из четырех единиц, а хвост – это последовательность  01010101. в данном примере длина головы равна 4.

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

            2.2. Подсчет количества решений

В соответствии с важным наблюдением, количество решений совпадает с количеством возможных голов. Очевидно, существует 10 голов, состоящих из единиц (1, 11, 111, …, 1111111111) и столько же голов, состоящих из нулей.

Ответ: 20.

Замечание. Как видим, сложность решения задачи не зависит от числа переменных и уравнений. Если понятно, как устроено множество решений, подсчитать количество решений для аналогичной системы, скажем, с 20-ю переменными, не сложнее, чем в уже рассмотренном случае.