ERUDITOR.RU

106. 100 бутылок

Есть 100 бутылок вина, в одну из которых оказался добавлен сильный яд, и всего 10 лабораторных мышек. Яд убивает мышку за 1 день (точность срока действия яда не позволяет отсчитывать дробное количество дней). За какое наименьшее количество дней можно с помощью этих мышей вычислить отравленную бутылку?
2016-05-08

Обсуждение


Задачки :: 100 бутылок
↓↓ 0 ↑↑   eruditor.ru (118 / 229)   2016-05-08 15:15   »»


Хорошая задачка для собеседования программистов.
↓↓ +5 ↑↑   eruditor (143 / 443)   2016-05-08 22:03   «« #2 »»   Ответить


Решил, получилось 1 день и 8 мышей.
↓↓ 0 ↑↑   GrizikMM (0 / 1)   2016-05-09 16:00   «« #3 »»   Ответить


Разве не 7?
↓↓ 0 ↑↑   eruditor (143 / 443)   2016-05-15 08:31   «« #5 »»   Ответить


У меня получилось 7 мышек тоже. Количество бутылок можно до 127 увеличить, ну если я правильно сложил все))
↓↓ 0 ↑↑   DM (0 / 2)   2016-05-16 09:35   «« #7 »»   Ответить


Как получился 1 день?
У меня 2 дня.
↓↓ 0 ↑↑   Арсений (0 / 3)   2016-05-14 09:02   «« #4 »»   Ответить


Решай через комбинаторику — число сочетаний из n по k без повторений.
↓↓ 0 ↑↑   DM (0 / 2)   2016-05-16 09:35   «« #6 »»   Ответить


Решение гораздо проще, без комбинаторик и сложных "правильно сложить всё". И число "127" (а вернее, 128) должно подсказать это решение ;-)


Расскажите как. Я короче как за 2 итерации и минимум 1 мышь сделать не могу.
↓↓ 0 ↑↑   Даниил (0 / 2)   2016-07-31 02:38   «« #11 »»   Ответить


2
↓↓ −5 ↑↑   Mr.Gelon (-5 / 1)   2016-05-17 17:36   «« #9 »»   Ответить


2 дня. Не больше 2 мышей
↓↓ 0 ↑↑   Алекс (0 / 1)   2016-06-29 13:28   «« #10 »»   Ответить


двоичное кодирование информации. Для 100 бутылок необходимо 7 бит.
↓↓ 0 ↑↑   Spanden (0 / 1)   2016-08-08 13:01   «« #12 »»   Ответить


Очень некорректное условие задачи. Минимум — один день, если случайно отравленная бутылка оказалась в первой партии. Максимум зависит от смертельной дозы вина для мышки и периода его выведения. Теоретически, очередную дозу можно вводить хоть через полчаса, если срок действия яда составляет 24 часа и 0 минут. Попробуйте опровергнуть, "программисты".
↓↓ 0 ↑↑   Евгений (-5 / 7)   2016-08-30 21:28   «« #13 »»   Ответить


И как это вы за 1 день найдете бутылку?!?!&₽
Я так понимаю делим 100 бутылок на 10 мышей. Каждая мышь пробует вино из 10 бутылок своей партии. Через день одна мышь умирает, значит бутылка в ее партии. Далее каждой из 9 мышей по бутылке. На 2 день смотрим кто умрет, если никто — значит яд в 10 ой бутылке. Ответ 2 дня и все 10 мышей. Хочу увидеть решение программистов
↓↓ 0 ↑↑   Алексей (0 / 1)   2016-08-30 21:39   «« #14 »»   Ответить


А чего программисты сразу, правильный ответ 2, имхо, все верно расписали, есть похожие задачи, а то выше понапишут про 1 день с умным видом. Все что дольше 24 часов уже следующий день, а в условии написано "точность срока действия яда не позволяет отсчитывать дробное количество дней" следовательно хрень их расчеты, с текущим условием...
↓↓ 0 ↑↑   Сергей (0 / 1)   2016-09-08 13:39   «« #15 »»   Ответить


