Задача про "Новичек" и 10 лабораторных мышек

Мне всегда нравились задачки, в которых решение кажется невозможным до тех пор, пока не узнаешь алгоритм, по которому ее можно решить. А как только алгоритм решения становится известным – задача кажется уже примитивной и легкой, а решение простым и понятным. Яркий пример такой задачи – задача на поиск пути из точки А в точку В по двумерному полю, минуя случайные препятствия. Когда сам пытаешься ее решить «в лоб» не зная теории – она кажется невероятно сложной. Но достаточно изучить алгоритм «А-звездочка» и вот решение задачи минуту назад казавшееся невозможным – сейчас уже простое и понятное.
И вот в интернетах наткнулся на еще одну такого рода задачу. Мне она очень понравилась:

В лаборатории есть 1000 пробирок, в одной из которых находится отравляющее вещество «новичек», а во всех остальных – безвредное вещество. Еще есть 10 подопытных лабораторных мышек.
Требуется: абсолютно точно узнать, в какой именно пробирке находится "новичок".
Задача проста? Ну тогда чтобы задача не казалась простой - вот Вам проблема: дело в том, что «новичок» не убивает мышку сразу! Дело в том, что мышка ГАРАНТИРОВАННО погибает от микроскопической дозы «новичка» только в течении примерно 20 часов (это уж самый-самый максимум), а в Вашем распоряжении есть всего 24 часа чтобы найти пробирку с ядом.

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

[яростно жмет "в пену"!!!]

Действительно, простая задача, если знать алгоритм её решения.

Пр классике в этой задаче травили не мышей, а политзаключённых!!!

> а мышки не лопнут от почти 512 инъекций

Там одна инъекция. Готовится коктейль из всех необходимых пробирок, а потом колется.

Т. Е есть 100х10 пробирок, 110минут на кормление + 20 часов времени на ожидание + 110 минут на съем показаний и 20 минут на подготовку . А далее, после подготовки, каждые 10 минут даём каждой из 10 мышек пробирку, подписываем её (+1 минута на 10 записей) и засекаем время. Как только сдохнет первая мышь, останавливаем эксперимент, отнимаем 4800минут, вычисляем пробирку и спокойно идем спать.

Итого, каждая мышь получает 100 инъекций за 110 минут с разницей 11минут (и примерно 10 секунд между мышами) и наблюдается с секундомером в течение 20 часов.

Можно рискнуть и уменьшить время на подготовку и съем показаний, тем самым ввести математическое ожидание с определенной вероятностью.

От 1 до 10 в зависимости от того, в какой по счету пробирке будет яд.

Инструкция для биологов по проведению опытов над мышами:
1. Взять мышь
2. Подготовить мышь к опыту
3. Полученную кашицу...

Тогда представим, что пробирок 1024
И начинаем кормить их в соответствии с порядковым номером. Через 20 часов мёртвые мыши это 1, а живые 0.

00000 00001 - 1
00000 00010 - 2
...
11111 01000 - 1000

Делим пробирки на десятки произвольным образом, распределяем между мышами. Добавляем в каждый коктейль еще девять доз, собранных из других десятков по принципу "второму мышу все пробирки номер 1, третьему - номер 2" и т.д. По составу пары издохших мышей вычисляем нужную пробирку.

> Делим пробирки на десятки произвольным образом, распределяем между мышами. Добавляем в каждый коктейль еще девять доз, собранных из других десятков по принципу "второму мышу все пробирки номер 1, третьему - номер 2" и т.д. По составу пары издохших мышей вычисляем нужную пробирку.

Ай блять, спросонья тысячу с сотней перепутал, простите, камрады

Усилим накал бредятины!
Вспомним, что ошибка неизбежна, и вероятность ее появления тем выше, чем сложнее манипуляции.
Следовательно, можно накосячить при приготовлении комбинированных смесей, при вкалывании, при интерпретации результатов.
Поэтому не выебываемся, заказываем еще 2000 мышей (1000 на опыты, 1000 как контрольную группу, исходные 10 - про запас).
Делаем эксперимент как положено, пропиваем премию.

Все мыши выживут, "Новичок" же безвреден. Хотя если на лабораторную мышь надеть трусы, пропитанные "Новичком"...

> Хотя если на лабораторную мышь надеть трусы, пропитанные "Новичком"...

Причем трусы должны содержать компоненты Навального

> 1. Яд действует в течение суток. У нас есть 2 суток.
> 2. Мышей не 10, а 7.
> 3. Пробирок не 1000, а 2000.

4. Яд не в одной пробирке, а в 13...

> По составу пары издохших мышей вычисляем нужную пробирку.

если правильно понял, то на первом этапе таким образом ты вычислишь "десяток" пробирок с двумя дохлыми мышами.

как за оставшиеся 4 часа и 8 мышей вычислить одну?

> Hi there, are you interested in emigrating to the UK?

Нужен козёл отпущения для демонстрации как кровавый режим дотянулся до очередной ставшей бесполезной жертвы?

Это задача про то как в двоичной системе досчитать до тысячи.

[censored]

> Самое трудное будет не ошибиться и не запутаться в смешивании содержимого этих 1000 пробирок.

На самом деле не так сложно.
Ставим в ряд 10 колб, куда мы будем капать из пробирок, на колбы клеем цифры от 1 до 10. А на каждую пробирку клеем её номер в двоичной системе, и под каждым разрядом подписываем его порядковый номер (это всё можно распечатать на компьютере в Экселе, он не ошибается).

Получается типа:

0 1 0 1 1 0 0 0 1 1
1 2 3 4 5 6 7 8 9 10

А можно не двоичное число писать, а красным цветом выделять разряд, в котором стоит единица. Или нули скрыть, а единицы оставить.

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

> Вот так бодрее


1. мышей 7

2. Пробирок 2000

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.

Эвон. Неплохо.)
Я не все вкурил, но я перечитаю и постараюсь понять, засчет чего весь цимес)

> Поэтому не выебываемся, заказываем еще 2000 мышей

и используем кодировку с избыточностью
имени Хэмминга или Рида с Соломоном...