Виктор Губерниев Мастер

Как решается задача о 1000 бутылок?

Эту задачу прислал мне один мой знакомый, сообщив, что подобные задачи любят давать на собеседованиях при приёме на работу. Задача показалась мне настолько интересной, что я придумал для неё красивый конан-дойловский антураж и предложил читателям. В этой статье я предлагаю своё решение задачи, но перед тем, как прочесть его, предлагаю всё-таки решить задачу самостоятельно. Задача невероятно красивая и стоит того, чтобы день-другой поломать голову.

ostill , Shutterstock.com

Задача о 1000 бутылок

Шерлок Холмс развалился на диване и простреливал на противоположной стене очередной вензель. Скрипка надоела, от химических опытов болела голова, табак для трубки закончился. Самое паскудное, давно не было интересных дел, как будто весь преступный мир Лондона в это лето дружно отправился в отпуск на континент. Поэтому он был приятно удивлён видом запыхавшегося инспектора Лейстрейда.

 — Мистер Холмс, выручайте, срочное дело!

 — У вас все дела срочные, — валял дукрака Холмс, прикидывая, что могло приключиться на этот раз…

 — Государственное!

 — У вас все дела государственные…

 — Но речь идёт о жизни Её величества!

Кот на кушетке навострил уши. Холмс тоже бы так сделал, если бы мог.

 — А подробнее, инспектор?

Лейстрейд отдышался, выпил предложенный миссис Хадсон стакан воды и начал свой рассказ…

 — Завтра, как Вы знаете, Королева устраивает Большой Благотворительный Вечер в Букингемском дворце. Приглашены именитые гости — послы, министры, члены обеих палат и прочий нобилитет. Одного вина французского 1845-го года урожая закуплена тысяча бутылок! А тут по нашим точным агентурным сведениям поступила информация, что одна из этих бутылок отравлена сильнейшим ядом! Он убивает в любой концентрации, даже 1/1000! Отменить Вечер никак нельзя, провести его без вина — немыслимо! Заменить вино — нечем. А главное, необходимо срочно найти именно ту самую отравленную бутылку, чтобы изучить её как следует — снять отпечатки и т. п. Дело осложняется тем, что яд этот действует не сразу, а в течение суток, и как раз сутки остались до Мероприятия! Для тестирования у нас всего 10 лабораторных мышей, и других нам так срочно взять негде. Помогите, Холмс, на вас вся наша надежда!

Холмс на секунду задумался.

 — Так, 2 в десятой — тысяча двадцать четыре, — невнятно пробормотал знаменитый сыщик. Ну конечно, вот что надо сделать!

 — Это гениально, Холмс, — воскликнул Ватсон.

 — Это элементарно, Ватсон, — скромно пробасил Холмс.

Лейстрейд побежал срочно выполнять полученную инструкцию.

Что же сказал ему Холмс?

Прежде чем читать дальше, попробуйте решить задачу сами!

Решение

Вот что сказал инспектору Холмс…

Пронумеруйте каждую мышь, возьмите 10 стаканов и пронумеруйте их тоже. Далее пронумеруйте каждую бутылку, но не обычными числами, а… ДВОИЧНЫМИ. Поскольку 2 в 10 степени равно 1024, то вам понадобится для этого не более 10 разрядов. Далее каждую бутылку разливаем в каждый из стаканов по следующему правилу:

В стакан номер N наливаем из некоторой бутылки, если N-й разряд в её двоичном номере равен 1, и не наливаем, если он равен 0.

Например, из бутылки номер 3 наливаем немного вина только в 1-й и 2-й стакан, т.к. двоичная запись числа 3 будет 0000000011.

Полученные коктейли даём попробовать мышам с соответствующим номером. Через сутки некоторые мыши умрут. Теперь составим двоичное число, где N-й разряд равен 1, если мышь номер N умерла, и 0 — если осталась жива. Полученное число и будет двоичным номером отравленной бутылки.

Статья размещена на сайте 4.12.2014

Комментарии (14):

Чтобы оставить комментарий зарегистрируйтесь или войдите на сайт

Войти через социальные сети:

  • Инфа 100% смотрите скриншот:

  • Улыбнуло: автор и сам оценил свое спорное творение высшим баллом. Виктор, можете добавить к своим прекрасным качествам и хобби в обширном вашем перечне саморекламы и этот момент.

  • Мне кажется или здесь используется принцип нейронных сетей? Получается поток входной информации, вернее его обработка ускоряется в сотни раз. Что-то подобное приходилось слышать о зрении

    Оценка статьи: 5

  • Увы! Это я недосмотрела! (((

    Оценка статьи: 2

  • А не проще ли сделать так:
    Взять 10 стаканчиков. В каждый капнуть по капельке из 100 бутылок.
    Сдохнет 1 мышка.
    Взять 100 бутылок, из которых 1 отравленная, и 9 новых стаканчиков. В каждый из 8 ст. накапать из 11 бутылок (8х11=88). И в один - из 12 бут. (88+12=100). 2-я мышка сдохнет.
    Взять 11 (или 12) бутылок, из которых 1 отравленная, и 8 стаканчиков. В 5(4) ст. капнуть из 1 бутылки. Еще в 3(4) из 2-х (3х2=6 или 4х2=8). 5(4)+6(8)= 11(12). 3-я мышка сдохнет.
    Если мышка пробовала из стаканчика, в которую налили из одной бутылки, ее выбросить.
    Если мышка выпила из ст., в которую налили из двух бутылок, провести еще один тур в 2 стаканчика.

    Максимальная смертность среди мышек - 4. Оптимальная -3. И высшая математика не нужна!

    Оценка статьи: 2

    • Лариса Шеенко, нет, не проще. Ведь в условии задачи сказано:

      Дело осложняется тем, что яд этот действует не сразу, а в течение суток, и как раз сутки остались до Мероприятия!

      Т.е. пробовать можно только один раз и на всех мышках сразу!

      Оценка статьи: 5

  • Ни фига не понял, ибо слаб в математике.
    Но всё равно - КРАСИВО!

    Оценка статьи: 5

  • Интересная задачка. Но помоему мыши сдохнут все от алкогольного отравления раньше чем от яда))

    Оценка статьи: 5

  • Браво! Шерлока Холмса ждет следующая задачка по информатике.

    Оценка статьи: 5