РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 7593 Добавить в вариант

Даны множества:

$X_1= левая фигурная скобка 1, 6, 9 правая фигурная скобка ,$ $X_2= левая фигурная скобка 2,7 правая фигурная скобка ,$ $X_3= левая фигурная скобка 2, 3, 4, 5, 6, 7, 9 правая фигурная скобка ,$ $X_4= левая фигурная скобка 2, 3, 4, 6, 9 правая фигурная скобка ,$ $X_5= левая фигурная скобка 1, 2, 3, 5, 6, 7, 8, 9 правая фигурная скобка ,$ $X_6= левая фигурная скобка 1, 2, 6, 7, 8, 9 правая фигурная скобка ,$ $X_7= левая фигурная скобка 7, 9 правая фигурная скобка ,$ $X_8= левая фигурная скобка 2, 6, 7, 8 правая фигурная скобка ,$ $X_9= левая фигурная скобка 2, 9 правая фигурная скобка .$

Сколько существует наборов различных цифр (a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈, a₉) таких, что $a_i принадлежит X_i?$ Предъявите все эти наборы.

Спрятать решение

Решение.

Комментарий.

Пусть задано семейство подмножеств X₁, X₂, ..., X_n множества $A= левая фигурная скобка x_1, x_2, \ldots, x_m правая фигурная скобка ,$ тогда упорядоченный набор $левая круглая скобка a_1, \ldots, a_n правая круглая скобка ,$ в котором все элементы различны и $a_i принадлежит X_i,$ $i=1, \ldots, n,$ называется трансверсалью или системой различных представителей данного семейства множеств. Как видно из условия, в данной задаче требуется найти все трансверсали семейства множеств X₁, ..., X₉.

Понятие трансверсали семейства множеств связано с понятием матрицы инцидентности семейства множеств. Пусть задано семейство подмножеств X₁, X₂, ..., X_n множества $A= левая фигурная скобка x_1, x_2, \ldots, x_m правая фигурная скобка ,$ тогда матрицей инцидентности данного семейства называется таблица, имеющая n строк и m столбцов, состоящая из нулей и единиц вида:

где $b_i j=1$ только если $x_j принадлежит X_i$ и $b_i j=0$   — в противном случае. Упорядоченный набор элементов $левая круглая скобка b_1 j_1, \ldots, b_n j_n правая круглая скобка ,$ равных 1, в котором элементы лежат в разных столбцах, называется трансверсалью матрицы инцидентности. Нетрудно понять, что число трансверсалей семейства множеств X₁, X₂, ..., X_n равно числу трансверсалей матрицы инцидентности данного семейства.

Перейдем к решению.

Запишем матрицу инцидентности $B= левая круглая скобка b_i j правая круглая скобка ,$ $i=1, \ldots, 9 ;$ $j=1, \ldots, 9$ всех цифр множеств $X_i:$ То есть, $b_i j=1,$ если $j принадлежит X_i,$ и $b_i j=0$ в противном случае. В этой матрице нам необходимо найти все наборы (трансверсали) вида $b_1 j_1,$ ..., $b_9 j_9,$ где j₁, ..., j₉  — некоторая перестановка цифр 1, 2, ..., 9, и все $b_i j_k=1,$ $i=1, \ldots, 9 ;$ $k=1, \ldots, 9.$ Иными словами мы ищем такие наборы из 9 единиц, что все единицы одного набора лежат в разных строках и разных столбцах. Для облегчения поиска переставим в матрице B строки и столбцы (в целом, строки с меньшим количеством 1 ставим выше, а столбцы с большим количеством 1  — левее). Результат приведен на правом рисунке.

Поскольку единицы надо выбирать из разных строк и столбцов, сначала следует выбирать 1 из отмеченной пунктиром матрицы 3 на 3. В ней две трансверсали. Затем выбираем трансверсали в двух отмеченных прямоугольником матрицах 3 на 3. В каждой из них по 3 трансверсали. Значит, всего 18 трансверсалей.

Ответ: 18 наборов. Пример:

$левая круглая скобка 1, 2, 3, 4, 5, 6, 7, 8, 9 правая круглая скобка ,$ $левая круглая скобка 1, 2, 3, 4, 5, 8, 7, 6, 9 правая круглая скобка ,$ $левая круглая скобка 1, 2, 4, 3, 5, 6, 7, 8, 9 правая круглая скобка ,$ $левая круглая скобка 1, 2, 4, 3, 5, 8, 7, 6, 9 правая круглая скобка$ $левая круглая скобка 1, 2, 5, 4, 3, 6, 7, 8, 9 правая круглая скобка ,$ $левая круглая скобка 1, 2, 5, 4, 3, 8, 7, 6, 9 правая круглая скобка ,$ $левая круглая скобка 1, 7, 3, 4, 5, 6, 9, 8, 2 правая круглая скобка ,$ $левая круглая скобка 1, 7, 3, 4, 5, 8, 9, 6, 2 правая круглая скобка$ $левая круглая скобка 1, 7, 4, 3, 5, 6, 9, 8, 2 правая круглая скобка ,$ $левая круглая скобка 1, 7, 4, 3, 5, 8, 9, 6, 2 правая круглая скобка ,$ $левая круглая скобка 1, 7, 5, 4, 3, 6, 9, 8, 2 правая круглая скобка ,$ $левая круглая скобка 1, 7, 5, 4, 3, 8, 9, 6, 2 правая круглая скобка$ $левая круглая скобка 6, 2, 3, 4, 5, 1, 7, 8, 9 правая круглая скобка ,$ $левая круглая скобка 6, 2, 4, 3, 5, 1, 7, 8, 9 правая круглая скобка ,$ $левая круглая скобка 6, 2, 5, 4, 3, 1, 7, 8, 9 правая круглая скобка ,$ $левая круглая скобка 6, 7, 3, 4, 5, 1, 9, 8, 2 правая круглая скобка$ $левая круглая скобка 6, 7, 4, 3, 5, 1, 9, 8, 2 правая круглая скобка ,$ $левая круглая скобка 6, 7, 5, 4, 3, 1, 9, 8, 2 правая круглая скобка .$