Меню

1000 бутылок вина 1 отравлена 10 кроликов решение

Король и 1000 бутылок вина: как найти одну отравленную?

Условие задачи

Вы — правитель средневековой империи, и завтра у вас намечается торжество. Это будет самая чумовая вечеринка из всех, что вы когда-либо устраивали. По такому поводу не грех открыть 1000 бутылок вина. Но вот незадача: одна из них отравлена.

У яда нет никаких симптомов, кроме смерти, которая наступает в течение 10–20 часов после принятия даже малейшей дозы яда.

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

Какое минимальное количество заключённых должно попробовать вино из бутылок, чтобы точно найти отравленную в течение 24 часов?

Решение

Спойлер: попробовать вино должны 10 узников.

Пронумеруйте все бутылки в двоичной системе (начиная с нуля). Затем присвойте каждому узнику двоичный флаг. Например, первому — 00000000001, третьему— 00000000100 (чем больше номер узника, тем дальше влево продвигается единица) и т.д. Узники должны сделать глоток из каждой бутылки, в которой попадается их флаг. Например, из восьмой бутылки (0000000111) сделают по глотку первый, второй и третий узники.

Вот как мы бы нашли отравленную бутылку, будь их всего 8:

1 2 3 4 5 6 7
Узник A X X X X
Узник B X X X X
Узник C X X X X

Если все узники умерли, то отравлена седьмая бутылка (или восьмая, если считать от единицы): номера узников — 001, 010 и 100, нужно найти бутылку, в которой все единицы встречаются на тех же позициях, что и у узников. Это бутылка под номером 111 или же седьмая бутылка в нашей таблице.

Никто не умер — нулевая бутылка. Умерли A и B — яд в третьей бутылке. Не забывайте, что мы нумеруем от нуля.

Для десяти человек существует 1024 уникальные комбинации, так что мы можем проверить до 1024 бутылок вина.

Каждый узник попробует вино примерно из 500 бутылок. Узники должны пить из каждой бутылки не дольше 15 секунд и только небольшое количество вина. Небольшие глотки не просто позволят оставить побольше вина гостям, но и не дадут узникам умереть от алкогольного отравления. Поскольку они выпьют примерно по миллилитру из каждой бутылки, в сумме каждый из них выпьет всего по бутылке.

У узников будет как минимум 50-процентный шанс выжить. Только в одном случае умрут все узники. Также существует 10 комбинаций, в которых умрёт 9 из 10 человек. Таким образом, избегая двух типов этих комбинаций, можно ограничиться смертью максимум восьми узников.

А вы знаете другие решения этой задачи? Делитесь в комментариях.

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Источник

1000 бутылок вина 1 отравлена 10 кроликов решение

Царь при подготовке к пиру узнал, что одна из 1000 бутылок вина с ядом.
У него есть 10 кроликов, которыми можно пожертвовать.
Как узнать, какая из бутылок с ядом, если известно, что после выпивания хоть капли яда кролик через 5 дней умрет.
Знать, какая бутылка отравлена надо уже через неделю!

Читайте также:  Китаянка давит кролика ногами

Пишите сюда свои варианты решения или вопросы по условию! Скидку получит тот кто первым напишет вариант которым МЫ решили эту загадку!)
ПОЛНОСТЬЮ опишите ответ, что то типа и.т.д в ответе — НЕ ПРОЙДЁТ и в спорных случаях будет расцениваться как неверный ответ!
Мы не будем проверять рабочие ли у вас версии или нет, просто под одним из вариантов напишем ПОЗДРАВЛЯЕМ — это НАШ вариант(если он будет)!

Из 1000 берем по 250 бутылок (делаем пробник из 250 капель в одну), даем 4м кроликам, из 250 разделяем ящики по 50 даем (пробник из 50ти капель) 5ти другим кроликам, на след день из 50 делаем 10 пробников из 5 бутылок , даем пятерым. Остается на след день дать по десять пробников десятке кроликов. По цепочке дохлых кроликов вычисляем в какой бутылке яд.

