2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Замки и ключи
Сообщение10.03.2016, 23:04 
Аватара пользователя


05/08/11
36
Калининград
Есть задача, которая уже долгое время не дает мне покоя, я даже начинаю сомневаться в том, что у нее есть решение. Звучит она следующим образом:
Дверь закрыта на несколько замков. У каждого из $M $ человек есть несколько ключей, притом никакие $N$ человек не могут открыть дверь, а любые $ N+1$ человек могут. Найдите наименьшее количество замков, на которые закрыта дверь и определите количество ключей у каждого человека.
Кажется, что тут нужно каким-то образом использовать принцип Дирихле, но ума не приложу как именно.

 Профиль  
                  
 
 Re: Замки и ключи
Сообщение10.03.2016, 23:53 
Заслуженный участник


10/01/16
2318
Рассмотрим каких-либо $N$ чел. У них нет ключа от некоторого замка (а у всех остальных он есть!). Поставим в соответствие нашей компании этот замок. Разным компаниям ставится в соответствие разные замки. Значит, замков не менее $C_M^N$ штук.
Покажем, что стоко замков хватит. Для этого занумеруем замки наборами из $N$ чел. Ключ от замка дадим тем людям, кто не входит в номер этого замка. Тогда: любой компании из $N$ чел не хватит одного ключа, а в любой компании из $N+1$ чел есть ключи от всех...

 Профиль  
                  
 
 Re: Замки и ключи
Сообщение16.03.2016, 20:43 


08/09/13
210

(Оффтоп)

В 21 веке можно и без ключиков. Схема Шамира в помощь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: DariaRychenkova


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group