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

[Whitaker]

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

[Хорхе]

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

[ИС]

Хорхе
Мне даже ваша подсказка не помогла =(

[gris]

Тогда уменьшите количество членов до двух
Ну это не интересно. До трёх. Три человека. Сколько нужно замков и как раздать ключи, чтобы любые два открыли, а один нет.

[arseniiv]

(Можно тоже порешать?)
$\{\{1, 2, 3\}, \{1, 2, 4\}, \{3, 4\}\}$? Симметричного ли меньшеключно-замочного пока не выдумал.

$\{\{1, 2\}, \{1, 3\}, \{2, 3\}\}$!

[Joker_vD]

(Оффтоп)

Можно поставить один кодовый замок и разделить секретную комбинацию

[Whitaker]

Уважаемый Хорхе честно скажу я даже такую упрощенную задачу не знаю как решить.

[Dan B-Yallay]

Whitaker в сообщении #481854 писал(а):

Уважаемый Хорхе честно скажу я даже такую упрощенную задачу не знаю как решить.

Вешаем три замкА {123} и раздаем ключи: -> (12) (23) (13)
P.S. Не заметил, что arseniiv уже написал решение.

[Whitaker]

Вот допустим, что у нас только 3 человека: $a_1, a_2, a_3$
Выбрать 2 из 3 можно сделать 3-я способами. Это $a_1a_2, a_2a_3, a_1a_3$.
А что дальше сделать я не понимаю вообще. Сколько могжет быть замков и сколько ключей у каждого из членов оргкомитета .... как найти их мне пока непонятно.

-- Пт сен 09, 2011 17:47:46 --

Dan B-Yallay в сообщении #481856 писал(а):

Whitaker в сообщении #481854 писал(а):

Уважаемый Хорхе честно скажу я даже такую упрощенную задачу не знаю как решить.

Вешаем три замкА {123} и раздаем ключи: -> (12) (23) (13)
P.S. Не заметил, что arseniiv уже написал решение.

Уважаемый Dan B-Yallay. А почему нельзя каждому из них дать по 3 ключа?

[PAV]

Whitaker в сообщении #481861 писал(а):

А почему нельзя каждому из них дать по 3 ключа?

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

В исходной задаче полезно рассмотреть двоичную матрицу, имеющую 11 столбцов и минимально возможное число строк. Условие задачи означает, что для любых 5 столбцов этой матрицы должна существовать строчка, в которой в этих столбцах все нули, а для любых 6 столбцов любая строчка матрицы должна содержать хотя бы одну единицу. Для начала нужно понять, какие строчки могут, а какие не могут содержаться в такой матрице.

[Whitaker]

Да

[Dan B-Yallay]

Whitaker в сообщении #481965 писал(а):

Да

Что - "Да" ?

[Whitaker]

Хотелось бы для начала решить упрощенную задачу, которую дал Хорхе, но пока не знаю как его делать.

[Dan B-Yallay]

Вам же уже дали решение. И на вопрос ответили. В чем затруднения?

[ИС]

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

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