Saturday, February 05, 2011

Джек Лондон. Строптивый Ян.


Ибо нет закона, ни божьего, ни людского,
К северу от пятьдесят третьей.


Ян царапался и лягался, катаясь по земле. Он молча, сосредоточенно отбивался от своих противников руками и ногами. Двое из них наседали на него, покрикивая друг на друга. Но коренастый волосатый детина не хотел сдаваться. Третий человек вдруг взвыл от боли. Ян укусил его за палец.

— Да угомонись ты, Ян, пусти его! — проговорил, тяжело дыша, Рыжий Билл и сдавил Яна за шею. — Дай нам повесить тебя тихо и мирно.

Продолжение тут http://www.jacklondon.su/stroptiviy-yan/page/1/
http://www.jacklondon.su/stroptiviy-yan/page/2/
http://www.jacklondon.su/stroptiviy-yan/page/3/

UPDATE: А теперь перечитайте ещё раз этот рассказ имея в виду, что Ян=Израиль. ;-) END OF UPDATE

Задача о квасе



http://my-tribune.blogspot.com/2011/01/blog-post_23.html

По наводке блога "Привычка не думать" предлагаю по думать о решении следующей задачки. Её условия взято с этой заметки http://my-tribune.blogspot.com/2011/01/blog-post_23.html, хотя я её цитирую не дословно.

Предупреждаю, задачка вовсе не является "элементарной". Итак, условие.

Ниже есть продолжение.

У вас есть 240 бочек с квасом. Ровно одна из них была отравлена пятью вашими врагами, которых вы поймали. Враги были приговорены к смертной казни, поэтому вам разрешается поить их квасом из этих бочек. Яд очень сильно действующий, отравляет человека в любой концентрации (одной капли яда достаточно чтобы умереть). Т.к. бочки одинаковые, ваши враги не знают какую бочку они отравили. Яд убивается в течении суток (может через 10 минут, а может и через 24 часа). Вы должны за двое суток определить максимальное количество бочек в которых заведомо нет яда.

По ссылке выше в комментариях есть решение. Здесь я постараюсь представить "элементарное" решение.

Итак, давайте для начала поймём условие задачи. Что значит "яд убивается в течении суток (может через 10 минут, а может и через 24 часа)" и то, что у нас есть двое суток? Допустим мы дали арестанту попробовать квас. Далее мы смотрим умер он или нет. Если он умер - значит в квасе был яд (в задачи неявно предполагается, что за двое суток, по естественным причинам, там сердечный приступ, никто не умрёт, иначе она теряет смысл). Если он не умер, то что это значит? Если прошло более суток, значит яда нет ("яд убивается в течении суток"). Если прошло 10 минут - то это ничего не значит, т.к. может быть просто ещё не подействовал. Таким образом, если прошло менее 24 часов и "пациент" жив - нельзя сделать никакого вывода, если прошло более 24 часов (или ровно), значит он не отравился. Таким образом, необходимо и достаточно 24 часов. У нас есть двое суток, таким образом, у нас есть две итерации, мы можем дважды напоить арестантов.

Что значит "Яд очень сильно действующий, отравляет человека в любой концентрации (одной капли яда достаточно чтобы умереть)"? Это значит, что если мы возьмём квас из двух бочек, в одной из них есть яд, в другой нет и нальём его в один стакан и дадим арестанту выпить, то он умрёт. Более того, если мы возьмём вместо двух, скажем, 48 бочек, он также умрёт (в обычных условиях яда будет настолько мало, что он может и не подействовать, что усложняет задачу). Итак, задача может быть переформулирована следующим образом:

У вас есть 240 бочек с квасом. Ровно одна из них была отравлена 5 врагами. Достаточно любой концентрации яда, чтобы умереть. Вы должны за две итерации определить максимальное количество бочек в которых заведомо нет яда.

Теперь, применим стандартный приём, а именно решим задачу на меньшем масштабе.

Задача 1.2 Допустим, у нас есть только 1 арестант и 2 итерации. Какое максимальное количество бочек можно распознать?

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

Задача 1.1 Допустим, у нас есть только 1 арестант и 1 итерация. Какое максимальное количество бочек можно распознать?

