Подбор ключей

[grizzly]

(По мотивам обсуждавшейся недавно детской задачи.)
Пусть будет $N$ чемоданов и $N$ ключей и папа с мамой. За одну попытку папа может дать маме на проверку любые $k \le N$ чемоданов и $k$ ключей и получить в ответ количество совпадений. Какое минимальное количество попыток потребуется папе, чтобы наверняка подобрать все ключи.

[wrest]

grizzly
Нужна уточнения. Совпавшие из игры выбывают?
И что значит "получить в ответ количество совпадений"? Например есть 10 чемоданов и 10 ключей. Даем маме по 10 того и другого, мама пробует каждый даденый ей ключ к каждому чемодану или что?

[grizzly]

wrest в сообщении #1327800 писал(а):

Совпавшие из игры выбывают?

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

wrest в сообщении #1327800 писал(а):

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

Ну, например, так. Или у неё список есть. Это не важно. Важно, что Вы для этой попытки гарантированно получите число 10 в ответе (если $N=10$). По условию полный набор ключей соответствует набору чемоданов.

[Naf2000]

хочется верить что
$\left\lfloor\log_2N!\right\rfloor+1$ при $N>2$

[worm2]

Naf2000, а почему логарифм по основанию 2? В этой задаче возможно получить до $n_{\max}=\left\lfloor N/2+1\right\rfloor$ различных вариантов на один запрос, так что в грубой теоретической оценке снизу можно поставить $n_{\max}$ вместо двойки.