Задача 10 кроликов

Понравилась задачка, которую мне рассказали сегодня. Здесь я такой не нашла, хотя как оказалось, задача известная. Поэтому предлагаю.

Есть 1000 бутылок вина и 10 мышей. Ровно одна из бутылок отравлена. Яд действует через час с момента принятия. Как, экспериментируя на мышах, за час определить, какая из бутылок отравлена?

задан 8 Окт ’14 20:40

Всё это замечательно. Ответы правильные. Только вот, что меня беспокоит. Ни одна мышь не сможет выпить столько вина. А если выпьет, то где гарантия, что не отравилась от чрезмерного употребления алкоголя?

2 ответа

Это похоже на способ угадывания одного числа из 1000 (или из 1024) при помощи 10 вопросов, задаваемых заранее. Занумеруем мышей, и каждой бутылке произвольным образом сопоставим свой двоичный код длиной 10. Поскольку кодов всего $%2^<10>$%, этого количества хватит. Далее для каждой мыши делаем «коктейль», включая в его состав для $%i$%-й мыши вино из данной бутылки, если в её коде на $%i$%-м месте стоит 1. Через час смотрим, какие мыши сдохнут. По их номерам восстанавливаем код и определяем бутылку.

отвечен 8 Окт ’14 23:59

falcao
247k ? 2 ? 35 ? 48

Я думаю тут, только час уйдет на нумерацию бутылок.))) Вообще задача понравилась! У falcao верное решение, только мне кажется, решение можно более подробно оформить. Например так:

Допустим, у нас есть 1000 бутылок вина и 1 бутылка отравлена. Пронумеруем бутылки: $$\eqalign< & <\text<бутылка 1>> — 0000000001 \cr & <\text<бутылка 2>> — 0000000010 \cr & <\text<бутылка 3>> — 0000000011 \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \vdots \cr & <\text<бутылка 1000>> — 1111101000 \cr> $$

Пронумеруем мышей под каждым битом:

То есть правая крайняя мышь будет под индексом 0, а левая крайняя под индексом 9. Берем все бутылки, где под индексом 0 задан единичный бит, и наливаем той мыши, которой соответсвует данный индекс. То же самое проделываем для мышей под индексом $%i$%, где $%i = \ < 1,2,3,4,5,6,7,8,9\>$%.

Через заданное время смотрим, какие мыши отправились в мир иной. Например, если скончались мыши под индексами: $%i = \ < 0,3,7,9\>$%, то номер бутылки можно определить по числу $%1010001001 = 649$%.

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

Задача о 1000 бутылок

Шерлок Холмс развалился на диване и простреливал на противоположной стене очередной вензель. Скрипка надоела, от химических опытов болела голова, табак для трубки закончился. Самое паскудное, давно не было интересных дел, как будто весь преступный мир Лондона в это лето дружно отправился в отпуск на континент. Поэтому он был приятно удивлён видом запыхавшегося инспектора Лейстрейда.

— Мистер Холмс, выручайте, срочное дело!

— У вас все дела срочные, — валял дукрака Холмс, прикидывая, что могло приключиться на этот раз…

— У вас все дела государственные…

— Но речь идёт о жизни Её величества!

Кот на кушетке навострил уши. Холмс тоже бы так сделал, если бы мог.

— А подробнее, инспектор?

Лейстрейд отдышался, выпил предложенный миссис Хадсон стакан воды и начал свой рассказ…

— Завтра, как Вы знаете, Королева устраивает Большой Благотворительный Вечер в Букингемском дворце. Приглашены именитые гости — послы, министры, члены обеих палат и прочий нобилитет. Одного вина французского 1845-го года урожая закуплена тысяча бутылок! А тут по нашим точным агентурным сведениям поступила информация, что одна из этих бутылок отравлена сильнейшим ядом! Он убивает в любой концентрации, даже 1/1000! Отменить Вечер никак нельзя, провести его без вина — немыслимо! Заменить вино — нечем. А главное, необходимо срочно найти именно ту самую отравленную бутылку, чтобы изучить её как следует — снять отпечатки Дело осложняется тем, что яд этот действует не сразу, а в течение суток, и как раз сутки остались до Мероприятия! Для тестирования у нас всего 10 лабораторных мышей, и других нам так срочно взять негде. Помогите, Холмс, на вас вся наша надежда!