Очевидно, если у нас есть 1 бочка, арестант из неё пьёт и если умирает, значит она была отравлена, если не умирает, значит не было отравлена, т.е. 1 бочку можно распознать таким образом. Однако, на самом деле 1 бочку можно распознать за 0 (ноль) итерации. По условию задачи известно, что 1 бочка отравлена, поэтому ответ - она отравлена.

Хорошо, увеличим количество бочек до 2. Если мы смешаем квас из этих бочек и дадим его выпить арестанту, мы ничего не добьёмся. Так как из условия задачи (1 бочка заведомо отравлена) следует, что он умрёт. Т.к. наши попытки на этом закончатся мы не узнаем, где был яд. Значит, смешивать квас не надо. Арестант должен выпить с 1 бочки, а 1 бочку нужно отложить в сторону. Далее, если арестант жив, значит в этой бочке яда нет, и отравлена другая, отложенная бочка (1 бочка заведомо отравлена). Если арестант умер, значит бочка с которой он пил была отравлена, а та вторая без яда. Итак 1 арестант может за 1 итерацию различить 2 бочки.

Можно ли различить 3 бочки? Если смешать квас из этих бочек и дадим его выпить арестанту, мы ничего не добьёмся. Так как из условия задачи (1 бочка заведомо отравлена) следует, что он умрёт. Т.к. наши попытки на этом закончатся мы не узнаем, где был яд. Значит как минимум одну бочку нужно отложить в сторону. Для 3 бочек есть следующие ситуации - 2-1, 1-2, т.е. смешиваем 2 бочки, одну откладываем в сторону, пьём из 1 бочки, две откладываем в сторону (3-0, как было показано выше не приводит к решению, также как и 0-3, арестант ничего не пьют вообще).

а) Мы смешали две бочки, одну отложили в сторону. Допустим, арестант умер, значит яд в одной из этих двух бочек. Но в какой? Попытки вышли...

б) Арестант пил из какой-то бочки и 2 отложили в сторону. Допустим, арестант выжил. Значит яд в одной из двух отложенных бочек. Но в какой? Попытки вышли...

Значит максимум за 1 итерацию 1 арестант может различит 2 бочки. Теперь вернёмся к задаче 1.2


Задача 1.2 Допустим, у нас есть только 1 арестант и 2 итерации. Какое максимальное количество бочек можно распознать?

Если после первой итерации у нас останется 2 бочки и, естественно, живой арестант, то мы сведём решению задачи 1.2 к решению задачи 1.1 (это называется редукцией). Таким образом, если мы начнём с 2 бочек мы точно сможем решить задачу. Как насчёт 3 бочек? Как мы выше показали, имеет смысл рассмотреть только два варианта 2-1 и 1-2 (убедитесь в этом сами):

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

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

Как мы видим, для 3 бочек, решение выпить из одной бочки и 2 отложить в сторону.

Можно ли решить для 4 бочек? Как мы видели выше, если мы смешаем квас из двух бочек и более и арестант умрёт, мы не сможем определить, где был яд (он был в одной из этих бочек из которых мы взяли квас для арестанта, но в какой именно не понятно), значит арестант при первой итерации должен пить из ровно 1 бочки. Если он умрёт, то сколько бы n бочек мы не отложили, задача решена, в той бочке, из которой он пил был яд, в остальных n - яда не было. Если же он выживет, то значит та бочка, из которой он пил, без яда, а яд находится в одной из n отложенных бочек. У нас есть живой арестант, 1 итерация и n бочек. Согласно, задаче 1.2. n=2, т.е. мы можем максимум отложить 2 бочки. Всего 2+1=3 бочки. Т.е. это максимум.

Если у нас 1 арестант и 2 итерации, мы можем распознать максимум 3 бочки. Делаем мы это следующим образом:

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

Итерация 2. Она происходит, если арестант выжил после первой итерации. Итак, нам осталось определить в какой из 2-ух бочек есть яд. Согласно задаче 1.2. для этого мы откладываем 1 бочку и даём арестанту выпить с 1 (другой) бочки. Если арестант умер, значит яд был в той бочке из которой он пил. Если арестант выжил, значит яд был в оставшейся бочке.

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

Теперь, увеличим, количество арестантов до 2.


