December 1
Решение. Ключи от сейфа (#153)
Обозначим число членов комиссии n=11 и рассмотрим все группы по k=5 человек. Их число равно Cᵏₙ. Каждой такой группе не хватает некоторого набора ключей для открытия всех замков. Эти наборы попарно не пересекаются, поскольку иначе, объединив две группы с общими наборами, мы получили бы группу из ≥ k+1 = 6 человек, которая также не смогла бы открыть все замки. Следовательно, число замков не может быть меньше числа наборов ключей, которых, как и групп, имеется Cᵏₙ.
Теперь навесим на сейф в точности Cᵏₙ замков, ключи же раздадим следующим образом. Перенумеруем группы из k=5 человек от 1 до Cᵏₙ и членам комиссии, не попавшим в группу под номером i, раздадим ключи от замка i. Тогда ясно, что
- группа из k=5 человек, соответствующая номеру i, не сможет открыть замок с номером i
- группа из ≥ k+1 = 6 человек сможет открыть все замки, так как в этой группе всегда найдётся человек, не входящий в какую-либо группу из k=5 человек