vott.ru — Мне всегда нравились задачки, в которых решение кажется невозможным до тех пор, пока не узнаешь алгоритм, по которому ее можно решить. Вот одна из таких задач.
Мне всегда нравились задачки, в которых решение кажется невозможным до тех пор, пока не узнаешь алгоритм, по которому ее можно решить. А как только алгоритм решения становится известным – задача кажется уже примитивной и легкой, а решение простым и понятным. Яркий пример такой задачи – задача на поиск пути из точки А в точку В по двумерному полю, минуя случайные препятствия. Когда сам пытаешься ее решить «в лоб» не зная теории – она кажется невероятно сложной. Но достаточно изучить алгоритм «А-звездочка» и вот решение задачи минуту назад казавшееся невозможным – сейчас уже простое и понятное.
И вот в интернетах наткнулся на еще одну такого рода задачу. Мне она очень понравилась:
В лаборатории есть 1000 пробирок, в одной из которых находится отравляющее вещество «новичек», а во всех остальных – безвредное вещество. Еще есть 10 подопытных лабораторных мышек.
Требуется: абсолютно точно узнать, в какой именно пробирке находится "новичок".
Задача проста? Ну тогда чтобы задача не казалась простой - вот Вам проблема: дело в том, что «новичок» не убивает мышку сразу! Дело в том, что мышка ГАРАНТИРОВАННО погибает от микроскопической дозы «новичка» только в течении примерно 20 часов (это уж самый-самый максимум), а в Вашем распоряжении есть всего 24 часа чтобы найти пробирку с ядом.
З.ы. на первый взгляд эта задача кажется похожей на классические задачи про взвешивания монет и поиск фальшивки. Но с таким подходом на поиск "новичка" уйдет до 5 суток, которых у Вас нет.
На второй взгляд задача с такими жесткими условиями вообще не имеет решения. Но - решение есть.
Т. Е есть 100х10 пробирок, 110минут на кормление + 20 часов времени на ожидание + 110 минут на съем показаний и 20 минут на подготовку . А далее, после подготовки, каждые 10 минут даём каждой из 10 мышек пробирку, подписываем её (+1 минута на 10 записей) и засекаем время. Как только сдохнет первая мышь, останавливаем эксперимент, отнимаем 4800минут, вычисляем пробирку и спокойно идем спать.
Итого, каждая мышь получает 100 инъекций за 110 минут с разницей 11минут (и примерно 10 секунд между мышами) и наблюдается с секундомером в течение 20 часов.
Можно рискнуть и уменьшить время на подготовку и съем показаний, тем самым ввести математическое ожидание с определенной вероятностью.
Делим пробирки на десятки произвольным образом, распределяем между мышами. Добавляем в каждый коктейль еще девять доз, собранных из других десятков по принципу "второму мышу все пробирки номер 1, третьему - номер 2" и т.д. По составу пары издохших мышей вычисляем нужную пробирку.
> Делим пробирки на десятки произвольным образом, распределяем между мышами. Добавляем в каждый коктейль еще девять доз, собранных из других десятков по принципу "второму мышу все пробирки номер 1, третьему - номер 2" и т.д. По составу пары издохших мышей вычисляем нужную пробирку.
Ай блять, спросонья тысячу с сотней перепутал, простите, камрады
Усилим накал бредятины!
Вспомним, что ошибка неизбежна, и вероятность ее появления тем выше, чем сложнее манипуляции.
Следовательно, можно накосячить при приготовлении комбинированных смесей, при вкалывании, при интерпретации результатов.
Поэтому не выебываемся, заказываем еще 2000 мышей (1000 на опыты, 1000 как контрольную группу, исходные 10 - про запас).
Делаем эксперимент как положено, пропиваем премию.
> В лаборатории есть 1000 пробирок, в одной из которых находится отравляющее вещество «новичек», а во всех остальных – безвредное вещество. Еще есть 10 подопытных лабораторных мышек. > Требуется: абсолютно точно узнать, в какой именно пробирке находится "новичок". > Задача проста? Ну тогда чтобы задача не казалась простой - вот Вам проблема: дело в том, что «новичок» не убивает мышку сразу! Дело в том, что мышка ГАРАНТИРОВАННО погибает от микроскопической дозы «новичка» только в течении примерно 20 часов (это уж самый-самый максимум), а в Вашем распоряжении есть всего 24 часа чтобы найти пробирку с ядом.
Так слишком просто.
Вот так бодрее:
1. Яд действует в течение суток. У нас есть 2 суток.
2. Мышей не 10, а 7.
3. Пробирок не 1000, а 2000.
Британские уч0ные несколько лет назад убедительно доказали, что задачи про "Новичок" решаются методом Хайли-Лайкли.
Таким образом:
- берем любую использованную пробирку после инъекции любой мыши
- объявляем, что Хайли-Лайкли в ней был "Новичок"
- уничтожаем все оставшиеся улики, и предлагаем не согласным с результатом доказать, что мы не правы.
> Британские уч0ные несколько лет назад убедительно доказали, что задачи про "Новичок" решаются методом Хайли-Лайкли. > Таким образом: > - берем любую использованную пробирку после инъекции любой мыши > - объявляем, что Хайли-Лайкли в ней был "Новичок" > - уничтожаем все оставшиеся улики, и предлагаем не согласным с результатом доказать, что мы не правы
Hi there, are you interested in emigrating to the UK?
> Самое трудное будет не ошибиться и не запутаться в смешивании содержимого этих 1000 пробирок.
На самом деле не так сложно.
Ставим в ряд 10 колб, куда мы будем капать из пробирок, на колбы клеем цифры от 1 до 10. А на каждую пробирку клеем её номер в двоичной системе, и под каждым разрядом подписываем его порядковый номер (это всё можно распечатать на компьютере в Экселе, он не ошибается).
Получается типа:
0 1 0 1 1 0 0 0 1 1
1 2 3 4 5 6 7 8 9 10
А можно не двоичное число писать, а красным цветом выделять разряд, в котором стоит единица. Или нули скрыть, а единицы оставить.
А потом рутинная операция: взял пробирка, посмотрел, на против каких номеров стоит единица - капнул в колбы с соответствующими номерами. Взял следующую пробирку... Ну а потом уже из этих колб уколоть мышей и посмотреть, что получится.
3. Времени 2 суток, действует вещество в течении 1 суток
===
7 мышей это = 128 комбинаций двоичных. 1111111
128 комбинаций содержится в 2000 комбинаций - 15 целых раз
это 16 блоков пробирок по 128
Каждую Nю пробирку из каждого блока скармливаем мышам в соответствии с бинарным представлением N
Т.е. 0ю пробирку из каждого из 16 блоков не разливаем по мышам воообще, т.е. 0000000
...
3ю пробирку из каждого из 16 блоков разливаем по мышам вот так 0000011
4ю пробирку из каждого из 16 блоков разливаем по мышам вот так 0000100
...
127ю пробирку из каждого из 16 блоков разливаем по мышам вот так 1111111
В итоге по истечении суток - подохнет ряд мышей.
Что мы тут узнаем?
Мы узнаем N - номер внутри блока.
Напр, подохли мыши 0000011, это значит, что какая то из 3их пробирок - целевая.
Или, напр, мыши вообще не подохли - это значит, что какая то из 0ых пробирок - целевая.
Дальше у нас остается 16 пробирок.
Нам нужно повторить эксперимент, но уже с 4мя мышами.
Вопрос лишь в том - останутся ли они живые в таком количестве.
Проверим. Напр, если целевая пробирка 127я в одном из блоков - подохнут все мыши.
Мышиной емкости вроде как не хватает на все вариации.)))
Навскидку, если пытаться решать вот так в лоб, то что один раз, что несколько - раз изначально не хватает комбинаций, то и по результатам второй итерации тоже не хватит.
Да, там хитрее. Блоки переменных размеров. Такие, что если сдохнет несколько мышей, то оставшихся мышей во второй день должно в точности хватить на оставшиеся пробирки.
Например, в первый день опытов будет пробирка, из которой каждая мышь выпьет (все сдохли - значит в ней яд). И будет 128 пробирок из которых ни одна мышь не попробует (7 живых - значит в одной из 128 нетронутых яд). Ну и все промежуточные варианты. Чуть позже выложу схему, где-то рисовал раньше и сфоткал картинку.
В общем случае можно обследовать пробирок в количестве (число_дней+1)^число_мышей. Для описанной ситуации это 3^7 = 2187.
Сейчас, сейчас
И вот в интернетах наткнулся на еще одну такого рода задачу. Мне она очень понравилась:
В лаборатории есть 1000 пробирок, в одной из которых находится отравляющее вещество «новичек», а во всех остальных – безвредное вещество. Еще есть 10 подопытных лабораторных мышек.
Требуется: абсолютно точно узнать, в какой именно пробирке находится "новичок".
Задача проста? Ну тогда чтобы задача не казалась простой - вот Вам проблема: дело в том, что «новичок» не убивает мышку сразу! Дело в том, что мышка ГАРАНТИРОВАННО погибает от микроскопической дозы «новичка» только в течении примерно 20 часов (это уж самый-самый максимум), а в Вашем распоряжении есть всего 24 часа чтобы найти пробирку с ядом.
З.ы. на первый взгляд эта задача кажется похожей на классические задачи про взвешивания монет и поиск фальшивки. Но с таким подходом на поиск "новичка" уйдет до 5 суток, которых у Вас нет.
На второй взгляд задача с такими жесткими условиями вообще не имеет решения. Но - решение есть.