23 янв. 2011 г.

Всё для людей!

Добрый день!

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

Задача про 240 бочек вина, 5 рабов и одного патрицияНо есть задачки, в которых мало найти хоть какое-то решение, а надо доказать его оптимальность (показать, что лучшего решения не существует). Например, в недавней задаче про тетраэдры в кубе спрашивалось, сколько правильных тетраэдров с ребром один можно поместить в единичный куб. Легко было понять, что влазит один, несложно догадаться, как разместить два, некоторые в комментариях предложили способ, как запихнуть три тетраэдра. Но у решающего на каждом из этих этапов нет уверенности, что он нашёл наилучшее решение. В самом деле, а вдруг как-то так можно повернуть тетраэдры, что влезет сразу четыре?

И тут у решающего возникает дилемма, как лучше дожимать задачу:
1) искать способ улучшить текущее решение,
2) доказывать, что лучшего решения не может быть (как в случае с тетраэдрами).

Соответственно, правильным может быть только одно действие из этих двух. И если не угадать (не поверить своей интуицию/опыту или поверить им тогда, когда они ошибаются), то можно потерять много времени, не продвинувшись к решению.

Ну а самые удачные задачки устроены так, что большинство людей постоянно делают неправильный выбор. Я это называю «способность задачи сопротивляться». Вроде бы ничего сложного нет, но мозг постоянно выбирает не то направление, из-за чего на поиск элементарного решения может уйти много времени.

Мне очень нравится следующая классическая задача, решая которую люди радостно выкрикивают «я решил!», бодро называют число, после чего слышат остужающее «можно больше». И это происходит несколько раз, потому что автор задачи запланировал несколько правдоподобных неправильных решений, на грабли которых все и наступают. Повторюсь, задачка элементарная, но хорошо продумана.

Метеорологи одного города предсказали, что через двое суток начнётся небывалая жара. Необходимо поддержать жителей города в такой трудный момент, поэтому мэр решил вывести на улицы 240 прицепов-цистерн с квасом. Этого должно было хватить, чтобы пережить неожиданный подарок природы. Но пятеро коварных врагов не только прокрались в тыл, но и отравили квас в одной из цистерн. Конечно, служба безопасности их поймала, но было уже поздно.

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

Вопрос: какое максимальное количество прицепов-цистерн кваса (но только заведомо без яда) можно выпустить на улицы через двое суток?


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

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

Хорошего вам завершения выходных!

