Задача про кроликов и яд.

    Есть 10 кроликов и 1000 бутылок с одинаковой на цвет и запах жидкостью. Но в одной из бутылок яд.
    Яд действует достаточно долго, но не дольше, чем 20 дней.
    Требуется на 21-й день сказать, в какой из бутылок яд.

    Upd. Спасибо неизвестным дарителям кармы, перенёс в занимательные задачи.

    Комментарии 29

      +10
      нумеруем все бутылки в двоичном коде. выстраиваем кроликов по порядку и даем им отпить из нужных бутылок в зависимости от того 0 или 1. ну и ждем 21 день.
      ясно что 10 кроликов хватит на 1024 бутылки :)
        +4
        Позволю себе пояснить ваш ответ :)

        Допустим у нас есть 4 бутылки и 2 кролика, тогда:

        кролики 1 2
        бутылки
        0 0 0
        1 0 1
        2 1 0
        3 1 1

        В этой таблице там, где стоят единицы кролики должны пить, т.е. 1-ый кроли пьет из 2,3 бутылки; а 2-ой из 1,3 бутылки.
        В зависимости от того какие кролики пострадают вычисляем исходную бутылку.
          0
          Как-то криво вставилась таблица :(
            0
            а если яд был в 4-й бутылке? ))

            скорее всего Ваша измененная задача про 4 бутылки и 2 кролика не имеет решения
            не даром в оригинале предлагается 1000 бутылок на 10 кроликов, а не 1024
              0
              если яд был в четвертой (3-ей, т.к. в таблице нумерация с нуля), погибнут оба кролика. Таблица действительно вставилась криво, но для понимания принципа это не мешает. Десятка кроликов с избытком хватит для тысячи бутылок.
                0
                Совершенно верно.

                Простите за офтоп, но как надо было правильно вставлять таблицу?
                Я выранивал пробелами, но несколько пробелов подряд почему-то заменились на один.
                  0
                  «почему-то» :)
                  это все таки браузер, а в html, несколько подряд идущих пробелов отображаются как один.
                    0
                    Попробуйте воспользоваться табличными тегами. Выравнивание пробелами вряд ли подойдет, даже если использовать pre — шрифт не моноширинной.
                      0
                      Выравнивание пробелами вряд ли подойдет, даже если использовать pre — шрифт не моноширинной.

                      Подойдет, моноширинный)
                      0
                      Ну например так (не забывая тыкать кнопку «предпросмотр»):

                      12      23      34
                       1       2       3
                      <pre>Таблица, выровненная пробелами</pre>
                  0
                  спасибо за объяснение :)
                –4
                Ну и задача в чем? Так как она поставлена, ну хватит и одного кролика, давать ему воду из всех бутылок подряд, на которой ему станет плохо в той и яд!
                Если яд начинает действовать ерез неизвестный промежуток времени, не более 20 дней, то так и нужно написать.
                  0
                  яд убивает на двадцать первый день :)
                    0
                    Точнее, яд убивает в любой момент до двадцати дней включительно после приёма.
                  +5
                  Требую добавления пункта к задаче — не один кролик не должен пострадать
                    0
                    Если кролик вдруг начнёт закатывать глазки, дёргать лапами и проявлять желание отправиться на небо, то можно дать ему антидот и посчитать за погибшего. А на бутылке с антидотом добавить чёрточку :)
                      0
                      >>Яд действует достаточно долго, но не дольше, чем 20 дней.
                      Я это расцениваю как в играх, отравили — пей антидот. Нет антидота, будет какое-то время(20 дней) отниматься hp, если hp много останешься в живых.

                      Так кролик должен умирает или нет? и действие яда видно сразу или только тогда когда кролик умрет?
                        0
                        Если без шуток, то подразумевается, что яд убивает насмерть. В первый день надо по искомому алгоритму отравить кроликов, и, выпившие из бутылки с ядом, будут умирать случайным образов в любой из 20 ближайших дней. Таким образом, к 21-му дню станет окончательно ясно, кто умер — тот отпивал из бутылки с ядом.
                      0
                      Главное, чтобы их можно было после этого есть! Если нет, звоню в гринпис!
                      0
                      Один шанс из тысячи, что ни один кролик не пострадает
                        +1
                        Это получается, если отравлена бутылка под номером 512, погибнет 9 кроликов из 10? Куда смотрит Гринпис…
                          +1
                          Такой вопрос задавали на собеседовании если не ошибаюсь в компанию AVIcode в Питере. Заставляет подумать)
                            –3
                            Задачка конечно интересная. Но как тест на собеседовании, ИМХО слабовата.
                            0
                            про двоичный код не подумал, т.к. не программист, а во на ум пришла ассоциация с рулеткой в казино, точнее с зонами на игровом поле: красное/чёрное, чёт/нечет и т.д.
                            т.е. действовать надо примерно так: первого кролика весь день поить только из чётных бутылок (сдохнет через месяц — значит яд в одной из чётных, не сдохнет — в нечётной)
                            второго кролика поить только из первых пятиста. Уже так уменьшаем кол-во угадываемых бутылок до 250ти.

                            прежде чем мучать третьего кролика, маркируем бутылки: половину чётных (250 штук) отмечаем красным маркёром, другую половину чёрным. Так же метим нечётные. после этого даём третьему кролику выпить «красный» коктейльчик, уменьшая количество неизвестных бутылок до 125.

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

                            Ну я если в задаче именно тысяча бутылок… то можно вместо 24х дополнительных бутылок подписать на тетрадном листочке «бутылка» и использовать его для ровного счёта, чтобы не держать их в уме.

                            Так же важно понимать, в каких дозах яд проявляет себя, т.е. сколько яду должен выпить кролик, чтобы по нему через 20 дней можно было сказать, что он отравился (там, чесаться начал, волосатость повысилась, и т.п.)
                            Ведь даже если кролику достаточно всего 5мл, то это значит, что каждому придётся споить за день 5 литров жидкости, причём не смешивая, чтобы не разбавлять яд, а по чайной ложечке из каждой их пятиста бутылок…
                              0
                              Если на всех кроликов яд действует за одинаковое время, то есть стратегия по сокращению потерь среди мирного ушастого населения.
                              Маркируем бутылки от 000 до 999. Соответственно значение разряда обозначает кролика.
                              В первый час кролики пьют бутылки по соответствию старшему разряду (так первый(нулевой) кролик пьет воду из первой сотни бутылок), во второй час — по среднему разряду, в третий — по младшему.
                              В итоге в какой то момент у нас начнут по очереди дохнуть кролики. Если по очереди сдохнут первый, второй и третий кролики, значит яд в бутылке 012.
                              В итоге максимальные потери — 3 ушастых… ;)

                              З.Ы. Если яд действует на кроликов по разному, то мы в худшем случае получим выбор из 6 бутылок. Что тоже неплохо. ;)
                                –1
                                g fdsg dsg
                                  +1
                                  Есть более изящное решение!
                                  Мысленно разместим бутылки по ячейкам куба 10x10x10 (всего 1000 ячеек — на каждую по бутылке).
                                  Расставим кроликов в ряд у одной из граней куба и пронумеруем их от 10 до 10. Каждый кролик выпьет из каждой из 100 бутылок, находящихся в вертикальном квадрате, перпендикулярном данному кролику. Повернем куб на 90 градусов по одной из осей и повторим операцию с отпиванием из 100 бутылок. И наконец, повернем куб на 90 градусов по другой оси и снова каждый кролик выпьет из 100 стоящих перед ним бутылок.
                                  Вот картинка для третьего кролика:



                                  Таким образом каждый кролик выпивает из 300 бутылок (на самом деле меньше, но для решения — не важно). На 21й день найдем от 1 до 3 охладевших тушек. По номерам кроликов легко найдем из какой бутылки они вместе выпили.
                                    0
                                    хотя это и и не так «айтишно», как двоичный метод из первого коммента, но это круто. еще и кролики экономятся.

                                    P.S.: а вы долго решали :)
                                      0
                                      Метод решения — неверный. Проблема в том, что эта бутылка будет не единственной.

                                      Предположим, погибло три кролика, за номерами 1, 2 и 3.
                                      Давайте на вашем же кубике дорисуем бутылки, которые выпили ещё 2 погибших кролика: бутылки первого кролика обозначим жёлтым цветом, бутылки второго — синим.



                                      Чёрным помечены бутылки, из которых пили все три погибших кролика, и больше никто.
                                      Их несколько, а значит — задача не решена.

                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                    Самое читаемое