Логика №2

[LazarusLong]

Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Недоброжелателя тут же поймали, дальнейшая его судьба неизвестна.
Про яд известно, что человек, его выпивший, умирает в течение 24 часов. До праздника осталось два дня, то есть 48 часов. У патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд. Расскажите каким образом можно это узнать.

Большая просьба не гуглить. Ответ найти можно за пару минут, но ведь может быть интересно людям порешать)))).

[FazU]

1шаг: разделить бочки на 5 рабов поровну. рабы выпивают каждый из своих бочек по глотку. Через 24 часа один клеит ласты.
2 шаг: Те бочки из которых пил умерший раб делят поровну наоставшихся и повторяют процедуру. Через 24 часа умирает еще один раб. А у Патриция будет уверенность в том, что 240*4/5+48*3/4=192+36=228 бочек не отравлены.
***

шаг 3 (злобно уничтожительный):
Оставшиеся 12 бочек патриций тоже использует. Вино из них он подаст своим недоброжелателям. И случай выберет из них кто будет жив, а кто мертв.

***
Не гуглил.



(Отправлено в: 25 Апреля 2008, 08:41:29)

Тут эта если б не было написано, что судьба диверсанта не известна можно было бы предположить, что он тоже может участвовать в "дегустации". И тогда можно было бы уверенно говорить об отсутствии яда в большем количестве бочек.
Повторив описаный алгоритм, но исходя уже из 6 "дегустаторов", получим, что об отсутствии яда известно в 232 бочках, а 8 достанется недоброжелателям.

[broken-wings]

FazU не люблюподобные выводы

Вино из них он подаст своим недоброжелателям

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

[LazarusLong]

FazU, нет нужно точно идентифицировать бочку с ядом за 48 часов.

Дегустаторов всего 5.

[broken-wings]

LazarusLong и бочка должна быть точно определена. искал решение - но нашел лишь наподобии удачно определить 8 бочек...
Лишь одна?

[FazU]

Ну одна определится тогда когда кто-то из недоброжелателей копытнется))

А моя импровизация и мои выводы помоему восприняты слишком сухо и серьёзно. Че вы такие не веселые с утра?

[LazarusLong]

Нужно ОДНОЗНАЧНО определить бочку с ядом ДО НАЧАЛА праздника.

FazU, твой ход мыслей понятен, но это не решение задачи:) Я тоже сперва так думал.

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

[FazU]

Прикольно )))
Саша, респект за ход мысли!!

[grimgav]

Разделить бочки по ровну на 5 рабов. Т.е. по 48 на рыло. Каждые 10 минут (например, лень считать интервалы чтоб уложиться в 48 часов). И засечь через сколько часов после начала распития скопытиться один дегустатор. Соответственно отнять 24 часа и вычислить какая бочка отравлена =)

[LazarusLong]

grimgav, да это был один из моих первых вариантов решения. Но фишка в том, что выпивший вино умрет не ровно через 24 часа, а В ТЕЧЕНИИ 24 часов. То есть может быть и через 10 минут.

(Отправлено в: 25 Апреля 2008, 09:38:12)

шаг: разделить бочки на 5 рабов поровну. рабы выпивают каждый из своих бочек по глотку. Через 24 часа один клеит ласты.

Кстати не приходило в голову, что можно разделить и на 6 частей - каждый раб пьёт из 40 бочек. А из 40 последних бочек - ни пьёт никто. Соответственно если кто-то умер - мы знаем в каких из 40 бочек отрава. А если никто не умер - то яд в одной из бочек из которых никто не пил (это не намек на решение), просто усовершенствование метода предложенного FazU. Таким образом можно локализовать интервал до 8 бочек. Но это тоже не решение.

[NunTerix]

Знаю решениЯ, если бы в задаче было указано не 48, а 72 часа ...

[LazarusLong]

Знаю решениЯ, если бы в задаче было указано не 48, а 72 часа ...

Увы, нужно решить именно за 48. За 72 задача решается вообще элементарно )))

[Fr0sT]

Разделим общее кол-во бочек на 16 частей (по 15шт). Первые 5 частей пьют соответственно 1,2,...,5 рабы. Одну часть не пьет никто. Оставшиеся 10 частей пьют сразу 2 раба. (т.е. 1 и 2, 1 и 3 и т.д. Таких сочетаний: С_5²=120/12=10). Через 24 умирают либо 2 раба, либо 1, либо 0. Если 0 или 1 - составляем 15 разных групп из 4-5 рабов и через 24 часа узнаем нужную бочку. Если же умерло 2 раба, то аналогично они пробуют по 2 бочки (1 не пробует никто). Дальше  - не хватило рабов(или времени).
з.ы. или мозга у меня