73 комментария:

  1. 232 получилось. Можно больше?

    ОтветитьУдалить
  2. Анонимный23.01.2011, 10:45

    Если есть только один день, видимо, 232, потому что больше чем 5 бит информации из них извлечь нельзя, а способ найти 8 бочек, среди которых точно есть отравленная, есть. Про два дня еще подумаю.

    ОтветитьУдалить
  3. Анонимный23.01.2011, 10:58

    Этот комментарий был удален администратором блога.

    ОтветитьУдалить
  4. Уважаемый аноним, я скрыл Ваш ответ, чтобы он не мешал желающим дойти до него самостоятельно.
    Быстро Вы разделались с этой задачкой! :)

    ОтветитьУдалить
  5. Если я не ошибся, можно определить все 239 бочек без яда. И вроде этот способ подойдет даже, если бочек будет не 240, а 243.

    ОтветитьУдалить
  6. Felix, очень сильная подсказка! Можно долго гадать, чем замечательно число 240 (оно много чем замечательно), но вот для приведённой Вами границы всё становится ясным.

    ОтветитьУдалить
  7. В худшем случае, у меня получилось 236.

    ОтветитьУдалить
  8. У нас вроде есть минимум две итерации.
    Дальше - у нас есть 5 человек и "две пустышки" = 7 "проверяющих".
    соответственно мы можем разбиться все 240 бочек на 12 вариантов. (12 вариантов = 3*4). Итого 20 бочек на каждого. В результате на первой итерации умрёт в худшем сценарии один из них умрёт.
    Итого нужно из 20 бочек 4-мя человеками отсеять максимум за одну итерацию.Итого по старой схеме: 4 человека + 2 пустышки. = 6 проверяющих. Или 9 вариантов. И в самом худшем сценарии необходимо будет отбросить три бочки. Итого в самом плохом случае мы выкатим 237 бочек.

    ОтветитьУдалить
  9. Не читая комментарии, есть способ определить для всех 240 бочек имея 5 смертников и 2 суток. Если правильно, напишу ход рассуждений через 2-е суток. :-)

    ОтветитьУдалить
  10. Анонимный23.01.2011, 14:59

    Догадываюсь, что было в скрытом ответе.
    Задачка очень простая - для программиста :) Очень легко за 2 пробы найти единственную отравленную бочку из 240 или даже из 243.

    ОтветитьУдалить
  11. Очень сильный - значит, для гарантированной смерти в течении 24 часов достаточно любой дозы?

    ОтветитьУдалить
  12. У меня тоже получилось то, что за два дня можно проверить 243 бочки. Самое интересное тут - в какой пропорции смешивать квас из разных бочек.

    Отложим 32 бочки на случай того, что никто не умрёт.
    Если умрёт один - пять вариантов, на второй день можно будет проверить 16 бочек, итого 80 бочек.
    И так далее, умрут четверо - пять вариантов, на второй день можно проверить 2 бочки, итого 10 бочек.
    Просуммировав, получаем 242 бочки. Содержимое оставшихся даём всем гадам: все умрут - выкатываем 242 бочки.

    ОтветитьУдалить
  13. Анонимный23.01.2011, 15:27

    Вопрос не очень корректно поставлен. Максимально-239,гарантированно 238.(догадался после чтения комментариев)

    ОтветитьУдалить
  14. monkegoist, Vladimir Leonenko, можно больше.

    Camill, да, достаточно любой дозы.

    Уважаемый аноним, возможно, это не некорректный вопрос у меня, а неполное решение у Вас. Впрочем, гарантированные 238 цистерн - это уже немало.

    ОтветитьУдалить
  15. Пока что знаю, как можно гарантированно в худшем случае указать на 3 потенциально отравленные бочки бочки из 240, т.е. 237.

    ОтветитьУдалить
  16. Анонимный23.01.2011, 16:14

    Самое интересное тут - в какой пропорции смешивать квас из разных бочек.

    Со смешиванием как раз все просто. Каждый заключенный отвечает за отдельный разряд номера. Значит, выбираем группы бочек, номера которых в соответствующем разряде содержат 1.

    ОтветитьУдалить
  17. Думаю, на практике всех устроит наиболее очевидный вариант:
    Сначала делим бочки на 6 частей, каждому по 40 и 40 в запасе. Потом заведомо отравленные 40 бочек делим еще на 4 (если один умер) или 5 (если никто не умер) групп, и получаем максимум 10 бочек, которые гарантированно отравлены (от остальных никто не умер, от этих 10 - точно умер)

    Но чисто математически очевидно, что предел будет 240/3^5 = 240/243 < 1, т.е. возможно точно выяснить отравленную бочку.

    ОтветитьУдалить
  18. 3^5 потому, что каждый заключенный кодирует один троичный бит - он может умереть на первый день, на второй день или выжить.

    ОтветитьУдалить
  19. Анонимный23.01.2011, 21:49

    По идее за два дня при таких ресурсах можно было бы протестировать не более, чем n=243 бочек.
    Следовательно, выпустить на улицы можно будет (n - 1) заведомо неотравленных бочек.
    А на самом деле выпустить можно (n - 1 - то_количество_что_они_выпили_для_тестов).
    Следовательно для поставленных условий в ответе будет "меньше, чем 239 полных бочек".

    ОтветитьУдалить
  20. Анонимный23.01.2011, 22:19

    Спасибо! Очень понравилась задача. Правда, без подсказки о том, что максимум можно проверить 243 = 3^5 бочки, наверное бы не решил.
    Кстати, я решал геометрически и в процессе решения открыл для себя, что в многоугольнике с n сторонами содержание фигур с k сторонами, где (0 <= k <= n) подчиняется биномиальному распределению :) Ну и вообще, в процессе решения часто находилась связь с треугольником Паскаля.

    ОтветитьУдалить
  21. Поздновато увидел задачу. Ну да ладно.
    Приведу вариант рассуждений.
    Пусть в первый день каким-то образом террористов напоили квасом.
    Ко второму дню возможны варианты:
    1) Выжили все. Значит яд в тех бочках, откуда никто не пил.
    С помощью 5 террористов за оставшийся день можно различить 2^5=32 группы бочек.
    2) Выжило 4. Яд в тех бочках, из которых пил только умерший.
    За оставшийся день мы можем различить 2^4=16 групп бочек, а с учётом того что в первый день мог умереть любой из 5, то общее число различаемых групп 5*16=80.
    3) Если выжило 3, то по аналогичным рассуждениям мы сможем различить 10*2^3=80 групп.
    10 - число комбинаций 2 умерших из 5 (бином Ньютона).
    4) Для 2 выживших - 10*2^2=40 групп.
    5) Для 1 выжившего - 5*2^1=10 групп.
    6) Если все умерли - различима 1 группа.

    Всего 32+80+80+40+10+1=243 групп, чего нам хватит, чтобы определить отравленную бочку. Для этого во все группы помещаем по 1 бочки, ну а в 3 оставшиеся 0 бочек.

    ОтветитьУдалить
  22. Анонимный24.01.2011, 2:12

    Назовем гадов-отравителей Abe, Ben, Cid, Dan и Erl, или просто без лишних церемоний A,B,C,D и E.

    Бочки пронумеруем в троичной системе от 00001 до 22220 - всего 240 бочек. Затем дадим злодеям попробовать холодного кваску согласно их именам и номерам бочек. Положение каждой троичной цифры в номере каждой бочки подскажет нам кому и когда дать попробовать кваску из этой бочки.

    Например, Abe и Erl получать квас из бочки 12021 в начале первых суток, а Ben и Dan - в начале вторых суток (если конечно они доживуть до этого времени) , а Cid вообще не получит дозу из этой бочки.

    Кто и когда умрет укажет однозначно на бочку с ядом.

    Артур Бараов

    ОтветитьУдалить
  23. 240=3^5 я сразу увидел, но как это использовать понял не сразу. В начале я получил 232, а потом заметил, что второй день при этом никак не используется. Тут до меня дошло что можно по второму разу использовать выживших и через пару минут я понял как к этому приделать троичную систему счисления.

    ОтветитьУдалить
  24. Сам дошел до логики ответа, содержащейся в приведенных в большом количестве выше комментарииях. Если это решение верное и единственное, то не могу сказать, что задача "элементарная" (для непрограммистов и не любителей теории вероятностей), и не могу сказать, что в ней какая-то изюминка (впрочем, возможно, мне так кажется только после того, как я ее решил).

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

    ОтветитьУдалить
  26. Хочу заметить, что 243 в качестве ответа, неверно. т.к. по условию задачи есть всего 240 бочек. Хотя, конечно, в качестве подсказки подходит, это очень сильная подсказка, вместе с подсказкой использовать троичную систему счисления.

    Также согласен с Алексеем, что задача вовсе не "элементарная". Только не теория вероятности, а теория информации.

    ОтветитьУдалить
  27. Анонимный25.01.2011, 1:36

    Ну если придумать способ, как проверить 243 бочки, то он и с 240 сработает. Во всяком случае тот, что я придумал (я писал выше, что решал геометрически). А вот подсказка про троичную систему мне бы никак не помогла :)

    ОтветитьУдалить
  28. Работает, но это не является ответом на поставленный вопрос. :-) Когда вас спрашивают сколько будет 1+1, вы конечно можно объяснить как складывать любые комплексные числа, и поняв это, действительно можно сложить, 1+1, но, согласитесь, что-то здесь не так.

    Лично я пошёл другим путём. Для начала я решил совсем другую задачу: "У меня есть 2 преступника, 1 итерация и кто-то гарантировано должен умереть. Какое максимальное число бочек может быть различено?" Очевидно, 2 бочки могут быть различены. Можно ли больше? Если дать каждому выпить по 2 бочке, т.е. всего есть 4 бочки (в стороне мы не может ничего оставить по условию новой задачи), то после 1 итерации кто-то умрёт, значит в 2 других бочках нет яда. Теперь отменим требование о смерти. Тогда мы можем иметь 6 бочек, по 2 бочке на смертника и 2 в стороне. Если никто не умер, значит мы нашли 4 бочки без яда, исключая те которые мы отложили в сторону. Если кто-то умер, мы нашли другие 4 бочки, исключая те из которых пил умерший. Забегая вперёд, отмечу, что решение с помощью кодирования бочек даёт также 4, каждый испытуемый может умереть или не умереть после 1 итерации, таким образом он даёт два бита информации, всего 2*2=4 бита информации. Меня это поначалу несколько смутило и я поэтому нашёл сначала ответ 232, который выглядит довольно правдоподобно. На практике, я бы всё-таки сделал бы именно так.

    Итак, возвращаясь к первоначальной задаче, нужно поделить 240 бочек на 6 груб по 40 бочек. Дать каждому арестанту выпить кружку из смеси из определённой группы и одна группа останется нетронутой. Если кто-то умрёт, мы будем знать, что яд находится в одной из 40 бочек "его" группы. У нас останется ещё 4 арестанта и 1 итерация. Поделив 40 бочек, аналогично, на 5 групп по 8 бочек, повторим эксперимент. Если опять кто-то умрёт, значит яд будет где-то в "его" 8 бочек, тем самым в 232 остальных бочках яда нет. Если во-второй итерации никто не умрёт, значит яд в оставшихся 8 бочках. Выглядит, как будто-бы улучшать нечего? Но что будет если в-первой итерации никто не умрёт? Тогда яд находится в отложенных в сторону 40 бочках, у нас есть 5 арестантов. Но определить яд "с точностью до 8 бочек" можно имея только 4 арестанта! Имея 5 арестантов можно в этом случае добиться большой точности, хотя бы разделив на 5 групп по 6 бочек и 4 бочки отложив в сторону (даже тут видно отсутствие симметрии). И вот тут меня осенила мысль, а почему у меня из каждый бочки пьёт максимум 1 человек в каждой итерации? Почему бы не пить нескольких арестантам? Уже поздно, поэтому далее лишь схематично. Далее нужно также учесть итерацию... Вернувшись к примеру с 2 арестантами я увидел, что там улучшения за счёт того, что из бочки пьют несколько арестантов нет. Однако, увеличив количество арестантов и итераций, а также запутавшись кто откуда пьёт я "вдруг" увидел, что...это же биты информации и всё стало очень просто.

    ОтветитьУдалить
  29. Анонимный25.01.2011, 2:57

    Ну почему не является? Ведь если указать способ, как проверить все 240 бочек (а он почти не отличается от проверки 243), то, т.к. в одной бочке заведомо есть яд, то ответ на вопрос - 239. Да, решал я не самым рациональным путем, т.к. я сначала решил аналогичные задачи для 2, 3 и 4 смертников и 9, 27 и 81 бочки соответственно, но в результате вполне смог получить ответ на вопрос задачи.

    ОтветитьУдалить
  30. Анонимный25.01.2011, 14:04

    УРА! напоил арестантов, только боюсь лопнут они раньше чем наступит 2-й день. У меня выходит: за день они выпьют 405, необходимых для отравления, доз. Если доза стакан, выходит 81 литр; да еще и одну бочку испортили.... Предлагаю добавить пару бочек в условие раз уж засуха настолько сильная :-).

    ОтветитьУдалить
  31. Уважаемый аноним, яд сильный, поэтому можно давать пить по маленькому глоточку. Тогда и потери на тестировании кваса будут ничтожны.

    ОтветитьУдалить
  32. Анонимный27.01.2011, 13:40

    рассуждал примерно так :
    На второй день необходимо оставить не более того количества бочек, которые можно однозначно определить оставшимися в живых смертниками.
    т.е. если остается 5 арестантов, то бочек должно быть не более 32; 4 = 16 ; 3 = 8 ; 2 = 4 ; 1 - 2 ; 0=0 . А значит ценность живого заключенного тем больше чем больше бочек останется непроверенными к началу второго дня . Следовательно если арестанту суждено отравиться в первый день, то он должен отсеять максимум бочек . Значит если из одной бочки дать выпить всем арестантам, в случае отравления однозначно определяется бочка с ядом, одновременно сформировать различные 4-ки , например 1,2,3,4 и 2,3,4,5 и т.д. тройки двойки и отдельно каждому дать пробу из соответственно ( 2, 4, 8, 16 ) еще непроверенных бочек одновременно , таким образом при отравлении 4-ки мы однозначно определяем пару бочек и для анализа на следующий день оставляем 1-го живого, не входящего в отравившуюся 4-ку, аналогично с тройками двойками и индивидуальными порциями. Итого в первый день проверяется 211 бочек . на второй день остается максимум 29 . Дальше просто. И совершенно необязательно использовать троичную систему. Можно конечно усложнить (упростить). Но ведь сказано что задача элементарная.

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

    ОтветитьУдалить
  34. Анонимный27.01.2011, 23:14

    получается 233 с гарантией.

    ОтветитьУдалить
  35. Анонимный28.01.2011, 0:22

    Разделив 240 бочек на пятерых получим по 48 бочек на каждого, чтобы каждый получил дозу со свих 48 бочек плюс по 8 бочек каждого другого, т.е. 48 бочек каждого поделим еще на 6 частей (т.е.по 8 бочек). В худшем случае умирают 2 человека и у нас остается 8 бочек и 3 человека. (если умирает 1 чел. остается 8 бочек и 4 человека). На 2-ой день: делим 8 бочек на троих, т.е. двум по 3 бочки и одному 2 бочки. Каждый выпивает свои бочки плюс по одному соседних... на второй день с помощю 3 людей можно было бы определить единственную отравленную бочку даже с 12 бочек.

    Заурби Бараов.

    ОтветитьУдалить
  36. Анонимный28.01.2011, 8:35

    ммм не совсем понятно "48 бочек каждого поделим еще на 6 частей", а как между оставшимися 4-мя поделить эти 6 частей, чтобы при этом погиб максимум 1, ведь еще один погибнет однозначно, выпив свои отравленные 48 ?

    ОтветитьУдалить
  37. Анонимный28.01.2011, 9:29

    Andrey писал : "В начале я получил 232, а потом заметил, что второй день при этом никак не используется. " можно ход рассуждений, каким образом за один день достоверно определить одну из 232 бочек? С трудом верится, что такое возможно.

    ОтветитьУдалить
  38. Мы можем разделить бочки на 32 группы по 7-8 бочек в каждой. Теперь каждый отопьет из группы, в двоичной записи номера которой на i-том месте стоит 1. Тогда умершие арестанты закодируют номер группы в двоичной системе счисления.

    ОтветитьУдалить
  39. Анонимный01.02.2011, 12:33

    Хочу предложить еще один вариант решения:
    Каждый человек получает свой номер (1,2,3,4,5),
    бочки ставим в 4 ряда (по 60 ) и получают свои номера, на каждую бочку первого ряда ставим (1), соответственно второго ряда (2) и (3) и (4).Вначале первых суток первые 4 человека пробуют кваску со своих рядов. Через 24 часа должень умереть один из них (допустим человек под №1, который пил из ряда бочек под номерами (1).
    Однако мы не сидим и не ждем целых 24 часа пока он умрет,после этой пробы, скажем через 1 час, мы приступаем к следующим пробам.Каждый из этих 4-х пробуют теперь перпендикулярно ряду, при этом подключаем 5-го человека, он будет пробовать только с тех бочек, где получают совпадения номеров человека и бочки (т.е. человек под №1 не будеть пить дважды с бочек под номерами(1), и другие тоже). И если мы будем через каждые 1 час пробовать следующую партию, то весь процесс займет 15 часов.
    Т.е. через 24 часа мы узнаем № умершего человека и номер ряда бочек с ядом, и следующие кажддый 1 час просто исключаем по 16 бочек без яда пока не умрет второй человек.

    Заурби Бараов.

    ОтветитьУдалить
  40. Заурби, спасибо за интересные мысли. Но я не понимаю это решение. Можете написать подробнее?

    ОтветитьУдалить
  41. Анонимный02.02.2011, 22:09

    Каждый человек получает свой номер (1,2,3,4,5),
    бочки ставим в 4 ряда (по 60 бочек ) и получают свои номера, на каждую из 60 бочкек первого ряда ставим (1), соответственно второго ряда (2) и (3) и (4).Вначале первых суток первые 4 человека пробуют кваску со своих рядов.Человек под №1 пробует ряд бочек под номерами (1), человек под №2 пробует ряд под номерами (2),
    №3-(3), №4 - (4). Через 24 часа должень умереть один из них и указать на ряд бочек с ядом.
    Однако мы не сидим и не ждем целых 24 часа пока он умрет,после этой пробы, скажем через 1 час, мы приступаем к следующим пробам.Каждый из этих 4-х пробуют теперь перпендикулярно ряду, при этом подключаем 5-го человека, он будет пробовать только с тех бочек, где получают совпадения номеров человека и бочки (т.е.человек под №1 пробует бочки (2),(3),(4), а бочку (1) пробует человек под №5. человек под №2 пробует бочки (1),(3),(4), а бочку (2) пробует человек пд №5. человек под №3 пробует бочки (1),(2),(4), а бочку (3) пробует человек пд №5. человек под №4 пробует бочки (1),(2),(3), а бочку (4) пробует опять человек пд №5). Это была 2-ая операция, таких операций будет 15 с интервалом 1 час. Т.е. через 24 часа мы узнаем № умершего человека и номер ряда бочек с ядом, и следующие кажддый 1 час просто исключаем по 16 бочек без яда пока не умрет второй человек. Как умрет 2-ой человек, № второго умершего человека укажет на бочку с ядом.

    Заурби

    ОтветитьУдалить
  42. Анонимный02.02.2011, 23:06

    Похоже Заурби не учел, что яд действует не через 24 часа ровно, а в течение 24 часов (может через 10 минут, а может и через 24 часа).

    Поэтому в конце первых суток, в принципе, мы можем обнаружить не одного мертвеца а 4 или даже 5. Следует также помнить, что условия задачи не гарантируют, что яд действует через определенное, хотя и неизвестное, время: яд может действовать быстрее на одного арестанта, чем на другого.

    ОтветитьУдалить
  43. Заурби, теперь Ваше решение понятно.
    Аноним ниже верно заметил, что на разных людей яд может действовать за разное время. Одно известно точно - не позже чем через 24 часа после приёма яд убивает. Но если все хилые, то он их за первые 15 минут выведет из тестирования.
    Поэтому вполне возможно, что через час после начала решения задачи у вас не останется ни одного добровольца для тестирования бочек, но всё ещё не будет ясно, где яд.

    ОтветитьУдалить
  44. Анонимный03.02.2011, 13:57

    Похоже Заурби не учел, что яд действует не через 24 часа ровно, а в течение 24 часов (может через 10 минут, а может и через 24 часа).
    Поэтому в конце первых суток, в принципе, мы можем обнаружить не одного мертвеца а 4 или даже 5. Следует также помнить, что условия задачи не гарантируют, что яд действует через определенное, хотя и неизвестное, время: яд может действовать быстрее на одного арестанта, чем на другого.



    В конце первых суток, если даже яд подействует быстрее, мы никак не сможем обнаружить ни 4, тем более 5 умерших, поскольку пробуют каждую бочку только 2 раза (2 человека). Ну а если яд действует ранше 1 сутки, то нам будет просто легче определить эту бочку, просто мы используем крайний срок действия. Ну а то что яд такой коварный, и действует на разных арестантов по разному, я не увидел в условиях задачи.
    Я так думаю, что мы просто должны показать как можно больше, не похожих друг на друга, решений.

    Заурби.

    ОтветитьУдалить
  45. Анонимный03.02.2011, 16:30

    У меня получилось 228.
    240 бочек делим на 5, по 48 бочек на человека.
    Через сутки 1 умирает от яда.
    48 бочек, где точно яд делим на 4 человека, по 12 бочек на человека.
    Через сутки один умирает от яда и мы знаем те 12 бочек где яд.
    Вот эти 12 бочек горожанам давать нельзя.
    Итого 240-12=228

    ОтветитьУдалить
  46. Заурби, спасибо за интересное мнение! В самом деле, мы хотим увидеть как можно больше разных осмысленных взглядов на решение этой задачи. И Ваше решение может быть очень эффективным для некоторых других задач.

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

    Получается, что смерть двух тестеров указывает нам на группу из 30 бочек (так как в каждой паре пересечение множеств бочек равно 15).

    В любом случае, спасибо за интересный взгляд на эту задачу.

    ОтветитьУдалить
  47. Анонимный03.02.2011, 20:03

    Илья, я делал ставку именно на промежуток времени между пробами. Если мы не можем воспользоваться этим показателем, действительно мое решение не имеет смысла. А если можем воспользоваться, то в моем случае не смогут умереть сразу 2 человека. После того как умер 1-й человек мы сразу будем знать в каком ряду именно находится бочка с ядом.После первой смерти, если мы давали пробовать через каждые 1-час, подводить итоги тоже будем каждый час.

    Заурби.

    ОтветитьУдалить
  48. Илья, решение, которое предложил Заурби, будет работать, если яд действует с фиксированным и одинаковым интервалом для всех. Действительно, согласно этому решению, проба с ядом будет предложена только двум и причем в разное время, поэтому оба не могут умереть одновременно. Время прошедшее с начала первых суток до первой смерти дасть нам период действия яда. Три куска информации - период действия яда, кто и когда умер вторым - конечно же укажет однозначно на бочку с ядом.

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

    Например, дайте первому арестанту коктейль из всех бочек. Через одну минуту начинайте давать второму арестанту пробу из каждой бочки с интервалом в одну секунду. Смерть первого злодея даст период срабатывания яда, время смерти второго минус этот период укажет на бочку с ядом.

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

    ОтветитьУдалить
  49. Хорошо, как только враги воспользуются ядом, который действует фиксированное время (не глядя на вес потребителя), Заурби получит себе несколько батраков :)

    ОтветитьУдалить
  50. Вот здесь http://alexsmail.blogspot.com/2011/01/blog-post_26.html я довольно детально разобрал решение задачи.

    ОтветитьУдалить
  51. Добавил решение с фиксированным периодом действия яда, довольно оригинально.

    ОтветитьУдалить
  52. alexsmail, спасибо за качественный разбор!
    Рекомендую его всем, кто хочет лучше понять, как решать подобные задачи!

    ОтветитьУдалить
  53. Вероятно, я чего-то не понимаю, но разве возможно проверить 243 бочки?
    Ведь, когда мы кодируем в троичной системе исчисления, то не учитываем, что некоторые преступники на второй день уже могут быть мертвы. К примеру, бочка с номером 21101 подразумевает, что преступник А выпивает из нее на второй день, однако он может быть уже мертв.

    ОтветитьУдалить
  54. Да и вообще, проверка бочки 11111 означает (в худшем варианте, то есть когда именно в ней находится яд) смерть всех преступников и отсутствие второй итерации как таковой :)

    ОтветитьУдалить
  55. truefalse, да, Вы не полностью поняли решение.
    Троичный бит может принять три состояния (0, 1 или 2), а преступник тоже может принять три состояния (отравиться в первый день, отравиться во второй день, не отравиться). Как видите, состояний столько же, поэтому и проверять можно таким же образом.

    Например, в первый день i-ый преступник пьёт из тех ёмкостей, i-ый бит в троичной записи которых равен 1. Соответственно, отравившиеся в первый день чётко указывают нам номера битов искомой бочки, равные единице.

    Например, если отравились второй и четвёртый, то мы знаем, что номер бочки с ядом имеет такую троичную запись: "?1?1?" (причём на месте знака вопроса может быть только 0 или 2).

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

    Допустим, во второй день отравился только 3-ий. Это значит, что номер ёмкости с ядом имеет номер "?121?", причём на месте знака вопроса может стоять только "0". Другими словами, так мы точно узнаем номер искомой ёмкости.

    Что касается Вашего второго вопроса, то тут ещё проще: если яд был в бочке с номером 11111, то в первый день все преступники отравятся. Но мы точно будем знать, где яд, поэтому второй день уже будет не нужен.

    Пишите, если у Вас остались вопросы.

    ОтветитьУдалить
  56. Анонимный15.02.2011, 11:32

    Хороший квест. Предлагаю решение в общем виде.

    Пусть R(x,y) - количество бочек, которые можно протестировать за y дней при помощи x заключенных, тогда

    R(x,y)=Sum(C(x-i,x)*R(i,y-1), i, 0, x),

    где Sum(Ai, i, 0, n) - знак суммирования слагаемых Ai, индекс i пробегает значения от 0 до n;
    C(k,n) - Цэ-из-n-по-k - количество вариантов чтобы выбрать k предметов среди n возможных.
    R(1,y)=1+y
    R(x,1)=power(2,x) - два в степени x
    R(0,y)=1
    C(0,x)=1

    В данном конкретном случае
    R(5,2)=
    C(5,5)*R(0,1)+C(4,5)*R(1,1)+C(3,5)*R(2,1)+C(2,5)*R(3,1)+C(1,5)*R(4,1)+C(0,5)*R(5,1)=
    1*1+5*2+10*4+10*8+5*16+1*32=243
    При степенях двоек коэффициенты Паскаля.

    Если было бы 3 дня на тестирование, то
    R(5,3)=
    C(5,5)*R(0,2)+C(4,5)*R(1,2)+C(3,5)*R(2,2)+C(2,5)*R(3,2)+C(1,5)*R(4,2)+C(0,5)*R(5,2)
    =
    1*1
    +5*[C(1,1)*R(0,1)+C(0,1)*R(1,1)]
    +10*[C(2,2)*R(0,1)+C(1,2)*R(1,1)+C(0,2)*R(2,1)]
    +10*[C(3,3)*R(0,1)+C(2,3)*R(1,1)+C(1,3)*R(2,1)+C(0,3)*R(3,1)]
    +5*[C(4,4)*R(0,1)+C(3,4)*R(1,1)+C(2,4)*R(2,1)+C(1,4)*R(3,1)+C(0,4)*R(4,1)]
    +1*[C(5,5)*R(0,1)+C(4,5)*R(1,1)+C(3,5)*R(2,1)+C(2,5)*R(3,1)+C(1,5)*R(4,1)+C(0,5)*R(5,1)]
    =
    1
    +5*[1+1*2]
    +10*[1+2*2+1*4]
    +10*[1+3*2+3*4+1*8]
    +5*[1+4*2+6*4+4*8+16]
    +1*[1+5*2+10*4+10*8+5*16+32]
    =
    1024
    Красивое число, не правда ли?

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

    Пишите мне i.dubov@rambler.ru

    ОтветитьУдалить
  57. Уважаемый аноним, спасибо за интересное обобщение!

    ОтветитьУдалить
  58. Нет надобности усложнять решение обобщенной задачи с произвольным количеством арестантов, m, и произвольным количеством дней для тестирования, n, до такой степени: оно ничуть не сложнее, чем решение конкретного варианта задачи где m=5, n=2. Нужно всего лишь воспользоваться (n+1)-чной системой счисления вместо троичной. Максимальное количество бочек, из которых однозначно можно определить единственную бочку с ядом, очевидно, равно Max=(n+1)^m. Например, если у нас всего m=4 арестанта, но n=9 дней для тестирования, тогда нужно воспользоваться обычной десятичной системой и 10000 бочек получат номера от 0000 до 9999.

    ОтветитьУдалить
  59. Анонимный04.03.2011, 8:55

    Уважаемый Arthur Baraov!
    Я согласен с Вами что ответ совпадает, но я не согласен с тем, что стратегия на основе (n+1) - ричной системы исчисления является оптимальной (по постороению, не по результату). Могли бы Вы любезно предоставить рассуждения в доказательство этого либо вывести ответ из стратегии на основе коэффициентов паскаля?

    ОтветитьУдалить
  60. Уважаемый аноним, я не понимаю Ваш вопрос.
    Вы согласны, что ответы совпадают но считаете, что стратегии отличаются. Но ведь ответ в данном случае - это стратегия (или алгоритм действий, чтобы выявить отравленную бочку).

    Т.е. выглядит так, как будто и Ваш ответ, и ответ Артура совпадают (предложены одинаковые способы искать отраву), но отличаются подходы, позволившие найти эти решения.

    А раз так, то в чём состоит вопрос? И если не так, то уточните, пожалуйста, что я неправильно понял.

    ОтветитьУдалить
  61. Анонимный09.03.2011, 9:42

    Как раз таки стратегии у нас отличаются.

    Стратегия на основе (n+1)-ричной системы исчисления. Один раз вначале пронумеровать все бочки и каждый день давать бочки на пробу в соответствии с номером.

    Стратегия на основе чисел Паскаля. Ежедневно разбивать все оставшиеся бочки на (m+1) групп и давать (или не давать) бочки на пробу в соответствии с нахождением бочки в группе (номером группы).
    Для меня стратегия на основе групп Паскаля очевидно оптимальная по построению, её невозможно улучшить.
    Доказательство оптимальности стратегии на основе групп паскаля.

    Мы находимся в k-ом дне тестирования. Нумерация дней в обратном порядке от y до 1
    Если мы отправляем на смерть сразу m заключенных, то мы им можем дать на пробу не более 1 бочки. Если мы им дадим 2 бочки, то при помощи оставшихся 0 заключенных, мы не сможем распознать, какая из этих двух бочек была отравлена.

    Если мы отправляем на смерть заключенных с номерами 1, 2, 3 ... m-1, то мы им можем дать на пробу не более того количества бочек, чем то которое можно будет протестировать одним оставшимся заключенным за номером m в течении оставшихся k-1 дней.

    Для примера если мы отправляем на смерть первые четыре заключенных (номера 1, 2, 3, 4), то оставшимся пятым заключенным мы в следующиее k-1 дней сможем протестировать не более чем R(1, k-1) бочек.
    Другой квартет - посылаем на смерть номера 1, 2, 3, 5, а оставшийся в живых четвертый заключенный сможет протестировать не более чем R(1, k-1) бочек.
    И т.д.
    Всего у нас разных 4 квартета. Всего при помощи квартетов мы в день k сможем протестировать не более R(1, k-1) + R(1, k-1) + R(1, k-1) + R(1, k-1) = 4* R(1, k-1) бочек.

    В общем случае,
    если посылаем на смерть m заключенных, то с их помощью на шаге k можно протестировать не более 1 бочки, т.к. оставшийся в живых 0 заключенный сможет протестировать за k-1 дней не более 1 бочки, по определению. А таких "квинтетов" у нас C(m,m)=1
    если посылаем на смерть (m-1) заключенных, то с их помощью на шаге k можно протестировать не более C(m-1,m)*R(1,k-1), т.к. оставшийся в живых 1 заключенный сможет протестировать за k-1 дней не более R(1,k-1) бочек, по определению. А таких "квартетов" у нас C(m-1,m)=m
    если посылаем на смерть (m-2) заключенных, то с их помощью на шаге k можно протестировать не более C(m-2,m)*R(2,k-1), т.к. оставшиеся в живых 2 заключенных смогут протестировать за k-1 дней не более R(2,k-1) бочек, по определению. А таких "триплетов" у нас C(m-2,m)

    и т.д.,
    если посылаем на смерть 1 заключенных, то с их помощью на шаге k можно протестировать не более C(1,m)*R(m-1,k-1), т.к. оставшиеся в живых (m-1) заключенных смогут протестировать за k-1 дней не более R(m-1,k-1) бочек, по определению. А таких "единичек" у нас C(1,m)=m
    если посылаем на смерть 0 заключенных, то с их помощью на шаге k можно протестировать не более C(0,m)*R(m,k-1), т.к. оставшиеся в живых m заключенных смогут протестировать за k-1 дней не более R(m,k-1) бочек, по определению. А таких "пустышек" у нас C(0,m)=1

    получаем R(m,k)=Sum(C(m-i,m)*R(i,k-1), i, 0, m),


    Вопрос в том, где рассуждения в пользу оптимальности стратегии на основе (n+1)-ричной системы исчисления? Почему её невозможно улучшить? До тех пор, пока они не приведены, считаю решение не удовлетворительным.

    ОтветитьУдалить
  62. Уважаемый аноним, я опять не понимаю вопрос. Можно разными способами объяснить одно и то же построение. Вам Ваше построение удобнее и понятнее, а мне понятны оба.

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

    Если бы Вы спрашивали, почему решение с n-ричной системой счисления является правильным, то я бы с радостью объяснил. Но объяснять, почему оно является оптимальным, если оно совпадает с тем, в оптимальности которого Вы уже и так уверены?.. Я не понимаю. Поясните, пожалуйста, что именно Вам не ясно.

    ОтветитьУдалить
  63. Анонимный16.03.2011, 11:38

    Ну мне то какбы и так всё ясно.

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

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

    У меня нет вопроса. У меня есть претензия, что уважаемый Arthur Baraov дает ответ, но без доказательства что это ответ. Причем комментирует это пафосно "нет надобности усложнять ..."

    ОтветитьУдалить
  64. Анонимный16.03.2011, 11:40

    ЗЫ повторяю:
    "Уважаемый Arthur Baraov!
    ... Могли бы Вы любезно предоставить рассуждения в доказательство этого либо вывести ответ из стратегии на основе коэффициентов паскаля?
    "

    ОтветитьУдалить
  65. Анонимный16.03.2011, 11:47

    PSPS
    Быть может доказательство было ранее и я его пропустил?

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

    ОтветитьУдалить
  66. Уважаемый аноним, Вы поражаете своим настойчивым нежеланием ответить на простой вопрос: зачем доказывать, почему одно решение является оптимальным, если оно совпадает с тем, в оптимальности которого Вы уже и так уверены (потому что сами её доказали)?

    Впрочем, я не ленивый, могу повторить доказательство для решения с n-ричной системой счисления:

    1. За D дней K добровольцев могут сообщить не более (D+1)^K информации, так как каждый доброволец умрёт в один из D дней или останется живым (это D+1 состояние), а всего независимых добровольцев K. Для условия задачи получаем, что пятью тестерами за два дня можно закодировать одно из 3^5=243 состояний (и большее количество информации передать невозможно).

    2. Предложенный способ кодирования как раз позволяет закодировать число от 1 до 243 (т.е. можно указать номер ёмкости от 1 до 240, например).

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


    Теперь о моей фразе «Но есть задачки, в которых мало найти хоть какое-то решение, а надо доказать его оптимальность (показать, что лучшего решения не существует).». Цитируя её, Вы, видимо, забыли, что она относилась к ответам менее предельного. То есть, если кто-то предлагает способ, позволяющий доказать неотравленность 236-тии ёмкостей с квасом, то мне мало узнать, как он это делает, но хочется ещё услышать, почему нельзя лучше.

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

    Надеюсь, что ответил на Ваш вопрос. Поясните, если что-то не будет ясно - постараюсь дополнить.

    ОтветитьУдалить
  67. Анонимный02.05.2011, 5:06

    Уважаемый Илья!
    Уже не один месяц с большим интересом читаю ваш блог.
    Масса впечатлений, масса мыслей по ходу.
    Увы, написать вам сподвигло не самое приятное обстоятельство.
    Удручает ваша манера сокращённо склонять числительные.
    Для справки: http://gramota.ru/spravka/letters/?rub=rubric_99
    Простите за прямоту.

    ОтветитьУдалить
  68. Уважаемый аноним, спасибо за прямоту.
    Буду работать и над этим.

    ОтветитьУдалить
  69. Спасибо за интересную задачку. Очень понравилась решение с кодированием жаль, что сам не додумался.

    ОтветитьУдалить
  70. Maxim, да у нас ещё будут задачки, заходите :)
    Кстати, о кодировании мы совсем недавно разбирали карточный фокус.

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

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний