» » Як вирішується завдання про 1000 пляшок?

Як вирішується завдання про 1000 пляшок?

Фото - Як вирішується завдання про 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 - якщо залишилася жива. Отримане число і буде двійковим номером отруєної пляшки.