Задача 2.2 Допустим, у нас есть 2 арестанта и 2 итерации. Какое максимальное количество бочек можно распознать?

Давайте, для определённости дадим арестантам имена, скажем A и B (Alice и Bob).

Можно эту задачу разбить на две параллельные задачи, а именно делим бочки на 2 части, даём A половину и B половину. Согласно задаче 1.2 A может "справится" с 3 бочками, а также согласно задаче 1.2 B может "справится" с 3 другими бочками итого вместе таким образом они могут справится с 6 бочками...

В этом месте мы можем захотеть вернутся к задаче с 5 арестантами и 240 бочкам. Поделим бочки на 6 групп по 240/6=40 бочек в каждой группе, для каждого арестанта своя отдельная группа (т.е. мы наливаем в кружку квас из каждой из 40 бочек, смешиваем квас из 40 бочек группы для каждого арестанта) и ещё 1 группа из которой никто не пьёт. Так как яд находится только в одной бочке, а из этой бочки пил максимум 1 арестант, то у нас минимум 4 арестанта останутся в живых и мы будем знать что в этих 4*40=160 бочках яда точно нет. Если у нас 1 арестант-таки умер, значит у нас есть 4 живых арестанта ещё 1 итерация и яд в одной из 40 бочек из которых пил умерший (a). Если у нас никто не умер, значит у нас есть 5 живых арестантов, ещё 1 итерация и яд в одной из 40 бочек из которых никто не пил (b).

Итак, для последней (второй) итерации имеем:

a) 4 арестанта и яд в одной из 40 бочек. Аналогично, делим квас на 5 групп по 40/5=8 бочек в каждой группе, для каждого арестанта своя отдельная группа (т.е. мы смешиваем квас из 8 бочек группы для каждого арестанта) и ещё 1 группа из которой никто не пьёт. Так как яд находится только в одной бочке, а из этой бочки пил максимум 1 арестант, то у нас минимум 4 арестанта останутся в живых и мы будем знать что в этих 4*8=32 бочках яда точно нет. А вот где яд в оставшихся 40-32=8 бочках мы не знаем. Таким образом мы можем различит 240-8=232 бочек.

b) 5 арестантов и яд в одной из 40 бочек. 1 арестанта оставляем в покое и решаем задачу с 4 арестантами, т.е. делаем редукцию на п.а) Получим также 232 бочки.

Очевидно, что в пункте б) можно улучшить оценку разделив 40 бочек на 6 групп, но это не улучшить итоговую оценку в 232 бочки.

Очевидно, 232 бочки является одним из решением задачи. Является ли оно максимально возможным? В пункте b) чувствуется отсутствие симметрии, есть ощущение, что можно как-то улучшить. Однако, это ощущение нам подсказывает, что так как 40/6=6+2/3 вместо 8 (в пункте а) это улучшение может быть на 1, максимум 2 бочки.

Здесь я хочу заметить, что для практических целей, это достаточное решение. Т.е. любой инженер на этом остановился бы. 232 из 240 бочек, это более 95% решения...

С чисто теоретической (математической) точки зрения, 232 - ответ не верный, можно больше. При этом можно больше даже, чем 233 и даже больше, чем 234. За счёт чего? За счёт того, что мы не будем делить на 5 параллельных задач, а допустим между ними взаимодействие. Запутались?

Самое время вернутся упростить задачу и вернутся к 2 арестантам.


Задача 2.2 Допустим, у нас есть 2 арестанта и 2 итерации. Какое максимальное количество бочек можно распознать?

Напомню, что мы дали арестантам имена A и B (Alice и Bob). Также, мы пробовали разбить задачу на параллельные задачи, а сейчас пытаемся сделать между ними взаимосвязи. Непонятно, с какого бока приступить к задаче? Значит, нужно её ещё упростить, уменьшив, для начала количество итераций до одной.

Задача 2.1 Допустим, у нас есть 2 арестанта и 1 итерация. Какое максимальное количество бочек можно распознать?

При "параллельном" решении задач, мы получаем 3 бочки, как было показано выше, а именно. Каждому даётся 1 бочка и ещё 1 бочка откладывается в сторону. Напомню, яд есть ровно в одной бочке. Таким образом, если никто не умрёт, значит яд в оставшийся в стороне бочке. Если кто-то умрёт, значит яд в его бочке.

