Дискретная математика. Комбинаторика. Ерош И.Л. - 22 стр.

UptoLike

Составители: 

22
Легко заметить, что каждый столбец содержит 6 единиц и 4 нуля.
Кроме того, если взять любые два столбца и поставить их рядом, то
всегда найдется комбинация 00. Если же взять три любых столбца, то
комбинации 000 не будет.
Если теперь считать номера строк 1), 2), …, 10) номерами ключей, а
каждый столбец рассматривать как способ выдачи ключей конкретно-
му члену комиссии, то мы получим решение поставленной задачи при 5
членах комиссии и пороговом значении h = 3. Если теперь построить
таблицу кодов длины 7 веса 4, мы получим решение исходной задачи.
Полученное решение легко обобщить на произвольное число членов
комиссии n и произвольный порог h. Действительно, если построить таб-
лицу равновесных кодов длины n веса k, то число ключей будет равно
P(n, n – k) = n!/ ((n – k)!k!), а сейф может быть открыт, если соберется
число членов комиссии равное h = n k + 1.
Так, например, пусть n = 4, h = 3, т. е. число членов комиссии равно 4,
а сейф должен открываться, если соберется не менее 3 членов комис-
сии. В общем случае k = n h + 1.
Для конкретного примера k = 4 – 3 + 1 = 2; т. е. нужно построить
таблицу равновесных кодов длины 4 веса 2:
1) 1 1 0 0
2) 1 0 1 0
3) 1 0 0 1
4) 0 1 1 0
5) 0 1 0 1
6) 0 0 1 1
Из таблицы видно, что сейф должен иметь в этом случае 6 замков, а
ключи должны распределяться в соответствии с таблицей равновесных
кодов, т. е. первый член комиссии (первый столбец) получает 1, 2 и 3
ключ, второй член комиссии получает 1, 4 и 5 ключ, третий член комис-
сии получает 2, 4 и 6 ключ и четвертый член комиссии получает 3, 5 и 6
ключ.
1.16. Раскладка предметов в несколько ящиков
Рассмотрим следующую задачу. Трое мальчиков собрали 40 яблок.
Сколько имеется способов раздела яблок между ними?
Напишем 40 единиц и 2 нуля, выполняющих как и ранее функции раз-
делителя, и затем начнем их переставлять всеми возможными спосо-