Добрый день.
Сегодня я хочу поговорить о небезызвестной задаче о тысяче бутылок и 10 крысах. Это задача из собеседований, которую очень часто обсуждают в Интернете.
Напомню в общем виде ее условие:
Есть 1000 бутылок с одинаковым содержимым. Одна из них отравлена ядом, который не выделяется внешне. Также есть 10 лабораторных крыс. Известно, что содержимое неотравленных бутылок безвредно для крысы, а яд убивает ее в течение суток. Как за минимально возможное число дней можно вычислить отравленную бутылку?
И я подумал: а какие варианты и обобщения могут быть у этой задачи?
Предлагаю к обсуждению следующие варианты с измененными или дополнительными условиями:
1. Что, если отравлены сразу две бутылки?
2. Что, если в одной из бутылок есть антидот, нейтрализующий действие яда? Как тогда вычислить отравленную бутылку?
3. А если каждая крыса может за день принять дозу не более чем из определенного числа бутылок?
4. Какое максимальное число бутылок можно проверить с помощью 10 крыс за указанное число дней?
А пока предлагаю вариант решения с 2 тестами:
Будем использовать двоичные коды. Поскольку крыс 10, то уникальных кодов будет 2^10=1024. Именно такое максимальное количество бутылок, кстати, можно проверить в оригинальной задаче (не забываем про принцип Дирихле).
Зарезервируем 10 емкостей, по одной для каждой крысы. Пронумеруем емкости. Для каждой бутылки проверяем код и наливаем из нее только в те емкости, для которых соответствующий бит равен 1. Например, содержимое бутылки с кодом 0010010001 наливаем в емкости под номерами 3, 6 и 10.
После этого даем материалы на пробу крысам в соответствии с номерами. Через сутки проверяем состояние каждой крысы.
В оригинальной задаче коды не повторяются, а потому на основании состояний крыс можно вычислить искомую бутылку. Но в двухтестовом варианте есть нюансы.
Через день после начала первого теста выживет определенный набор крыс. И с учетом результатов нужно провести второй тест с оставшимися крысами и определенной частью бутылок. Количество бутылок с одинаковым первоначальным кодом будет зависеть от числа нулей в этом коде.
Допустим, что после первого теста погибли все крысы. Тогда проведение второго теста станет невозможным, а потому нам наверняка должно быть известно, какая бутылка отравлена. Поэтому код со всеми единицами мы присвоим только одной бутылке.
Рассмотрим случай, когда выжила всего одна крыса. Тогда во втором тесте мы можем проверить до 2 бутылок. Мы вычисляем, кто именно выжил, и даем ей содержимое из одной бутылки, чтобы определить ту самую. Всего возможно 10 таких случаев, и для каждого такого случая мы резервируем по 2 бутылки.
Перейдем к случаям, когда выжили две крысы. В зависимости от того, какие именно, возможно 10*9/2=45 таких случаев, и для каждого из них мы резервируем еще по 4 бутылки.
Если выжили 3 крысы, а это 10*9*8/6=120 случаев, то можем проверить до 8 бутылок для каждого случая.
Аналогично с 4, 5, 6 крысами и т.д.
Если в первом тесте погибла только одна крыса, то мы снова имеем 10 различных вариантов этого события, но поскольку у нас осталось 9 крыс, то проверить мы уже сможем до 2^9=512 бутылок.
И наконец, зарезервируем еще 1024 бутылки. В первый день мы никому их не дадим. И задействуем их только в том случае, если на следующий день все крысы выживут. Дальнейшие действия аналогичны решению оригинальной задачи.
Таким образом, максимально возможное число бутылок в данном случае равно сумме:
1+10*2^1+(10*9)/2*2^2+(10*9*8)/3!*2^3+...+(N!)/((N-K)!*K!)+2^K+...+2^N, где x! - факториал (1*2*3*4...; 0!=1), N - первоначальное число крыс, K - число крыс, выживших после первого теста.
Расчеты предлагаю сделать самостостоятельно.
А что вы думаете по этому поводу? Пишите в комментариях.