2014 dxdy logo

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

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




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

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

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

 
 
 
 
Сообщение31.03.2011, 13:18 
Аватара пользователя
Нумеруем всех подозреваемых 2011-значным номером. На шаге i опрашиваем тех, чей номер в i-том разряде содержит единицу. При ответе "да" ставим в этот разряд 1, иначе 0. После 2011 вопросов читаем номер преступника.

 
 
 
 Re:
Сообщение31.03.2011, 13:29 
Евгений Машеров в сообщении #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