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

Задания

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

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

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

$X_1= левая фигурная скобка 1, 2, 3, 4, 5, 6, 7 правая фигурная скобка ,$ $X_2= левая фигурная скобка 2, 5 правая фигурная скобка ,$ $X_3= левая фигурная скобка 2, 3 правая фигурная скобка ,$ $X_4= левая фигурная скобка 1, 2, 3, 4, 5, 7, 8, 9 правая фигурная скобка ,$ $X_5= левая фигурная скобка 3, 5 правая фигурная скобка ,$ $X_6= левая фигурная скобка 1, 3, 5, 6, 7 правая фигурная скобка ,$ $X_7= левая фигурная скобка 2, 3, 5, 7, 8, 9 правая фигурная скобка ,$ $X_8= левая фигурная скобка 5, 7, 8 правая фигурная скобка ,$ $X_9= левая фигурная скобка 2, 3, 7, 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 столбцов, состоящая из нулей и единиц вида:

	x₁	$\ldots$	x_j	$\ldots$	x_m
X₁	b₁₁	$\ldots$	b_1j	$\ldots$	b_1m
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
X_i	b_i1	$\ldots$	b_ij	$\ldots$	b_im
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
X_n	b_n1	$\ldots$	b_nj	$\ldots$	b_nm

где $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₁, X₂, ..., X₉.

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

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

Ответ: 18 наборов:

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