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