пятница, 3 января 2014 г.

Логическая задача про вино

В древности патриций решил устроить праздник. Для этого он приготовил 240 бочек вина. Но к нему пробрался 

злоумышленник и подсыпал в одну из бочек яду.
Злоумышленника сразу же поймали, и он на допросе рассказал, что если выпить вино с ядом, то человек погибнет в течение 24 часов.
У патриция есть 5 рабов, которыми он может пожертвовать.
Каким образом можно узнать в какой бочке яд? 
(если нельзя определить отравленную бочку, то каково минимальное количество "подозрительных бочек", от которых придется избавиться?)
До праздника осталось 2 дня, т.е. 48 часов.



А в этой задачке ответа я не дам! 
Подумайте и напишите.

31 комментарий:

  1. минимальное кол-во бочек, которые можно выбросить -48

    ОтветитьУдалить
  2. если 5 рабов выпьют вина, возможно 2^5=32 разных исходов. 240 = 8 * 32 - 16. Группируем бочки по 8 и нумеруем группы. Каждый номер представляем в виде двоичного числа (например 18 это 10010), даем пить каждому рабу из всех бочек данной группы, если "его" бит в номере равен 1. Двоичное число, где биты равны 1, если соответствующий раб умер, и 0, если он жив, будет равно номеру группы, где есть отравленная бочка.

    Через 24 часа у нас будет точно известна группа из 8 бочек, одна из которых отравлена. При этом обязательно останется хотя бы один живой раб, т.к. число 11111=255 больше максимального номера. Этому рабу можно дать вина из половины бочек, тогда точно будет отбросить только 4 бочки. Если останется в живых 2 раба, можно будет отбросить только 2 бочки, 3 или больше рабов - можно точно определить отравленную бочку.

    Итак, ответ: гарантировано можно локализовать отраву с точностью до 4 бочек, а если повезет - до 2х или даже 1й.

    ОтветитьУдалить
  3. 240\5 = 48 бочек на 1 раба, одна из этих групп по 48 отравлена =>1 из рабов умрет за 24 часа, останется еще 24 часа на 1 проверку. 48 бочек на 4 рабов теперь => 48\4 = 12 бочек на 1 раба один умрет => мин. кол-во 12 бочек

    ОтветитьУдалить
  4. Разделяем бочки на 6 групп по 40 в каждой. Каждому рабу по группе бочек на дегустацию. На одну группу бочек рабов не хватает, остается нетронутой. Ждем сутки. Если кто-то умер, то локализовали группу из 40 бочек. Если никто не умер, то берем на проверку нетронутую группу бочек. (в худшем случае остается 4 раба).
    Дальше действуем примерно так как описал Fabio
    Эти 40 бочек разделяем на 16 групп (8 групп по 3 бочки и 8 групп по 2) потому что у нас 4 раба (разряда). Присваиваем группам номера от 0 до 15. Номер группы представляем в двоичном виде, единички в разрядах означают, что этот раб дегустирует группу бочек
    пример:
    группа номер 0 в двоичном виде 0000 (следовательно никто не пьет)
    группа номер 5 0101 (пробуют нулевой и второй раб)
    группа номер 10 1010 (пробуют первый и третий)
    Потом следим за самочувствием рабов и выделяем отравленную группу бочек.
    в самом худшем случае выбросим 3 бочки, в самом удачном 1.

    ОтветитьУдалить
  5. Этот комментарий был удален автором.

    ОтветитьУдалить
  6. 5 рабов должны выпивать 2 бочки в час, если конечно хозяину не жалко вина, таким образом они выпьют все бочки в течение 24-х часов

    ОтветитьУдалить
  7. формула количества сочетаний из n по k : C = n! / (k! * (n-k)!)
    (взято отсюда http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 )

    из 5 по 1 = 120 / (1 * 24) = 5
    из 5 по 2 = 120 / (2 * 6) = 10
    из 5 по 3 = 120 / (6 * 2) = 10
    из 5 по 4 = 120 / (24 * 1) = 5
    из 5 по 5 = 120 / (120 * 1) = 1
    из 5 по 0 = 120 / (1 * 120) = 1

    Итого, общее количество уникальных сочетаний из 5 пронумерованных рабов, равно 32.
    Хочу подчеркнуть, что это чистое совпадение с 2 в степени 5.
    Считать нужно именно по сочетаниям, а не по степеням.

    День первый.

    Даём продегустировать одну бочку всем пятерым рабам.
    (Если умрут все пятеро, эта бочка точно отравлена)

    Даём продегустировать ещё по две бочки каждому сочетанию из 5 по 4.
    Таких сочетаний 5, значит ещё 10 бочек будет продегустировано.
    Всего, с учётом предыдущей дегустации распробовано 11 бочек.

    Даём продегустировать по 4 бочки всем сочетаниям из 5 по 3.
    Таких сочетаний 10, значит ещё 40 бочек на дегустацию, итого 56.

    Cочетаниям по 2 даём по 8 бочек каждой, соответственно 10 * 8 = 80
    Итого, 136 бочек в работе.

    сочетаниям по 1 даём по 16 бочек каждой, это ещё 5 * 16 = 80.
    Итого, в первый день будет продегустировано 216 бочек.
    Нетронутыми останутся 240-216 = 24 бочки.


    День второй, решающий.

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

    Если умерли 4 раба, то у нас остаётся 2 подозрительные бочки и 1 живой раб.
    Как определить отравленную бочку в этом случае, надеюсь, всем понятно.

    Если умерли 3 раба, мы подозреваем 4 бочки и имеем 2-х пьяных рабов.
    Первую бочку пробуют оба раба, вторую первый раб, третью - второй раб, четвёртую - никто.
    Через сутки мы точно определим, в какой бочке яд.

    Если умерли 2 раба, на скамье подсудимых оказываются 8 бочек и 3 живых свидетеля.
    Если умер 1 раб, мы судим 16 бочек судом из 4 присяжных.
    Если никто не умер, значит яд в одной из 24 нетронутых бочек и все 5 рабов живы.

    Три последних случая подробно не буду разбирать, поскольку мы поступаем по тому же алгоритму, что и в первый день, но с учётом изменившегося n.

    Вуаля, мы определили отравленную бочку абсолютно точно, и выкидываем только её.

    ОтветитьУдалить
  8. делим бочки на 5 груп по 48
    каждый раб пьет и з своей группы из соседних подгрупп разбитых на 4 подгруппы.

    через сутки умрет трое и подозрительными будет 12 бочек.

    каждый пьет из своей группы из 6 бочек и одной из половин другой группы.

    ответ - 3

    ОтветитьУдалить
  9. 5 рабов 48ч. смерть через 24ч. то есть есть время для 2 подходов пробуют из 1 бочки каждый таким образом Патриций уверенно может подать на стол 10 бочек вина возможно этого не хватит но так гости останутся в живых избавляться от остальных бочек не выгодно после праздника можно проверить остальные

    ОтветитьУдалить
  10. Хех... все только рабов травят:( а м...ка который отравил? значит 6 подопытных:)

    ОтветитьУдалить
  11. Тут может быть несколько вариантов:
    1. давать пить по немногу из всех бочек злоумышленнику и надеется что н узнает то бочку куда подсыпал яд. По идее он должен был оставить какой нибудь знак на нем.
    2. Логически яд смертельный для человека смертельный и для животных можно использовать цыплят для определения зараженной бочки
    3. Можно осмотреть бочки может попытаться найти следы вскрытия бочки
    4. Но и математический 8 подозрительных бочек

    ОтветитьУдалить
  12. Разделим бочки на 5 групп. В каждой группе будут по 1 рабу. Каждый раб из каждой группы будет выпивать вино из каждой бочки с интервалом в 5 минут. Затем узнаем какой раб и из какой группы умер и через какое время после приема 1 бочки. Затем от этого времени отнимаем 24 часа умножаем на 60 и делим на 5 и умножаем на номер группы раба тем самым получаем номер бочки которая отравлена.
    Отпишите, правильно решил или нет :)

    ОтветитьУдалить
    Ответы
    1. привет , пожалуйста, я хочу, чтобы ты обращаться ко мне , его срочно. moopata2@gmail.com или на притон , или скайп pecmosg . порадовать своих неотложных и наилучшие пожелания
      privet , pozhaluysta, ya khochu, chtoby ty obrashchat'sya ko mne , yego srochno. moopata2@gmail.com ili na priton , ili skayp pecmosg . poradovat' svoikh neotlozhnykh i nailuchshiye pozhelaniya

      Удалить
  13. Делим бочки на 10 груп (240/10=24). Каждому рабу по 2 групы (2*24=48).
    Опредиляем яд по групам. То-есть минимальное количество 24 бочки.

    ОтветитьУдалить
  14. Каждый раб должен попробовать
    240 бочек / 5 рабов = получаем 48 отравл. бочек 24 часа
    48 бочек / 4 рабов = получаем 12 отравл. бочек 24 часа

    За 48 часов 240 - 12 = 228 бочек хорошего вина. и 12 отравленных и 3 живых раба)

    ОтветитьУдалить
  15. Этот комментарий был удален автором.

    ОтветитьУдалить
  16. Этот комментарий был удален автором.

    ОтветитьУдалить
  17. 48*60=2880минут/240бочек=12минут на бочку, присваиваем каждой бочке номер, записываем на ней время питься и по прошествии 24 часов, если злоумышленник(а спаиваем именно его) не умер ставим на бычке галочку, если умер то крестик, так убив 1го злоумышлинника получаем бочку с ядом, и вероятно с противоядием(ну он же себе не враг и когда будет загибаться то скажет где он), а если нет то и черт с ним, а рабов еще покупать потом, в общем в лучшем случае обойдемся без потери бочек, в худшем с потерей одной - так думаю более точно описал то, что удалил ранее :) если с рабами то со сдвигом в час получаем минус 1го раба и 2 бочки( ну никто не мешает и злоумышлинника использовать, так что вариантов уйма). Если со сдвигом в 24 часа то все печально...

    ОтветитьУдалить
    Ответы
    1. Сори за отсутствие запятых в некоторых местах.

      Удалить
  18. Этот комментарий был удален автором.

    ОтветитьУдалить
  19. Ответ : минимально- 6 бочек!!

    ОтветитьУдалить
  20. Итак на 1 раба- 48 бочек.Каждый раб дегустирует свои 48 бочек + 16 (1/3) соседа. Через 24 часа остаются 3 раба и 16 бочек. По 5 бочек на одного + еще 1 бочка. Дегустируют 5 своих и +1 соседа.
    Через 24 часа либо 2 живых раба + 5 бочек, либо 1 раб и 1 отравленная бочка.

    ОтветитьУдалить
  21. рабы пробуют по 2 бочки вина каждый час, после того как все бочки будут испробованы остается подождать до смерти одного из рабов, после чего выкинуть те 2 боки что он пробовал за 24 часа до смерти

    ОтветитьУдалить
    Ответы
    1. На пробу всех бочек уйдет 24 часа, после чего остается достаточно времени чтобы выявить те 2 бочки

      Удалить
    2. И да, ребята, смотрите проще на мир)

      Удалить
  22. Этот комментарий был удален автором.

    ОтветитьУдалить
  23. Ответ: 8 бочек.
    Вино делится на шесть частей по 40 бочек. Из пяти групп каждому рабу дается выпить по 40 глотков вина. Если кто-то умер, то дальше рассматривают ту группу бочек, из которой пил. На случайность полагаться не будем, поэтому предположим, что один раб отравился. Далее 40 бочек делим на 5 и даем выпить 4 рабам. Выходит, что минимально допустимое количество бочек 8. Ну а минимально возможное, если первый раз никто не отравился - 7.

    ОтветитьУдалить