Холмс на секунду задумался.

— Так, 2 в десятой — тысяча двадцать четыре, — невнятно пробормотал знаменитый сыщик. Ну конечно, вот что надо сделать!

— Это гениально, Холмс, — воскликнул Ватсон.

— Это элементарно, Ватсон, — скромно пробасил Холмс.

Лейстрейд побежал срочно выполнять полученную инструкцию.

Что же сказал ему Холмс?

Прежде чем читать дальше, попробуйте решить задачу сами!

Решение

Вот что сказал инспектору Холмс…

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

В стакан номер N наливаем из некоторой бутылки, если N-й разряд в её двоичном номере равен 1, и не наливаем, если он равен 0.

Например, из бутылки номер 3 наливаем немного вина только в 1-й и 2-й стакан, т.к. двоичная запись числа 3 будет 0000000011.

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

  • Задачки, 19 апреля 2020 в 14:33
  • Никита Прияцелюк

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

Вы — правитель средневековой империи, и завтра у вас намечается торжество. Это будет самая чумовая вечеринка из всех, что вы когда-либо устраивали. По такому поводу не грех открыть 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 человек. Таким образом, избегая двух типов этих комбинаций, можно ограничиться смертью максимум восьми узников.

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

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

Ответ: 1. В зеленой вдвое больше, чем в желтой. Это значит, что в зелёной чётное количество кроликов.

2. Вы продаете пять кроликов из клетки, которая слева от вас, а половину остальных пересаживаете в красную. Это значит что (N-5) делится на два, следлвательно, N — нечётное число, значит эта клетка (в которой чётное) не зелёная.

3. А половину остальных пересаживаете в красную. Это значит что предыдущая клетка не красная, получается, что она желтая.

Комментарии

Оставлен Neko Сб, 04/28/2012 — 13:39

Во время решения задачи резко приходит в голову, что кролика нельзя разорвать пополам. Подвох обнаруживается сразу. Любите кроликов, и все задачи будут решаться в считанные секунды. =)

Оставлен Kiro Сб, 04/28/2012 — 19:33

«1. В зеленой вдвое больше, чем в желтой. Это значит, что в зелёной чётное количество кроликов.»
Лолщито простите? Это каким это образом вы такое определили?
Такую задачу, легче всего считать взял изначальное число. Ошибка вашего решения заключается в том, что какое бы число мы изначально не взяли, если умножить его на 2, то оно будет четным.
Допустим у нас в желтой клетке 5(изначально нечетное) кроликов. Соответственно в зеленой 10. Из желтой мы продаем 5, а остальных (оставшуюся половину от 10) мы пересаживаем в красную.
Возьмем 10(изначально четное) число кроликов в желтой. В зеленой соответственно 20. 10 продаем, 10 в красную клетку.

И ВНИМАНИЕ! УЧИТЕ РУССКИЙ ЯЗЫК! ПО РЕШЕНИЮ ВАШЕЙ ЗАДАЧИ, Я ОПРЕДЕЛИЛ ЧТО ФРАЗА «Вы продаете пять кроликов из клетки, которая слева от вас, а половину остальных пересаживаете в красную. » НЕПРАВИЛЬНО ПОСТРОЕНА! ПРИ ДАННОМ ВАМИ РЕШЕНИИ ОНА ДОЛЖНА ЗВУЧАТЬ ТАК: «Вы продаете пять кроликов из клетки, которая слева от вас, А ПОЛОВИНУ ОТ ОСТАВШИХСЯ пересаживаете в красную».
Задача зависит от построения в ней слов. Будьте внимательнее!

