Циничная задача :)

[worm2]

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

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

[Echo-Off]

worm2 писал(а):

Про яд известно, что человек, его выпивший, умирает в течение 24 часов

Известно, что человек умрёт ровно через 24 часа, или может пораньше?

[worm2]

Известно, только, что человек умирает в течение 24 часов.
Проще говоря, у патриция только 2 попытки, всё остальное - это поэзия

[Профессор Снэйп]

Если бы было ровно 24 часа, а не в течении двадцати четырёх часов, то задача бы решалась просто. А так...

Делим 240 бочек на 6 частей по 40 бочек. Для каждой части собираем бокал (по несколько капель из каждой бочки, находящейся в данной части) и даём попробовать одному из рабов. Ждём 24 часа.

После этого остаётся 4 раба (возможно, конечно, что и 5, но в худшем случае 4) и 40 бочек, про которые известно, что в одной из них яд. Делим на 5 частей по 8 бочек, повторяем процедуру.

Проходят ещё сутки. Становятся известны 8 бочек, в одной из которых яд. А время вышло. Конечно, с 232 бочками вина уже можно устроить нормальный праздник, но это всё же не решение задачи. А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Вот такой вопрос по ходу. Время, за которое раб умирает, попробовав отраву: оно фиксировано или может варьироваться? Другими словами, если два раба пробуют отраву одновременно, то они и умирают потом одновременно или могут умереть в разное время?

[Коровьев]

На самом деле бочек оказалось 243. Три бочки виногрузчики решили заныкать и стырить - мол всё равно никто считать не будет...
"Ну, в общм, они не сносили голов".

[Kid Kool]

Пусть k-ый раб отопьет из каждой бочки, у которой в k-ом разряде номера в троичной системе счисления стоит 0. Рассмотрим выживших в первые сутки рабов. Тогда в номере ядовитой бочки в соответствующих разрядах могут стоять только 1 и 2, а в разрядах умерших рабов стоят нули. Зафиксируем нулевые разряды, и во второй день выжившие рабы отопьют из бочек, где на соответствующих разрядах стоят 1. Если раб умер, то в номере ядовитой бочки соответствующий разряд равен 1, иначе 2.

[worm2]

Профессор Снэйп писал(а):

Время, за которое раб умирает, попробовав отраву: оно фиксировано или может варьироваться? Другими словами, если два раба пробуют отраву одновременно, то они и умирают потом одновременно или могут умереть в разное время?

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

Профессор Снэйп писал(а):

А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Я счастлив, что задача показалась Вам такой нерешаемой
А то боялся, что придёт сейчас кто-нибудь и напишет "всё тривиально"...

[Kid Kool]

Коровьев писал(а):

На самом деле бочек оказалось 243.

Просек фишку : ))

[Коровьев]

Kid Kool писал(а):

Коровьев писал(а):

На самом деле бочек оказалось 243.

Просек фишку : ))

Верно.
$243=3^5$

[Профессор Снэйп]

Да, я тоже просёк. Правда, только после того, как увидел подсказку насчёт числа $243$.

[worm2]

А я, если честно, когда решал, фишку так и не просёк, и 243 получил честно как сумму

$$\sum\limits_{i=0}^{5}C_5^i 2^i$$

Добавлено спустя 2 минуты 18 секунд:

Т.е. у меня было более сложное решение с разбором шести различных вариантов.

[Sanya]

есть единственно правильное решение
друг мой один решил вот так.
_______________________________________
Выкидываем в первый день обследования сразу 30 бочек. Их мы оставим на завтра, если никто не умрёт через 24 часа.

остаётся 240-30 = 210 бочек. Занумеруем рабов по порядку от 1 до 5 (на то они и рабы. Составим график пития для бочек:
1 - 16
2 - 16
3 - 16
4 - 16
5 - 16
1-2 - 8
1-3 - 8
1-4 - 8
1-5 - 8
2-3 - 8
2-4 - 8
2-5 - 8
3-4 - 8
3-5 - 8
4-5 - 8
1-2-3 - 4
1-2-4 - 4
1-2-5 - 4
1-3-4 - 4
1-3-5 - 4
1-4-5 - 4
2-3-4 - 4
2-3-5 - 4
2-4-5 - 4
3-4-5 - 4
1-2-3-4 - 2
1-2-3-5 - 2
1-2-4-5 - 2
1-3-4-5 - 2
2-3-4-5 - 2
----------------
итого: 16*5 + 8*10 + 4*10 + 2*5 = 210 бочек

Поим засранцев и смотрим на результат:
Никто не умер: 30 бочек и 5 живчиков
Умер один раб:отравленная бочка в одной из 16, которую он пил один. Осталось 4 раба, ищется элементарно
умерло двое: отравленная бочка в одной из 8-ми, которые они распивали вместе. На троих найдут в следующие сутки.
умерло трое: осталось два раба и 4 бочки. Ерунда
умерло четверо: остался один раб - и две бочки.

That's all!
ЗЫ. В задачу можно смело ещё три бочки запихать. Алгоритм тот же

[TOTAL]

worm2 писал(а):

Профессор Снэйп писал(а):

А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Я счастлив, что задача показалась Вам такой нерешаемой
А то боялся, что придёт сейчас кто-нибудь и напишет "всё тривиально"...

Задача и есть нерешаемая. Из того что раб остался жив, конечно, следует, что он не пил яда. Но из того что раб сдох, не следует, что он яд пил. Рабы дохнут и от других причин. Все ваши рассуждения рушатся, приглашенные на праздник гости в опастности.

[Sanya]

TOTAL писал(а):

worm2 писал(а):

Профессор Снэйп писал(а):

А как идентифицировать ту единственную бочку и уложиться в срок? Даже не верится, что это возможно...

Я счастлив, что задача показалась Вам такой нерешаемой
А то боялся, что придёт сейчас кто-нибудь и напишет "всё тривиально"...

Задача и есть нерешаемая. Из того что раб остался жив, конечно, следует, что он не пил яда. Но из того что раб сдох, не следует, что он яд пил. Рабы дохнут и от других причин. Все ваши рассуждения рушатся, приглашенные на праздник гости в опастности.

нет на этом свете не решаемых задач

[Архипов]

TOTAL в сообщении #152709 писал(а):

Задача и есть нерешаемая. Из того что раб остался жив, конечно, следует, что он не пил яда. Но из того что раб сдох, не следует, что он яд пил. Рабы дохнут и от других причин. Все ваши рассуждения рушатся, приглашенные на праздник гости в опастности.

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

Sanya в сообщении #152715 писал(а):

нет на этом свете не решаемых задач

Согласен. Решить можно любую задачу. Тока кто будет за это отвечать? Рабы, как всегда?