2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Кто украл алмаз?
Сообщение31.03.2011, 13:01 


01/10/10

2116
Израиль (племянница БизиБивера)
Перед Шерлоком Холмсом выстроились $2^{2011}$ подозреваемых в краже алмаза.
Холмс достоверно знает, что ровно один из подозреваемых совершил эту кражу.
Каждый из подозреваемых достоверно знает, кто совершил кражу, но боится назвать вора (в том числе и сам вор боится назвать себя).
Холмс может выбрать любое подмножество подозреваемых, содержащее более одного элемента, и спросить, есть ли среди них тот, кто украл алмаз. На этот вопрос Холмсу всегда ответят правду.

Великий Сыщик уже собрался было "раскусить" вора за 2011 вопросов, да вот беда, Холмс пообещал Доктору Ватсону, что опрашиваемые множества ему (Холмсу) придётся выбирать заранее, то бишь, нельзя в зависимости от предыдущих ответов менять план допроса. Если Холмс не сдержит обещание, он проспорит Ватсону бутылку отменного шотландского виски.

Помогите Холмсу!

 Профиль  
                  
 
 
Сообщение31.03.2011, 13:18 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва
Нумеруем всех подозреваемых 2011-значным номером. На шаге i опрашиваем тех, чей номер в i-том разряде содержит единицу. При ответе "да" ставим в этот разряд 1, иначе 0. После 2011 вопросов читаем номер преступника.

 Профиль  
                  
 
 Re:
Сообщение31.03.2011, 13:29 


01/10/10

2116
Израиль (племянница БизиБивера)
Евгений Машеров в сообщении #429473 писал(а):
Нумеруем всех подозреваемых 2011-значным номером. На шаге i опрашиваем тех, чей номер в i-том разряде содержит единицу. При ответе "да" ставим в этот разряд 1, иначе 0. После 2011 вопросов читаем номер преступника.

Тоже вариант.

У меня так было:

Берём 2011-мерный куб с единичной стороной и располагаем всех подозреваемых в его вершинах. Допросим 2011 попарно взаимно перпендикулярных 2010-мерных граней, это будут множества ${(0, x_1, x_2, \dots ,x_{2010})}, {(x_0, 0, x_2, \dots , x_{2010})}, {(x_0, x_1, 0, \dots ,x_{2010})}, \dots , {(x_0, x_1, x_2, \dots , 0)}$
В принципе, сводится к Вашему варианту.

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

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



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

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


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

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