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