Оставлен Александр Пнд, 04/30/2012 — 09:24

«1. В зеленой вдвое больше, чем в желтой. Это значит, что в зелёной чётное количество кроликов.»

Все абсолютно верно. Да, в желтой может быть как четное, так и нечетное число, но в зеленой четное точно. Из следующего утверждения понятно становится, что в желтой может быть только нечетное количество, т.к. мы убираем 5 и делим на два (не из красной, т.к. в нее перекладываем, но и не из зеленой, т.к. там четное количество).

Оставлен Гость Пнд, 07/02/2012 — 12:08

«не из красной, т.к. в нее перекладываем»
А что в этом такого?

Пример, если надо:
В желтой 30, в зеленой 60, а в красной после продажи, например — нуль. Клетка освободилась, помыли её и посадили туда 45. Не вижу помех быть красной клетке слева.
При чём, так даже не важно, «остальных» ли в условии написать или «оставшихся».

Оставлен Анатолий Ухванов Пнд, 04/30/2012 — 11:40

  1. Фраза построена не неправильно, а неточно. То, что Вы имели в виду, надо было выразить такими словами: «Условия задачи сформулированы недостаточно точно и могут быть поняты двояко».
  2. Слова: ‘оставшиеся’ и ‘остальные’ — означают ровным счётом одно и то же, так что в такой формулировке можно было использовать любое из них, и смысл от этого не изменился бы.
  3. Требуемое уточнение условий задачи заключается в том, чтобы пояснить, что именно автор подразумевает под словом ‘остальные’ (или ‘оставшиеся’): оставшиеся в этой клетке, или оставшиеся в других клетках, или же оставшиеся всего, во всех клетках. Поэтому уточнённые условия выглядят так:

Вы продаёте пять кроликов из клетки, которая слева от вас, а половину оставшихся в этой клетке кроликов пересаживаете в красную.

Оставлен Гость Втр, 06/19/2012 — 20:35

«ОТ ОСТАВШИХСЯ» . не логично заменять «остальных» на «от оставшихся» (от оставшихся в живых ? или они добровольно остались? глупо не правда ли?)

Оставлен dghitman Ср, 06/20/2012 — 03:32

Слушай, во первых мы рассматриваем какой то случай, и, так как в этом случае удалось пересадить половину из КАКОЙ ТО клетки, то методом исключения можно понять, что это могла бы быть только желтая клетка

Оставлен Катя Втр, 05/01/2012 — 16:47

Если честно, то не смогла решить задачу без ответа. И еще. Люди вам не все равно правильно они написали или нет. ПРОТИВНО! И хватит капслочить.

Оставлен котей Ср, 05/02/2012 — 06:29

да с чего бы это? В желтой ведь тоже могло оказаться 10 кроликов.В условии ведь не стоит ,что в зеленой четное количество,а в желтой нечетное!

Оставлен Гость Пт, 05/04/2012 — 18:36

если от 10 отнять 5, то оставшихся 5 кроликов можно поделить 2,5 + 2,5. Одному кролику придёт упсс!.

Оставлен Гость Чт, 05/10/2012 — 12:22

Как по-мне количество не играет роли. По условию задачи , у нас Cпрашивают какая клетка слева от меня ? То есть по левую руку, если я стою лицом к клеткам. В условии есть «относительный порядок», то есть я узнаю, об существовании , что сначала есть ЗЕЛЁНАЯ , далее ЖЁЛТАЯ и далее неизвестная , потом говорят об критерии , а потом я узнаю , что есть КРАСНАЯ. Давайте установим *условный порядок* .
Порядок№1(как в задаче).Зелённый далее (З), Жёлтый (Ж), и неизвестный (он же пофиг , он же любоый другой , он же красный т оесть (К)).
то есть [З] [Ж] [К] — если я стою лицом к жёлтой , чтобы забрать кроликов а я знаю , что должен забрать кроликов из клетки слева от меня , то есть жёлтая или зелёная, то я остачу, а именно пересаживаю в (Красную), то слева у меня остаётся Жёлтая клетка.
вообще есть 6 вариантов расположения этих клеток.
это 123,132,213,231,312,321.

