Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

106. 100 бутылок

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

Обсуждение


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


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


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


Разве не 7?
↓↓ 0 ↑↑   eruditor (133 / 441)   15 май 2016 08:31   «« #5 »»   Ответить


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


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


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


Решение гораздо проще, без комбинаторик и сложных "правильно сложить всё". И число "127" (а вернее, 128) должно подсказать это решение ;-)
↓↓ 0 ↑↑   Кузнецов Сергей Германович (267209 / 13856)   16 май 2016 22:20   «« #8 »»   Ответить


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


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


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


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


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


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


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


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


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


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


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


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


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


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

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

"Прямой" метод — разбить бутылки на блоки по 10 и дать смесь из 10 капель, а потом (одна погибнет, и "расскажет", где отравленная бутыль) девяти мышам по одной капле из 9 подозрительных бутылок — та, которая гибнет, пила на второй день из отравленной, если все выжили, то отравлена отложенная.
Итого — из 91 бутылки взята по 1 капле вина, из 9 бутылок — по две. Мыши пьют не более, чем по 10 капель за раз. Всем хорошо. Кроме одной или двух мышей.
Два дня потрачено.
↓↓ 0 ↑↑   Денис (25 / 13)   27 янв 2017 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 / 13)   27 янв 2017 16:30   «« #24 »»   Ответить


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



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы