vott.ru — Мне всегда нравились задачки, в которых решение кажется невозможным до тех пор, пока не узнаешь алгоритм, по которому ее можно решить. Вот одна из таких задач.
> В лаборатории есть 1000 пробирок, в одной из которых находится отравляющее вещество «новичек», а во всех остальных – безвредное вещество. Еще есть 10 подопытных лабораторных мышек. > Требуется: абсолютно точно узнать, в какой именно пробирке находится "новичок". > Задача проста? Ну тогда чтобы задача не казалась простой - вот Вам проблема: дело в том, что «новичок» не убивает мышку сразу! Дело в том, что мышка ГАРАНТИРОВАННО погибает от микроскопической дозы «новичка» только в течении примерно 20 часов (это уж самый-самый максимум), а в Вашем распоряжении есть всего 24 часа чтобы найти пробирку с ядом.
Так слишком просто.
Вот так бодрее:
1. Яд действует в течение суток. У нас есть 2 суток.
2. Мышей не 10, а 7.
3. Пробирок не 1000, а 2000.
Да, там хитрее. Блоки переменных размеров. Такие, что если сдохнет несколько мышей, то оставшихся мышей во второй день должно в точности хватить на оставшиеся пробирки.
Например, в первый день опытов будет пробирка, из которой каждая мышь выпьет (все сдохли - значит в ней яд). И будет 128 пробирок из которых ни одна мышь не попробует (7 живых - значит в одной из 128 нетронутых яд). Ну и все промежуточные варианты. Чуть позже выложу схему, где-то рисовал раньше и сфоткал картинку.
В общем случае можно обследовать пробирок в количестве (число_дней+1)^число_мышей. Для описанной ситуации это 3^7 = 2187.
Сейчас, сейчас