2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Подбор ключей
Сообщение20.07.2018, 10:17 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Подбор ключей
Сообщение20.07.2018, 10:25 


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

 Профиль  
                  
 
 Re: Подбор ключей
Сообщение20.07.2018, 10:30 
Заслуженный участник
Аватара пользователя


09/09/14
6328
wrest в сообщении #1327800 писал(а):
Совпавшие из игры выбывают?
При каждой попытке Вы узнаёте только одно голое число, не более того. Чемоданы и ключи Вам возвращают в целости и сохранности.
wrest в сообщении #1327800 писал(а):
Например есть 10 чемоданов и 10 ключей. Даем маме по 10 того и другого, мама пробует каждый даденый ей ключ к каждому чемодану или что?
Ну, например, так. Или у неё список есть. Это не важно. Важно, что Вы для этой попытки гарантированно получите число 10 в ответе (если $N=10$). По условию полный набор ключей соответствует набору чемоданов.

 Профиль  
                  
 
 Re: Подбор ключей
Сообщение20.07.2018, 15:10 


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

 Профиль  
                  
 
 Re: Подбор ключей
Сообщение20.07.2018, 16:30 
Заслуженный участник
Аватара пользователя


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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