2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 10:42 
Аватара пользователя
Здравствуйте!
Оргкомитет олимпиады состоит из 11 человек. Материалы олимпиады хранятся в сейфе. Сколько замков должен иметь сейф и сколькими ключами следует снабдить каждого лена оргкомитета, чтобы доступ в сейф был возможен, если соберутся любые 6 членов оргкомитета, и не был возможен, если соберутся меньше 6 членов.
Подскажите пожалуйста как ее решать?

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 11:09 
Аватара пользователя
Решите сначала задачу попроще. Сколько замков надо повесить и сколько ключей раздать, чтобы любые два могли открыть сейф, а в одиночку нет?

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 13:11 
Аватара пользователя
Хорхе
Мне даже ваша подсказка не помогла =(

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 13:16 
Аватара пользователя
Тогда уменьшите количество членов до двух :-)
Ну это не интересно. До трёх. Три человека. Сколько нужно замков и как раздать ключи, чтобы любые два открыли, а один нет.

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 13:48 
(Можно тоже порешать?)
$\{\{1, 2, 3\}, \{1, 2, 4\}, \{3, 4\}\}$? Симметричного ли меньшеключно-замочного пока не выдумал.

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

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 14:04 

(Оффтоп)

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

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 17:13 
Аватара пользователя
Уважаемый Хорхе честно скажу я даже такую упрощенную задачу не знаю как решить.

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 17:21 
Аватара пользователя
Whitaker в сообщении #481854 писал(а):
Уважаемый Хорхе честно скажу я даже такую упрощенную задачу не знаю как решить.

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

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 17:45 
Аватара пользователя
Вот допустим, что у нас только 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 ключа?

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 17:59 
Аватара пользователя
Whitaker в сообщении #481861 писал(а):
А почему нельзя каждому из них дать по 3 ключа?

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

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

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 22:33 
Аватара пользователя
Да

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение09.09.2011, 23:11 
Аватара пользователя
Whitaker в сообщении #481965 писал(а):
Да

Что - "Да" ?

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение10.09.2011, 07:51 
Аватара пользователя
Хотелось бы для начала решить упрощенную задачу, которую дал Хорхе, но пока не знаю как его делать.

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение10.09.2011, 07:53 
Аватара пользователя
Вам же уже дали решение. И на вопрос ответили. В чем затруднения?

 
 
 
 Re: Задача о сейфе [Комбинаторика]
Сообщение10.09.2011, 13:15 
Аватара пользователя
С матрицами, уже даже можно о чем-то думать )

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

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group