Оставлен Гость Чт, 05/10/2012 — 12:46

ЮМОР , если будет порядок
[Ж][З][К]- то ответ Жизнь Замечательных Кролей.
эТО ОКОНЧАТЕЛЬНЫЙ ПРАВИЛЬНЫЙ вариант , Я ТАК думаю ))

Оставлен Гость Чт, 05/10/2012 — 12:47

Как по-мне количество не играет роли. По условию задачи , у нас Cпрашивают какая клетка слева от меня ? То есть по левую руку, если я стою лицом к клеткам. В условии есть «относительный порядок», то есть я узнаю, об существовании , что сначала есть ЗЕЛЁНАЯ , далее ЖЁЛТАЯ и далее неизвестная , потом говорят об критерии , а потом я узнаю , что есть КРАСНАЯ. Давайте установим *условный порядок* .
Порядок№1(как в задаче).Зелённый далее (З), Жёлтый (Ж), и неизвестный (он же пофиг , он же любоый другой , он же красный т оесть (К)).
то есть [З] [Ж] [К] — если я стою лицом к жёлтой , чтобы забрать кроликов а я знаю , что должен забрать кроликов из клетки слева от меня , то есть зелёная, то я остачу, пересаживаю в (Красную), то слева у меня остаётся Жёлтая клетка. Когда я их посажу в красную , то слева от меня останется Жёлтая. Если я лицом , к красной , то всё равн омне брать их слева или в Ж или в З но всё равно нести в К, а значит при порядке
[З][Ж][К], слева останется Жёлтый клетка. Да и вообще раздел логика и рассуждения , да и название задачи Цветная. мне кажется , много времени уделили Вы цифрам товарищи
вообще есть 6 вариантов расположения этих клеток.
это 123,132,213,231,312,321.

ЮМОР , если будет порядок
[Ж][З][К]- то ответ Жизнь Замечательных Кролей.
эТО ОКОНЧАТЕЛЬНЫЙ ПРАВИЛЬНЫЙ вариант , Я ТАК думаю )). Удалите №1 и №3

Оставлен Гость Пт, 10/19/2012 — 13:12

«половина остальных» — оставшиеся кролики после взятия 5-и или половина «оставшихся» кроликов, непонятно

Оставлен Гость Втр, 12/25/2012 — 17:38

Ответ зеленая клетка слева.

Оставлен Гость Пнд, 01/28/2013 — 11:47

по-моему в условии лучше записать «а половину от оставшихся пересаживаете в красную». А то не совсем корректно получается)

Оставлен shadow_hawk Пт, 02/13/2020 — 08:02

Не КРАСНАЯ, т.к. в нее пересаживали кроликов ( мертвых не пересаживают, значит все были живы ).

Не ЗЕЛЕНАЯ, т.к, в ней ЧЕТНОЕ кол-во кроликов ( в двое больше — по условию ) а если из четного вычесть 5 и разделить на 2 не получим ЦЕЛОЕ число, а кроликов ПЕРЕСАЖИВАЛИ.

Ответ: ЖЕЛТАЯ ( слева ), т.к. брали кроликов именно из нее и она по условию СЛЕВА.

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

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

Есть 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-ную бутылку.

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

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

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

Хехе))) Как с задачкой-то? xD

прочитал то что думал 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 для случая нескольких дней – для достижения минимизации количества этих самых требуемых дней – предлагаю читателю в качестве упражнения – задача требует некоторого анализа, который выйдет за рамки короткого примечания в решении простой задачи).

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

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

Читайте так же:  Токийский гуль кролик