Решение задачи 483

Условие:

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

Решение:

Пронумеруем типы ключей и замков от 1 до n, ключ типа k открывает замок типа k и только его.

Рассмотрим ключ первого типа, он должен быть хотя бы у четверых людей, иначе, если он только у трех людей, то остальные шесть не смогут открыть сейф. Здесь возникает идея рассмотреть все возможные четверки людей. Их С(9, 4) = 126. Пронумеруем все четверки людей от 1 до 126.

Изготовим 126 типов замков и 126 типов ключей, каждого типа ключа по четыре штуки. Каждому человеку из первой четверки выдадим по ключу первого типа. Каждому человеку из второй четверки выдадим по ключу второго типа. И так далее.

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

Возьмем любые пять людей. Рассмотрим оставшихся четырех людей, они образуют какую-ту четверку, пусть у нее номер m. У каждого человека из этой четверки есть ключ типа m, и больше ни у кого нет таких ключей. Значит, эти пять человек не смогут открыть сейф, так как ни у кого из них нет ключа типа m.