Снова свиньи и ведра

Опубликовано Feb 5, 2013 в Олимпиадные задачи | 5 коммент.

,

Снова свиньи и ведра

Очень популярным в свое время оказался пост, посвященный решению задачи  про поиск ведра с ядом с помощью свиней.

В последнем комментарии автора Alehandro предложена весьма интересная модификация задачи и ее дальнейшее развитие. Теперь условие формулируется так.

Имеется 1000 ведер, одно из которых содержит яд, еще одно ведро содержит противоядие, а в остальных – просто вода. Если свинья выпьет яд, она умрет в течение 30 минут. Но ее можно спасти, если до того, как она умрет, ей посчастливится выпить противоядие. Инструкция по приему противоядия содержит такие сведения:

  • если выпить противоядие, не выпив при этом предварительно яд, то действие противоядия не обнаружится;
  • противоядие действует безотказно, вне зависимости через сколько времени ПОСЛЕ приема яда его выпили, если еще не померли;
  • противоядие, выпитое ДО приема яда, не действует.

Вопрос остается прежним: какое минимальное количество свиней нужно, для того, чтобы определить где яд, и где противоядие?


Автор публикации:

5 Коммент. : “Снова свиньи и ведра”

  1. При данных условиях необходимо за первые полчаса определить банку с ядом и за следующие полчаса банку с противоядием.

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

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

    Таким образом понадобится не более 20 свиней.

    Однако, если при определении банки с ядом, мы будем кодировать факт того, что двоичная цифра установлена в 1, тем что свинья умерла, тогда после определения номера банки с ядом у нас выживет минимум одна свинья (потому что для чисел от 1 до 1000 в двоичном представлении будет установлено максимум 9 бит, то есть умрут максимум 9 свиней). И эту свинью мы можем использовать для нахождения противоядия.

    Итого понадобится не более 19 свиней.

    • Решение выше не учитывает, что при обнаружении банки с ядом, в одну группу с ним могло попасть и противоядие, это происходит когда соответстующие цифры в двоичном представлении номеров банок с ядом и противоядием равны.
      Поэтому на данном этапе надо использовать по две свиньи на цифру: одна свинья пьет жидкость из банок слева-направо, а другая справа-налево и в этом случае, если одна из них умирает, то устанавливаем соответствующую двоичную цифру в 1 (умрет та свинья которая выпьет противоядие раньше чем яд), иначе если обе живы то в 0.
      В худшем случае после этого этапа остануться 11 свиней, которых достаточно, чтобы определить номер банки с противоядием, как это было описано выше.
      Поэтому всего необходимо 20 свиней.

    • Alehandro says:

      Предыдущая задача решалась так:
      Ищем – яд или его отсутствие, или 1 (наличие яда) или 0 (его отсутствие), основа двоичной системы исчисления.
      Есть десятичное число 1000 (количество вёдер), которое меньше 2-х в 10 степени = 1024 значит нам нужно 10 поросят за пол-часа.
      Но так как у нас по условию даётся час, то сначала проверяем 512=2^9 (два в 9-ой степени) вёдер, и если результат не достигнут, проверяем остальные вёдра теми же поросятами.
      Ответ задачи: нужно 9 (девять) поросят и за один час яд будет найден.

      Похоже, что и я тоже приближаюсь к разгадке усложнённой версии этой задачи. Для проверки в первые пол часа нужно взять 10 поросят, и проделать тест всех вёдер, составить таблицу истинности.
      Во вторые пол часа нужно взять последнее ведро и переместить его на первое место (сделать сдвиг по регистру, кажется это так называется) и тоже взять 10 поросят для проведения теста с новой комбинацией вёдер, которая никогда не повторит первоначальную и тоже составить таблицу истинности и только проанализировав эти две таблицы можно найти ответ на вопрос задачи.

  2. Alehandro says:

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

  3. Дзюблик Сергій says:

    Люди, що це ви робите? Невже вам сала не шкода, що попропадає? Чи їсти його можна, чи ні – хто зна, але аналізи заказувати – це теж не вихід (дорого й хто зна як зроблять ще). Виходячи з того, що про час в умові нічо не сказано і з метою мінімалізації втрат обійшовся би за даних умов 2-ма кабанчиками(самих худих вибирав, щоб не так кусала совість). Саме двома обійшовся б, а не 20-ма як дехто тут розумний пропонує. Кормлячи кожного з поросят щоразу з нового відерця з якого ще ніхто не пив,таки б знайшов оте отруєне і втратив би першого кабанчика. А далі щоразу готуючи спеціальне відро, в якому частка кожного неотруйного відра складала б 1/998 кормив би кабанчика, що залишивсяядом, спершу ядом, а далі відразу з відра з 998-кратною розбавленням антиотрути. А одне відро з тих неотруйних не використовував би і щоразу змінював. Тому з часом протиотрута не потрапить в загальну суміш і кабанчик здохне, однак укаже на відповідь до задачі. Дякую за увагу, ось і сказочці кінець – краще готуйте умови!

Оставить комментарий

Ваш адрес email не будет опубликован.


*