Можно ли решить эту задачу с 4 бочками? Если мы добавим её в одну из групп с одной бочкой выше мы не найдём решение. В самом деле, допустим, мы её добавили арестанту A. Тогда арестант A пьёт из двух бочек из которых больше никто не пьёт. Если он умрет, мы не узнаем в какой из этих двух бочек был яд. Если мы добавим бочку арестанту B, мы аналогично также не решим задачу. Если мы добавим бочку в стоявшие нетронутые бочки, тогда давайте посмотрит, что случится, если никто не умрёт. Тогда мы не сможем решить в какой их этих двух бочках яд. Но мы хотим как-то "распараллелить" задачу...

Давайте ещё раз посмотрим, что происходит с 3 бочками. Мы делим их на 3 группы, скажем группа 0, группа 1, группа 2. Группу 0 с 1 бочкой мы оставляем в стороне, группу 1 даём арестанту A, группу 2 даём арестанту B.



Давайте посмотрим, что происходит с арестантами, в зависимости от того, где был яд.

1) Если яд находится в бочке 0, то после 1 итерации оба арестанта выживут.
2) Если яд находится в бочке 1, то после 1 итерации арестант A умрёт, арестант B выживет.
3) Если яд находится в бочке 2, то после 1 итерации арестант B умрёт, арестант A выживет.

Какие ещё варианты живой\мёртвый арестант A\B могут быть? Очевидно, что есть ещё вариант, когда оба арестанта умрут. Ниже мы ещё вернёмся к этому моменту, а пока давайте подумаем, что должно произойти, чтобы оба арестанта умерли, применяя в качестве "оружия" ими же отравленный квас ? Т.к. яд есть только в одной бочке, очевидно, что для одновременной смерти двух арестантом необходимо и достаточно, чтобы они оба выпили из такой бочки. Таким образом, мы можем добавить 4 бочку, добавим её содержимое каждому арестанту.



Таким образом после 1 итерации, могут быть следующие исходы:
1) Оба арестанта живи, яд находится в отложенной в стороне бочке 0.
2) Умер только арестант A. Яд находился в одной из бочек из которых он пил. Он пил из бочки 1 и бочки X. Т.к. арестант B жив, мы знаем, что яда в бочке X нет (если бы он там был, то они бы оба умерли), значит яд точно был в бочке 1.
3) Умер только арестант B. Яд находился в одной из бочек из которых он пил. Он пил из бочки 2 и бочки X. Т.к. арестант A жив, мы знаем, что яда в бочке X нет (если бы он там был, то они бы оба умерли), значит яд точно был в бочке 2.
4) Умерли оба арестанта. Яд находился в одной из бочек из которых они пили. Он точно не находится в бочках, из которых они не пили, т.е. в бочке 0. Но в какой из бочек 1,2,x он находится? Мы знаем, по условию задачи, что в ровно в одной бочке он должен быть.

а) если он находился в бочке 1, то умер бы только арестант A, т.к. арестант B не пил из бочки 1. Т.к. умерли оба, значит яда не было в бочке 1.
б) если он находился в бочке 2, то умер бы только арестант B, т.к. арестант A не пил из бочки 2. Т.к. умерли оба, значит яда не было в бочке 2.

Значит, яд обязан быть в бочке x. Это единственная бочка из которых пили оба, а т.к. яд есть ровно в одной бочке и оба арестанта умерли, яд обязан быть в бочке x.

Итак, для 2 арестантов 1 итерации мы решили задачу с 3 бочками, решая её параллельно (см. бочку x). Можно ли решить её с 4 бочками? Нет. Если мы добавим четвёртую бочку в сторону, в группу 0, то тогда если яд будет в одной из двух бочек в группе 0, то после 1 итерации оба арестанта выживут и мы не узнаем в какой из этой бочек есть яд. Если мы добавим бочку в группу 1, то если яд будет в одной из бочек в группе 1, мы аналогично не узнаем где именно после смерти арестанта A. Аналогично, если мы добавим бочку в группу 2, то если яд будет в одной из бочек в группе 2, мы аналогично не узнаем где именно после смерти арестанта B. Если мы добавим бочку в группу x, то если яд будет в одной из бочек в группе x, после 1 итерации оба арестанта умрут и мы не узнаем в какой из бочек группы x был яд. Как доказать, что больше "исходов" нет?

