Задача о 1000 бутылок
Шерлок Холмс развалился на диване и простреливал на противоположной стене очередной вензель. Скрипка надоела, от химических опытов болела голова, табак для трубки закончился. Самое паскудное, давно не было интересных дел, как будто весь преступный мир Лондона в это лето дружно отправился в отпуск на континент. Поэтому он был приятно удивлён видом запыхавшегося инспектора Лейстрейда.
— Мистер Холмс, выручайте, срочное дело!
— У вас все дела срочные, — валял дукрака Холмс, прикидывая, что могло приключиться на этот раз…
— Государственное!
— У вас все дела государственные…
— Но речь идёт о жизни Её величества!
Кот на кушетке навострил уши. Холмс тоже бы так сделал, если бы мог.
— А подробнее, инспектор?
Лейстрейд отдышался, выпил предложенный миссис Хадсон стакан воды и начал свой рассказ…
— Завтра, как Вы знаете, Королева устраивает Большой Благотворительный Вечер в Букингемском дворце. Приглашены именитые гости — послы, министры, члены обеих палат и прочий нобилитет. Одного вина французского 1845-го года урожая закуплена тысяча бутылок! А тут по нашим точным агентурным сведениям поступила информация, что одна из этих бутылок отравлена сильнейшим ядом! Он убивает в любой концентрации, даже 1/1000! Отменить Вечер никак нельзя, провести его без вина — немыслимо! Заменить вино — нечем. А главное, необходимо срочно найти именно ту самую отравленную бутылку, чтобы изучить её как следует — снять отпечатки
Холмс на секунду задумался.
— Так, 2 в десятой — тысяча двадцать четыре, — невнятно пробормотал знаменитый сыщик. Ну конечно, вот что надо сделать!
— Это гениально, Холмс, — воскликнул Ватсон.
— Это элементарно, Ватсон, — скромно пробасил Холмс.
Лейстрейд побежал срочно выполнять полученную инструкцию.
Что же сказал ему Холмс?
Прежде чем читать дальше, попробуйте решить задачу сами!
Решение
Вот что сказал инспектору Холмс…
Пронумеруйте каждую мышь, возьмите 10 стаканов и пронумеруйте их тоже. Далее пронумеруйте каждую бутылку, но не обычными числами, а… ДВОИЧНЫМИ. Поскольку 2 в 10 степени равно 1024, то вам понадобится для этого не более 10 разрядов. Далее каждую бутылку разливаем в каждый из стаканов по следующему правилу:
В стакан номер N наливаем из некоторой бутылки, если N-й разряд в её двоичном номере равен 1, и не наливаем, если он равен 0.
Например, из бутылки номер 3 наливаем немного вина только в 1-й и 2-й стакан, т.к. двоичная запись числа 3 будет 0000000011.
Полученные коктейли даём попробовать мышам с соответствующим номером. Через сутки некоторые мыши умрут. Теперь составим двоичное число, где N-й разряд равен 1, если мышь номер N умерла, и 0 — если осталась жива. Полученное число и будет двоичным номером отравленной бутылки.