[LazarusLong]

Fr0sT, ты на верном пути

[Fr0sT]

Итоговый вариант
Чтобы определить бочку, необходимо, чтобы на 2ом шаге каждый раб(или их группа) пили только из одной бочки каждый.
Для этого разбиваем кол-во бочек так: 1,2,...,5 пьют из 18 бочек каждый(т.к. 4 оставшихся раба смогут проверить C₄¹+C₄²+C₄³+2(1 не пробует никто) бочек), группы по 2 раба пьют из 8 бочек каждая(3 оставшихся могут проверить 8 бочек), группы по 3 раба пьют из 4 бочек.
Тогда 5*18+10*8+10*4+(кол-во пустых бочек)=240
Следовательно, на 1ом шаге необходимо оставить 240-90-80-40=30 бочек.
Если отравленная - среди этих 30, то 5 рабов (никто не умрет) смогут определить нужную.

[LazarusLong]

Fr0sT, что-то не совсем внятно ты описал кто откуда пьёт.
1,2,3,4,5-й пьют из 18-ти бочек каждый? То есть охватили 72 бочки.
Кстати 4 раба не проверят 18 бочек. Они проверят максимум 16 (16 - 2⁴).

[Fr0sT]

Кстати 4 раба не проверят 18 бочек.

Ошибочка вышла)

То есть охватили 72 бочки.

А вот этого не понял. Почему не 16*5=80?
Получается 16*5+8*10+4*10+2*5=210. Из 30 бочек на 1ом шаге никто не пьет. 5 рабов достаточно

[LazarusLong]

Почему не 16*5=80?

Ошибся, с кем не бывает.

В общем правильно. +1.

Приведу моё решение.

Очевидно, что один раб может иметь два состояния - жив и мертв. То есть условно говоря - это один бит информации . Одного раба достаточно для того, что бы проверить две бочки (выпил из одной - если не умер - значит отравлена друга, если умер - значит отравлена та из которой пил). 2 раба могут проверить 4 бочки (1-й выпил из первой бочки, 2-й из второй, из третьей выпили оба из четвертой не пил никто), 3 раба - аналогичным образом проверяют 8 бочек, 4 раба - 16 бочек, 5 рабов - 32 бочки.

Таким образом план первой пьянки строим следующим образом:

Затем из 10 бочек пьют 5 рабов, причем пьют так, чтобы из каждой бочки выпили только 4 раба. Если отравлена одна из этих 10 - то 4 раба умрут и выживет 1. Он и определит, в какой из двух бочек, из которых не пил, находиться яд.

Затем берётся 40 бочек. 5 рабов можно организовать по 3 раба десятью
комбинациями. Каждая тройка рабов пьёт из определённых 4 бочек. Если яд
будет в одной из этих 40 бочек, тройка умрёт, а оставшиеся 2 раба
проверёт доставшиеся им 4 бочки.

Затем берётся 80 бочек. 5 рабов можно разбить на пары опять же десятью
способами. Если какая-то пара померла, то попробованные ей 8 бочек
проверит выжившая тройка.

Затем берётся 80 бочек. Каждый раб пьёт из 16ти. Если один умирает,
оставшиеся 4 определяют яд в 16ти бочках, опробованных ими.

Конец первой пьянки

И наконец на вторую попойку можно зарезервировать 32 бочки. Если рабы не
умрут, значит яд в этих 32х бочках. За один присест они их проверят.

Итак, общее число бочек - 1+10+40+80+80+32 = 243 бочки. Т.е. 5ю рабами
можно проверить 243 бочки за два захода

[grimgav]

LazarusLong, а как же 48 часов и смерть в течении 24-х?

[LazarusLong]

grimgav все там соблюдается.
Все действия первой пьянки проводятся сразу.
То есть
1. Все рабы выпили из 1-й бочки.
2. Из 10 бочек пьют 5 рабов, причем пьют так, чтобы из каждой бочки выпили только 4 раба.
3. 40 бочек. Каждая тройка рабов пьёт из определённых 4 бочек.
4. 80 бочек. Из каждой бочки пьет пара рабов.
5. 80 бочек. Каждый раб пьет из 16.

Ждем 24 часа.

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