Давайте введён следующую систему пометок бочек, которая будет связана с возможными "исходами" или "состояниями". Как было показано выше имея 1 итерацию для каждой бочке верно ровно одно из следующих:

а) ни A ни B ни пил из данной бочки (и соответственно оба живи на конец 1 итерации);
б) только A пил из данной бочки (соответственно на конец 1 итерации он может быть или жив или мёртв);
в) только B пил из данной бочки (соответственно на конец 1 итерации он может быть или жив или мёртв);
г) и A и B пили из данной бочки (соответственно на конец 1 итерации может быть либо оба живи либо оба мертвы);

Мы можем "закодировать" эту информацию следующим образом. Если арестант A не пил из этой бочки, напишем на ней 0, если он должен пить из этой бочке при 1 итерации напишем на ней. Аналогично для арестанта B, но напишем это рядом слева. К примеру, надпись, 10 обозначает, что арестант A не пил из этой бочки (т.к. крайне справа стоит 0), а арестант B пил (т.к. левее стоит 1). Итак, на каждом месте может быть либо 0 либо 1, всего мест 2, значит всего есть 4 комбинации (00, 01, 10, 11). Таким образом больше 4 состояний быть не может.

Перед тем как мы вернёмся к задаче Задача 2.2, я бы хотел быстро пробежаться по задачам 3.1 и 4.1.

Задача 3.1 Допустим, у нас есть 3 арестанта и 1 итерация. Какое максимальное количество бочек можно распознать?
При "параллельном" решении задач, мы получаем 4 бочки. Ещё мы можем добавить 3 бочки "типа x", "запутанные состояния степени 2", т.е. такие состояния в которых два арестанта пьёт из одной бочки (это могут быть арестанты A+B или B+С или A+C). Однако, это ещё не всё. У нас есть также "запутанные состояния степени 3", т.е. такие состояния в которых все 3 арестанта пьёт из одной бочки, таких состояний 1. Итого, получаем 4+3+1=8 бочки.

Задача 4.1 Допустим, у нас есть 4 арестанта и 1 итерация. Какое максимальное количество бочек можно распознать?
При "параллельном" решении задач, мы получаем 5 бочек. Ещё мы можем добавить 6 бочек "типа x", "запутанные состояния степени 2", т.е. такие состояния в которых два арестанта пьёт из одной бочки (это могут быть арестанты A+B или A+C или A+D или B+C или B+D или C+D). У нас есть также "запутанные состояния степени 3", т.е. такие состояния в которых 3 арестанта пьёт из одной бочки, таких состояний 4 (это могут быть арестанты A+B+C или A+B+D или A+C+D или B+C+D). Однако, это ещё не всё. У нас есть также "запутанные состояния степени 4", т.е. такие состояния в которых все 4 арестанта пьёт из одной бочки, таких состояний 1. Итого, получаем 5+6+4+1=16 бочек.

Но вернёмся к
Задача 2.2 Допустим, у нас есть 2 арестанта и 2 итерации. Какое максимальное количество бочек можно распознать?
Можно рассуждать аналогично решению задачи 2.1.


1. Решим задачу в "параллельном" режиме.
2. Посмотрим, что происходить с арестантами, найдём "неиспользованные исходы".
3. Будем добавлять новые бочки, чтобы использовать новые "исходы".


А можно пойти другим путем, сразу посмотрев какие у нас "исходы" могут быть. Для этого можно использовать разработанный выше код, слегка модифицировав его. Напомню, 01, к примеру обозначает, что из этой бочки A выпил при 1 итерации, а B не пил вообще. Т.к. у нас есть 2 итерации, то из бочки каждый арестант может пить и во время второй итерации. Таким образом мы должны расширить значения, которые могут встретятся в каждом разряде до 3. Новое значение 2 обозначает, что из бочки пили при 2 итерации. Место которое занимает эта 2-ка обозначает, кто именно пил. Итак, у нас будут бочки