Как программист — 1 день.
Пояснение:
для представления числа 100 в двоичной системе достаточно 7ми позиций, то нсть 7 мышей.
каждая мышь нумеруется (от 0 до 6 по привычке), а номера бутылок переводятся в двоичный код.
Таким образом подучаем например бутылка с номером 75 станет 100 1011, а с номером 5 станет 000 0101.
Номера позиций (опять же по привычке) идут справа на лево (6,5,4,3,2,1,0). Мышка пробует вино только если в двоичном номере бутылки на ее позиции стоит 1.
На следующий день несколько мышей уйдут к Великой Крысе... На озиции живых мышей запишем 0, на не очень живых 1, это и будет номер бутылки с ядом. Максимальная смертность — 6 мышей (если яд в 63ей бутылке 011 1111). И да, мыши при таком опыте пробуют из разного числа бутылок...
↓↓ +1 ↑↑   Иван (1 / 1)   2016-09-13 11:39   «« #16 »»   Ответить


Зачёт!
↓↓ 0 ↑↑   Данила (0 / 2)   2016-10-13 11:24   «« #17 »»   Ответить


Это должно было быть ответом на #16.
↓↓ 0 ↑↑   Данила (0 / 2)   2016-10-13 11:25   «« #18 »»   Ответить


2 дня
день 1 делим бутылки по 10 штук. делаем 10 смесей и даем 10 крысам
день второй 1 крыса погибает. берем 10 бутылок из которых делалась смесь для умершей крысы. из 9 даем оставшимся 9 крысам. одна в стороне.
вариантов 2:
1. если 1 крыса погибает значит она пила с отравленой
2. если крысы все живы отравлена та что отложена
↓↓ 0 ↑↑   Юрий (0 / 5)   2016-10-16 23:27   «« #19 »»   Ответить


2 дня.
↓↓ 0 ↑↑   Роман (-5 / 5)   2016-10-28 19:12   «« #20 »»   Ответить


Есть еще лучший способ чем у программистов, умрет максимум 3 мыши при любом раскладе а не 6, кто хочет могу написать ответ тут.
↓↓ 0 ↑↑   Roro (0 / 5)   2016-12-01 10:17   «« #21 »»   Ответить


Извиняюсь, дополню, метод так же работает для 1 дня но с минимальными потерями для мышей.
↓↓ 0 ↑↑   Roro (0 / 5)   2016-12-01 10:18   «« #22 »»   Ответить


Что-то все комбинаторику знают, а биологию не очень. Ну, допустим, что любое количество яда вызовет к вечеру кончину отравленной мышки (мышек). Ни раньше, ни позже. А вот сколько надо им наливать — не скопытятся ли они от такого количества бухла? Да еще и бутылки ополовинятся вдруг.

Для формализации фразы в скобках в условии — считаем, что неотравленная мышь живет нормально, отравленная — погибает через 24 часа после постановки опыта. Но опыты дозволяется проводить только в полдень. В полдень пришли — напоили, ушли. На следующий день осмотрели мышек и напоили, если надо, еще раз.

"Прямой" метод — разбить бутылки на блоки по 10 и дать смесь из 10 капель, а потом (одна погибнет, и "расскажет", где отравленная бутыль) девяти мышам по одной капле из 9 подозрительных бутылок — та, которая гибнет, пила на второй день из отравленной, если все выжили, то отравлена отложенная.
Итого — из 91 бутылки взята по 1 капле вина, из 9 бутылок — по две. Мыши пьют не более, чем по 10 капель за раз. Всем хорошо. Кроме одной или двух мышей.
Два дня потрачено.
↓↓ 0 ↑↑   Денис (25 / 14)   2017-01-27 15:45   «« #23 »»   Ответить


