Задача о сейфе [Комбинаторика]

[Whitaker]

ИС в сообщении #482065 писал(а):

С матрицами, уже даже можно о чем-то думать )

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

Согласен матрица намного упрощают задачу
К сожалению ответ не таков.

[Sender]

Пусть ключи есть у n человек, причём для достуа к сейфу требуется участие любых m+1 из них. Можно рассуждать следующим образом:
Рассмотрим произвольную группу A из m человек и одного произвольного человека из числа оставшихся n-m (назовём их группой B). A не сможет открыть сейф, как бы ни пыталась; в то же время, объединив усилия с этим одним, она с лёгкостью справится с задачей. Значит, у него есть как минимум один ключ, которого нет у группы A. Заметим, что этот же ключ есть у всех представителей группы B.
Дальше, по-моему, всё очевидно.

[PAV]

Примерно в том же духе, но немного другими словами, решение можно написать так. Для любых шести столбцов в каждой строчке должна быть хотя бы одна единица; легко понять, что это условие нарушается тогда и только тогда, когда хотя бы одна строчка матрицы содержит шесть или более нулей. Отсюда следует, что матрицу можно составлять только из строчек, имеющих не более 5 нулей, и это гарантирует выполнение данной части условия.
Далее, любые пять человек не могут открыть сейф - это означает, что для любых пяти столбцов должна существовать строчка, в которой в этих столбцах стоят нули. В силу предыдущего условия остальные элементы в этой строчке должны быть единицами. Таким образом, матрица должна содержать все строки, имеющие ровно 5 нулей. Соответственно, требуемая в задаче минимальная матрица состоит только из этих строк, число которых равно $C_{11}^5$

[Whitaker]

PAV в сообщении #482389 писал(а):

Примерно в том же духе, но немного другими словами, решение можно написать так. Для любых шести столбцов в каждой строчке должна быть хотя бы одна единица; легко понять, что это условие нарушается тогда и только тогда, когда хотя бы одна строчка матрицы содержит шесть или более нулей. Отсюда следует, что матрицу можно составлять только из строчек, имеющих не более 5 нулей, и это гарантирует выполнение данной части условия.
Далее, любые пять человек не могут открыть сейф - это означает, что для любых пяти столбцов должна существовать строчка, в которой в этих столбцах стоят нули. В силу предыдущего условия остальные элементы в этой строчке должны быть единицами. Таким образом, матрица должна содержать все строки, имеющие ровно 5 нулей. Соответственно, требуемая в задаче минимальная матрица состоит только из этих строк, число которых равно $C_{11}^5$

Ведь в матрице может быть 8 нулей и 3 единицы?

[PAV]

3 смогут открыть замок, а 8 не смогут. Восемь. Не смогут. Ни вместе, ни по отдельности.