1) 01, 11, 21 - это бочки из которых A должен выпить при итерации 1 (это все числа у которых есть 1 в младшем разряде);
2) 10, 11, 12 - это бочки из которых B должен выпить при итерации 1 (это все числа у которых есть 1 в старшем разряде);
3) 00, 02, 20 - это бочки которые мы оставляем в стороне.

или тоже самое



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


1) Если оба арестанта умерли, как нетрудно убедится, это значит, что была отравлена бочка 11.
2) Если оба арестанта выжили, значит яд находится в бочках 00, 02, 20. Имеем, 2 арестантов, 1 итерацию и 3 бочки. Согласно задаче 1.2 такая задача решаемая. Более того, текущая кодировка этих бочек показывает, как мы должны их разделить. Бочку 00 мы должны оставить в стороне, арестант A пьёт из бочки 02, арестант B пьёт из бочки 20.
3) Если умер только арестант A, значит яд в одной из бочек, из которых он пил, а именно 01, 11, 21. Однако, так арестант B жив, яд не может быть в бочке 11. Имеем 1 арестанта и 1 итерацию и 2 бочке. Согласно задаче 1.1. такая задача решаема. Более того и тут кодировка показывает как именно. Арестант B отвечает за старший разряд и у нас вторая итерация, значит он должен выпить бочку 21, а бочку 01 оставить в стороне.
4) Если умер только арестант B, значит яд в одной из бочек, из которых он пил, а именно 10, 11, 12. Однако, так арестант A жив, яд не может быть в бочке 11. Имеем 1 арестанта и 1 итерацию и 2 бочке. Согласно задаче 1.1. такая задача решаема. Более того и тут кодировка показывает как именно. Арестант A отвечает за младший разряд и у нас вторая итерация, значит он должен выпить бочку 12, а бочку 10 оставить в стороне.

Давайте убедимся, что кодировка нам говорит правильно. Она, к примеру, не даёт пить из бочку уже мёртвому арестанту. Арестанты пьют только из бочек, на которых на положенном месте находится 2. В частности, если на бочке нет 2 вообще, как например, на бочке 10, из неё арестанты пить во время 2 итерации не будут. Имеем:



Заметьте, что существует бочка 22, на рисунке она показана дважды, эта всё та же бочка x, это бочка из которой пьют оба арестанта, только уже во время 2 итерации, которая кодирует "состояние" оба мертвы, состояние, которого нет при "параллельном" решении.

Давайте ещё раз пройдёмся по всем вариантам:

В конце первой итерации:
1. Оба арестанта живы - яд находится в одной из бочек 00, 20, 22, 02. Заметьте, что 1 не встречается в описании этих бочек. По кодировке, бочку 00 откладываем в сторону, арестант A пьёт из бочек 02 и 22 (бочка x), арестант B пьёт из бочек 20 и 22 (бочка x). См. далее задачу 2.1.

2. Оба арестанта мертвы - яд находится в бочке 11, т.к. это единственная бочка из которых они пили оба. Задача решена.

3. Умер только арестант A. Яд находится в одной из бочек 01, 11 или 21. Заметьте, что в младшем разряде, отвечающим за арестанта A во всех случаях стоит 1, в частности это значит, что во 2 итерации, он не должен ничего не пить. Т.к. арестант B жив, яда нет в бочке 11. Значит яд либо в 01, либо в 21. По кодировке, арестант B не пьёт из бочки 01 (там находится 0 в его, старшем, разряде), а пьёт из бочки 21 (там находится 2 в его разряде). Согласно задаче 1.1 эта задача разрешима.

4. Умер только арестант B. Яд находится в одной из бочек 10, 11 или 12. Заметьте, что в старшем разряде, отвечающим за арестанта B во всех случаях стоит 1, в частности это значит, что во 2 итерации, он не должен ничего не пить. Т.к. арестант A жив, яда нет в бочке 11. Значит яд либо в 10, либо в 12. По кодировке, арестант A не пьёт из бочки 10 (там находится 0 в его, младшем, разряде), а пьёт из бочки 12 (там находится 2 в его разряде). Согласно задаче 1.1 эта задача разрешима.

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

Перед тем, как решить, наконец, поставленную задачу, решим

Задача 5.2 Допустим, у нас есть 5 арестанта и 2 итерации. Какое максимальное количество бочек можно распознать?