"Метод программиста":
Даем мышкам по капле из разных бутылок таким образом, чтобы капли из каждой бутылки раздавались разным наборам мышей. Уже хорошо, что мы выльем из каждой бутылки не более 10 капель. Больше, чем 2, но потери драгоценной жидкости невелики. А вот сколько достается бедным грызунам?
Набор по 0 мышей у нас один (1).
Наборов по 1 — 10, по 2 — 45, по 3 — 120, по 4 — 210, по 5 — 252, по 6 — снова 210 и т.д. в обратном направлении.
Как видно, можно поступить таким образом: составить список из наборов по 3 мышки, пронумеровать наборы, пронумеровать бутылки и разливать вино из каждой бутылки соответственно этому набору (не все наборы будут в списке). Через сутки смотрим, кто из мышей погиб, находим этот набор в списке и узнаем номер отравленной бутылки.
Теперь анализ. Теряем всего лишь 3 капли из бутылки. Лучше чем 10 и чуть-чуть хуже чем 2 — а в масштабе полной бутылки ничто. Но... это 300 капель всего, в среднем выпадает по 30 капель каждой животинке! Или поточнее?
А в скольких наборах участвует каждая? Ну, очевидно, это любой набор по 2 мыши из девяти остальных, или 36. Может быть, поскольку мы не 100% наборов выбираем, какие-то мыши окажутся в одной компании с любой комбинацией товарок, но мы "выкинем" только 20 наборов. Вот. Мыши вылакают от 16 до 36 капель на каждую... Много это или мало?

Одна капля в фармацевтике считается равной 0.025 мл (40 капель на миллилитр), можем считать это хорошей оценкой. Итак, мышки получают чуть меньше миллилитра вина каждая, 0,9, если точно. Пусть мыши крупные — 60 грамм (данные с сайта питомника лаб. мышей).
На килограмм веса выходит 1000/60 * 0,9=15 миллилитра=1/70 литра.
То есть они почувствуют себя примерно как человек, выпивший литр вина (!). А если мышата помельче, то и для них это, как для человека уже несколько бутылок одним махом.

Однако, если мыши у нас к алкоголю привычные — каким-то образом мы добиваемся этого, или решаем задачу не для вина, а для более безопасного питья, и считаем, что желудки у них крепкие (все же попробуйте без передышки выдуть литр компота), то это ответ:

Хватит одного дня, и только три мыши погибает.
- вешаем мышам на клетки ярлычки от A до J, это будут их индикаторы.
- напишем на стопке ярлычков всех возможные тройки из тех же букв: ABC, ABD, ABE, ... ABJ, ACD, ... GHI, GHJ, HIJ.
- всего получится 120 ярлычков, развесим их по одному на бутылки (20 ярлычков останутся не у дел)
- будем капать из каждой бутылки мышкам с этими самыми буквами (DFG, например, достанется мышам под номерами 4, 6 и 7)
- заметим, что каждой мышке достанется от 16 до 36 капель
- ждем, пока они это выпьют и засекаем сутки
- смотрим на результат.
Очевидно, что если отравлено вино DFG, то погибнут эти три мыши, остальные выживут. Они выпили отраву, тогда как мышь C, к примеру, пила только хороший продукт.
Обратное тоже верно: обнаружив, что погибли три (и только три мыши) с ярлыками D, F, G, мы делаем вывод, что отравлено вино DFG. Ведь если бы было отравлено CEG, то D и F выжили бы, но погибли C, E. Значит, CEG не отравлено — и так мы исключим еще 98 бутылок, оставив — правильно — DFG.
Итого — затрачен только один день.
↓↓ +5 ↑↑   Денис (25 / 14)   2017-01-27 16:30   «« #24 »»   Ответить


А сколько дней нужно (и как) на 1500 тысячи бутылок и 10 мышей? Со 100 процентной гарантией действенности метода, естественно.
↓↓ 0 ↑↑   Кирилл (0 / 3)   2017-05-15 19:01   «« #25 »»   Ответить


10 мышей за один день могут проверить 1024 бутылки, а за два дня 59049 🙂
↓↓ 0 ↑↑   Дамир (0 / 15)   2023-08-06 09:12   «« #26 »»   Ответить


Решил задачу для случая M количества мышей и N дней. Итоговая формула
(N+1)^M
↓↓ 0 ↑↑   Дамир (0 / 15)   2023-08-06 09:15   «« #27 »»   Ответить


Советую сначала найти максимальное количество бутылок которые могут протестировать две мыши за один день, потом за два дня, за три, ... за 7 дней. Далее для трёх мышей за один день, потом за два дня, за три, ... за 5 дней. Потом для 4 мышей. Когда нибудь станет очевидна закономерность и сама формула.
↓↓ 0 ↑↑   Дамир (0 / 15)   2023-08-06 09:59   «« #28   Ответить



© 2006-2024   Авторы