Задача 60384

Темы:    [ Сочетания и размещения ] [ Криптография ]

Сложность: 3+ Классы: 8,9 Название задачи: Ключи от сейфа.

Условие

Международная комиссия состоит из девяти человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее шести членов комиссии?

Решение

По условию, любые пять человек сейф открыть не могут. Значит, у них нет ключа от некоторого замка. При этом любой другой член комиссии должен этот ключ иметь. Поэтому нужно поставить    замков. Четыре ключа от каждого замка отдаются некоторой четвёрке членов комиссии, причём разные ключи раздаются разным четвёркам.

Ответ

126 замков, по 4 ключа к каждому замку.

Замечания

Ср. с задачей 35166.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	2
Название	Комбинаторика
Тема	Комбинаторика
параграф
Номер	3
Название	Размещения, перестановки и сочетания
Тема	Классическая комбинаторика
задача
Номер	02.050