Итак, каждую бочку будем кодировать 5-ти разрядный числом, каждый разряд для каждого арестанта. На каждом месте может быть написано либо 0 (этот арестант не пьёт из этой бочки никогда), либо 1 (пьёт во время итерации 1), либо 2 (пьёт во время итерации 2). К примеру, 11021 обозначает, что арестант C не пьёт из этой бочки никогда, во время 1 итерации из нею пьют только арестанты A, D и E, во время 2 итерации из нею пьёт только арестант С. Таким образом, помимо "чистых" состояний, когда из бочки пьют максимум 1 арестант, у нас есть и "запутанные" состояния, если умрут арестанты A, D и E, к примеру. Сколько таких состояний есть? Очевидно, это все числа вида 11??1, где вместо ? может стоят либо 2 либо 1 (если бы стояло 1, то умерло бы больше арестантов). Таких состояний 4...

Можно не считать подробно все такие состояния, а посчитать сразу сколько всего состояний есть. Их ровно столько сколько есть 5-ых чисел на каждом месте которого может быть либо 0, либо 1, либо 2. Всего таких чисел $3*3*3*3*3=3^5=243$.

"Длинный" способ подсчёта состоит в следующем. Он, в частности, иллюстрирует количество "запутанных" вариантов.

Для начала я напомню, что значит биномиальный коэффициент, точнее я ограничусь вполне конкретным {5\choose 2}. Допустим у нас есть 5 пронумерованных шариков. Для того чтобы выбрать 2 из 5, если нам не важен порядок выбора, мы можем сначала выбрать первого, скажем, шар номер 3, это мы можем сделать 5 способа, затем из оставшихся 4 выбираем второго, скажем шар номер 5, это мы можем сделать 4 способами. Итого имеем 5*4 варианта, но тут важен порядок (есть первый и второй). Если нам порядок не важен, то здесь нам поможет следующее наблюдение. Мы выбрали сначала шар номер 3, а потом шар номер 5. С нашей точки зрения такой выбор эквивалентен выбору сначала шара номер 5, а потом шара номер 3 (ведь порядок нам не важен). Формула 5*4 считает такие выборы дважды, поэтому чтобы получить искомое число, нужно разделить её на 2 - $\fract{5*4}{2}=10$.

${5\choose 0}=1$, сколькими способами можно не выбрать никого из 5 разных шаров. Очевидно одним способом.
${5\choose 1}=5$, сколькими способами можно выбрать 1 шар и 5. Можно выбрать любой шар из 5, поэтому 5 способами.
${5\choose 2}=\fract{5*4}{2}=10$, см. выше.
${5\choose 3}={5\choose 2}=\fract{5*4}{2}=10$, выбрать 3 шара это всё равно, что не выбрать 2 шара.
${5\choose 4}={5\choose 1}=5$, выбрать 4 шара это всё равно, что не выбрать 1 шар.
${5\choose 5}=1$, сколькими способами можно выбрать 5 шаров из 5? Очевидно 1, выбрав всех.

Отмечу вкратце, что общая формула для биномиального коэффициента выглядит так ${n\choose k}=\frac{n!}{k!(n-k)!}$, где n - неотрицательное число, а запись $n!$, читается как эн факториа́л есть произведение всех натуральных чисел до n включительно:

$n! = 1\cdot 2\cdot\ldots\cdot n =\prod_{i=1}^n i$

Также, по определению, $0! = 1$.

Например по этому определению, $5! = \prod_{i=1}^5 i=1*2*3*4*5=120$.

Вернёмся к нашему подсчёту. Как я уже говорил выше он, в частности, иллюстрирует количество "запутанных" вариантов.

Пусть в первый день каким-то образом арестантов напоили квасом.

Ко второму дню возможны варианты:

1) Если выжили все 5. Значит яд в тех бочках, откуда никто не пил.
С помощью 5 арестантов за оставшийся день можно различить 2^5=32 бочек (2 = количество "состояний" для каждого арестанта при 1 итерации - он либо будет пить из конкретной бочки либо нет).
2) Если выжило 4. Яд в тех бочках, из которых пил только умерший.
В первый день могли выжить любые 4 из 5, т.е. ${5\choose 4}$. За оставшийся день мы можем различить $2^4$ бочек. Общее количество бочек ${5\choose 4}*2^4$.
3) Если выжило 3, яд в тех бочках, из которых пили 2 умерших ("запутанные состояние степени 2").
В первый день могли выжить любые 3 из 5 или ${5\choose 3}$. За оставшийся день мы можем различить $2^3$ бочек. Общее количество бочек ${5\choose 3}*2^3$.
тона).
4) Если выжило 2, яд в тех бочках, из которых пили 3 умерших ("запутанные состояние степени 3").
В первый день могли выжить любые 2 из 5 или ${5\choose 2}$. За оставшийся день мы можем различить $2^2$ бочек. Общее количество бочек ${5\choose 2}*2^2$.
5) Если выжил 1, яд в тех бочках, из которых пили 4 умерших ("запутанные состояние степени 4").
В первый день могли выжить любые 1 из 5 или ${5\choose 1}$. За оставшийся день мы можем различить 2^1 бочек. Общее количество бочек ${5\choose 1}*2^1$.
6) Если выжило 0, т.е. все умерли ("запутанные состояние степени 5").
В первый день могли выжить любые 0 из 5 или ${5\choose 0}$. За оставшийся день мы можем различить 1=2^0 бочку. Общее количество бочек ${5\choose 0}*2^0$=1.

Как нетрудно заметить эти рассуждения все ложатся под следующий трафарет: Для k=0,1,2,3,4,5:
* Если выжило k из 5, яд в тех бочках, из которых пили 5-k умерших ("запутанные состояние степени 5-k").
В первый день могли умереть любые 5-k из 5 или ${5\choose 5-k}$. За оставшийся день мы можем различить 2^k бочек. Общее количество бочек ${5\choose 5-k}*2^k$.

Общее количество состояний будет:
$\sum_{k=0}^5 {5 \choose 5-k } 2 ^ k= 2^5+{5\choose 1}*2^4+{5\choose 2}*2^3+{5\choose 3}*2^2+{5\choose 4}*2^3+1= 2^5+5*2^4+10*2^3+10*2^2+5*2^3+1=32+80+80+80+40+10+1=243$.

Всего 243 бочек.

UPDATE-2: Замечание: можно было заметить, что $\sum_{k=0}^5 {5 \choose 5-k }*2^k=(1+2)^5=3^5=243$ первое равенство следует, из бинома НьютонаEND OF UPDATE

Эта задача отличается от поставленной задачи (точнее от эквивалентной ей задачи) только количеством бочек. Нас спрашивают какое максимальное количество бочек мы можем различить из 240 бочек, имея 5 арестантов и 2 итерации. Мы можем различить 243 бочки. Поэтому ответ, на поставленную задачу будет "мы можем различить 240 бочек".


UPDATE: В комментариях к оригинальной заметки было предложенное довольно оригинальное решение к вариации предложенной задачи. А именно, предположим, что яд действует на всех, не зависимо от веса или других данных, в течение одинакового строго-определённого с точностью, скажем, до секунды, времени. Тогда для решения задачи достаточно 2 арестантов при не ограниченном, в принципе, количестве бочек.

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

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

END OF UPDATE

Поставка газа из Египта временно приостановлена, но перебоев не будет


...Вполне возможно, что за терактом в районе Эль-Ариша на газопроводе, подающем газ в Иорданию и Израиль, стоят боевики ХАМАСа или другой исламистской террористической группировки. Это вытекает из распространенного государственными СМИ Египта официального заявления, в котором подчеркнуто: взрывчатку подложили "неизвестные, прибывшие на Синай извне".

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

В заявлении, распространенном канцелярией премьер-министра, подчеркнуто: Израиль всесторонне подготовлен к ситуации, при которой поставка природного газа из Египта может быть прекращена. Имеется возможность немедленно перейти на альтернативные источники энергии и газа.

Пока еще не ясно, причинен ли ущерб инфраструктуре по поставке газа из Египта, но Израиль по собственной инициативе, руководствуясь соображениями безопасности, временно приостановил подачу в страну египетского газа.

Канцелярия премьер-министра особо подчеркнула: при любом сценарии перебои в снабжении населения газом и электроэнергией не предвидятся.

http://www.zman.com/news/2011/02/05/94416.html
http://www.zman.com/news/2011/02/05/94419.html