Но гугл говорит, что легче пронумеровать бутылки двоичным кодом, и пронумеровать кроликов десятью разрядами, и соответственно давать из каждой бутылки кроликам которым соответствует двоичный код. Допустим 666ю бутылку давать кроликам 1010011010 (первому, третьему, пятому, шестому и восьмому.)
Через 5 дней посмотреть в каком порядке умерли кролики, и по коду бутылки вычислить саму бутылку.

Источник

Задача про отравленное вино и кроликов , головоломка якобы

Сообщений: 9 674
Из: Чебоксары/Москва

У тебя есть 1000 бутылок вина — разного и вкусного, но достоверно известно, что одна бутылка отравлена. Надо бы вычислить, какая отравлена. На это у тебя есть 10 кроликов, ты можешь пробовать вино на них. Яд на кроликов действует даже в микродозах, но действует не сразу, а на 5й — 7й день после приема. Надо бы за 8 дней найти отравленную бутылку. Кроликов не жалко, количество выпитого ими вина значения не имеет.

Сообщение отредактировал Sargay — Dec 7 2007, 11:58

И кто я? И где я? И зачем все это?

Сообщений: 2 362
Из: века в век

Тут только так.
Если сразу попадешь отравленным вином на кролика, то за 5 дней узнаешь.
Иначе не возможно узнать.

Сообщений: 12 229
Из: Чебоксары

Сообщений: 12 229
Из: Чебоксары

Помоему задача решается такю И кроликов хватит и 8. Для простоты приведу пример с 10 бутылками (расписывать на 100 лень)

бутылки\кролики
1 2 3 4
1 — — — +
2 — — + —
3 — — + +
4 — + — —
5 — + — +
6 — + + —
7 — + + +
8 + — — —
9 + — — +
10 + — + —
Кролей поим так: 1ый кроль пьёт из 8, 9 и 10 бутылки, 2й — из 4,5,6 и 7, 3й — из 2, 3, 6, 7, 10. И т.д.

Потом смотрим какой набор кролей помер. К примеру, если померли только 2й и 4й — значит яд в 5й бутылке, если только 1й — значит в 8й бутылке.

Читайте также:  Рейтинг пюре из кролика для грудничка

Иными словами, 10ю кролями можно проверить 1024 бутылки.

Сообщение отредактировал Creator_xx8x — Dec 5 2007, 14:17

Сообщений: 12 229
Из: Чебоксары

Сообщений: 12 229
Из: Чебоксары

Судя по твоему решению хватит и 7 кроликов

Сообщений: 12 229
Из: Чебоксары

Не позднее чем за 7 дней 10 кроликив 1024 бутылки проверят. Ничего ен путаешь.

Сообщений: 12 229
Из: Чебоксары

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

Сообщений: 23 520
Из: Москва

Изготавливается 10 коктейлей из 19 компонентов (10+9 — ряд и строка матрицы 10*10).
Или поятся 10 кролей. На 5 или 7 день помирает один. ПОдозреваемые — 19 бутылок. Непойдет, остался 1 день.

Тогда изготавливаются столько сетов по 10 девятнадцатикомпонентных коктейлей, сколько потребуется для получения одного живого кролика на выходе. Скоько — хз. А также как комбинировать матрицу 10*10 тоже хз.

Сообщений: 12 229
Из: Чебоксары

Creator_xx8x, действительно 10 кроликами можно проверить 1024 бутылки причем неважно через сколько часов действет яд. главное чтобы действия яда продолжалось менее того времени, сколько ставится в условии задачи

Источник

masterok

Мастерок.жж.рф

Хочу все знать

Есть 1000 бутылок вина, в одну из которых оказался добавлен сильный яд, и всего 10 лабораторных мышек. Яд убивает мышку за 1 день (точность срока действия яда не позволяет отсчитывать дробное количество дней).

За какое наименьшее количество дней можно с помощью этих мышей вычислить отравленную бутылку?

Как это называется? Классическая комбинаторика? Не простая задачка конечно, но оригинальное решение. Жаль только, то решение все таки специфически математическое, а не логическое.

Пронумеруйте каждую мышь, возьмите 10 стаканов и пронумеруйте их тоже. Далее пронумеруйте каждую бутылку, но не обычными числами, а… ДВОИЧНЫМИ. Поскольку 2 в 10 степени равно 1024, то вам понадобится для этого не более 10 разрядов. Далее каждую бутылку разливаем в каждый из стаканов по следующему правилу:

