Замки и ключи

[Alex Fox]

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

[DeBill]

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

[fractalon]

(Оффтоп)

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