В стакан номер N наливаем из некоторой бутылки, если N-й разряд в её двоичном номере равен 1, и не наливаем, если он равен 0. Например, из бутылки номер 3 наливаем немного вина только в 1-й и 2-й стакан, т.к. двоичная запись числа 3 будет 0000000011. Полученные коктейли даём попробовать мышам с соответствующим номером.

Через сутки некоторые мыши умрут. Теперь составим двоичное число, где N-й разряд равен 1, если мышь номер N умерла, и 0 — если осталась жива. Полученное число и будет двоичным номером отравленной бутылки.

2^10=1024
Разряды соответствуют спаиваемым кроликам
0000000000 — Никому не спаиваем нулевую бутылку.
0000000001 — Первому первую
0000000010 — Второму вторую
0000000011 — Второму и третьему четвертую

1111100111 — Кроликам 1,2,3,4,5,8,9,10 спаиваем 1000-ную бутылку.

Итого. Потребуется один день.

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

Источник

Простая задача с собеседования в Яндекс

Дубликаты не найдены

прочитал то что думал 5 лет назад, да я был чертовски умен 🙂 поддерживаю себя прошлого 🙂

Читайте также:  Убираем запах с мяса кролика

Достаточно всего одного дня, но помереть в худшем случае могут все кролики и то, что все они напьются в хлам – совершенно несомненно.

1) Нумеруем бутылки и кроликов (с нуля).

2) Поим кроликов по следующей стратегии: i-ый кролик выпивает из каждой бутылки, номер которой имеет единицу в i-ом двоичном разряде.

3) Составляем номер бутылки из номеров умерших кроликов: если умер i-ый кролик, то номер бутылки имеет единицу в i-ом разряде. Если ни один не умер, то отравлена бутылка номер нуль.

У меня завтра собеседование в Яндексе, думаете они меня возьмут на работу? =)

Примечание. Алгоритм также можно обобщить для произвольных N (количества бутылок) и K (количества кроликов): нужно просто сгруппировать бутылки и пронумеровать группы, так, чтобы хватило на всех. Однако, т.к. в худшем случае (бутылка номер 1023, пусть её и нет в нашем конкретном случае) помирают все кролики, то необходимо будет использовать не двоичную нумерацию, а иную, и использовать группы кроликов (один кролик был частным случаем, группой из одного), чтобы всегда какая-то группа кроликов не выпивала из какой-то группы бутылок и оставалось достаточное количество кроликов для второго и последующих дней. Там может быть много соображений, касающихся разбиений на группы, один из них может быть максимизация произведения G = (C0 + 1)*(C1 + 1)*. *(C(M-1)+1) при достижении оптимального S = (C0 — 1) + (C1 — 1) + . + (C(M-1) — 1), где CJ – количество кроликов в J-ой группе (сумма CI для I jот 0 до (M-1) равна K), а M – количество групп. Далее мы разбиваем бутылки на G количество групп, нумеруем их странным образом (I-ая цифра номера может принимать значения от 0 до (CI — 1)) и по итогам дня составляем номер группы бутылок по номерам померших кроликов в каждой группе (аналогично частному случаю, просто конкатенируем цифры). S – количество кроликов, которое выживет после текущего дня в худшем случае, показатель избыточности нашего разбиения. Для частного решения выше, M = 2**10, S = 0 т.е. он использует кроликов нещадно и имеет максимальный M (составить алгоритм оптимизации M и S для случая нескольких дней – для достижения минимизации количества этих самых требуемых дней – предлагаю читателю в качестве упражнения – задача требует некоторого анализа, который выйдет за рамки короткого примечания в решении простой задачи).

Ещё примечание. Наверное, есть специальная литература по этой области теории алгоритмов. Наверное, если бы я её читал, мне бы не потребовалось думать над задачей несколько часов пока я не пришёл к правильному ответу (я даже начал было набирать здесь камент, думая, что меньше двух дней никак не сделать).

И ещё одно примечание. А, вообще, тестировать на няшных и пушыстых кроликах всякие вредные вещества – неправильно, гораздо этичнее и практичнее было бы выявлять яды никого ими не отравляя =)

Источник

Adblock
detector