Задачка про рабов и бочки

Mausoleum

Жил-был хан, и был у него помощник. Как-то раз при дележе добычи после очередного успешного похода они поссорились. А нравы, надо сказать, были суровые - помощник перед смертью отравил бочонок вина, предполагавшегося для отмечания победы, а хан помощника повелел убить, лишь чуть позже случайно узнав о том, что из имевшегося запаса вина (240 бочек) одна бочка отравлена.
Яд имеет такую особенность: если выпьешь даже одну каплю отравленного вина, то обязательно умрешь в течение суток (в любой момент в течение суток).
У хана есть 5 рабов, которыми можно пожертвовать, и 2 суток для выявления неотравленного вина.
Вопрос: сколько бочек (гарантированно безопасного вина) он сможет выкатить на праздник?
Задача, наверное, баянная, хотя поиском найти и не смог. Всяко, кто знает решение - не надо спойлеров.

Logon

Всяко, кто знает решение - не надо спойлеров.
А тем кто не знает?
Я бы предположил, что таких бочек, выкаченных на праздник гарантированно безопасно, может быть 180
ЗЫ. Правда, сейчас подумал, что мой ответ вообще количество работ не учитывает, их должно быть больше одного
ЗЫЗЫ. Не-не, с пятью рабами можно гарантированно 228 бочек выкатить, проверив их за двое суток.
Если еще сутки дать - то выкатить можно будет уже 236 бочек

demiurg

?
Или можно больше?

Oxana-a

откуда у вас 228? у меня получается упрямо 232.
а если повезет, то и все 234-235.

stat64

Я так понимаю: в первый день делят все бочки поровну между 5 рабами т.е. 240/5=48 бочек. Рабы пробуют по капле из своих 48 бочек. Один умирает (яд в его партии). На второй день его партию из 48 бочек делят между оставшимеся 4мя рабами 48/4=12. Опять пробуют - один умирает. Яд в одной из этих 12 бочек. 240-12= 228. Как-то так.

Logon

откуда у вас 228? у меня получается упрямо 232.
а если повезет, то и все 234-235.
Гммм, значит ты по другому решаешь
В первый день рабам дают попробовать из всех бочек, на каждого раба придется 48 штук.
на второй день одним рабом станет меньше - и под подозрением будет только его часть бочек.
Эти 48 делят на 4 оставшихся работ - по 12 на брата, в одно из этих партий и находится яд.
В итоге, по истечению вторых суток забракованы будут только 12 бочек - после которых сканчается второй раб. Соответственно, 240-12=228 гарантированных бочек.
Если им дать третий день, то 3 оставшихся раба разопьют эти 12 бочек- это выявит 4 опасные., рабов останется двое.
На четвертый день можно будет выделить 2 оставшиеся опасные бочки, остается один раб.
Ну и на пятый день проверку можно будет считать завершенной, последний раб (и последние две бочки) либо умрет, выпив из одной из них - тогда это будет отравленная бочка; или останется живым, тогда отравленной будет последняя бочка.
А как у тебя 232 получается?

demiurg

Да, 228 даёт самый примитивный способ.
232 можно, и всего за один день :)

Oxana-a

делим не на 5, а на 6.
получается, что проверим по 40 бочек, если все выжили, то значит в оставшихся 40.
в лучшем случае, живы 5 рабов, в худшем - 4.
и опять делим на 6(на 5 соответственно.
баян, так-то, как со взвешиваниями.

stat64

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

stat64

Блин, голова! :o

demiurg

а если повезет, то и все 234-235.
Если совсем повезёт, то можно и вообще отравленную бочку найти.
А вообще гоню.
Нет, не гоню

Oxana-a

так и на первый) выпить по одной и не напрягаться)

Logon

делим не на 5, а на 6.
красиво :)

var24

С гарантией можно 237 бочек выкатить

Logon

237
А это как? :confused:

demiurg

:)

var24

Вначале - делим на 5 (или на 6, тут уже не важно получается)
Потом у нас есть 48 (или 40) бочек и 4 (4-5) рабов. Дальше дело техники :)

demiurg

А дальше по схеме которую я привёл.
Да, это самое лучшее решение.

Logon

Дальше дело техники
какая техника позволяет получить 237?

Oxana-a

ща посчитаю, мб действительно намного лучше получится.

demiurg

Так 237 получается, :)

Oxana-a

у меня вроде еще лучше получается.
но надо пересчитать.

Oxana-a

еба)
причем, можно улучшить до 239 в достаточно большом числе случаев, но это расписывать долго.
при 212 бочках можно было бы узнать достоверно.

Logon

238, еба)
можешь просветить?

Oxana-a

распишу для 212, для 240 по аналогии, просто надо будет числа где-то удвоить.
1.каждый из 5 рабов выпивает из 16 бочек = 80
2.разбиваем их по группам по 2 человека, таких групп 10, каждая выпивает еще из 8 = 80
3.разбиваем их по группам по 3 человека, таких групп 10, каждая выпивает еще из 4 = 40
4.разбиваем их по группам по 4 человека, таких групп 5, каждая выпивает еще из 2 =10
5.и все вместе пьют из еше 1 бочки. =1
6. и есть еще одна нераспитая бочка) =1
сумма 212
если умер один, то оставшиеся 4 аналогично разпивают его 16 бочек:
1. каждый по 1=4
2. 6 групп из 2х по 1 =6
3. 4 группы из 3х по 1 = 4
4. все пьют еше из одной = 1
5. одна остается нераспитой = 1
сумма 16, узнаем достоверно.
аналогично, если умерли 2, 3 и т.д. рабов

Oxana-a

спасибо гимли за идею.

var24

А, в принципе, можно все за 1 раз проверить.
Т.к., действительно, можно получить не бит информации а больше: умер, выжил, не пил.
3^5=243

Oxana-a

Да, в моих рассуждениях про 212 в первый день не пить не из одной бочки, а из 32, ты прав)

shpanenoc

Т.к., действительно, можно получить не бит информации а больше: умер, выжил, не пил.
Гы-гы, "умер, выжил, не пил, мужик, блондин". Если не пил, то зачем такой раб? :)
На самом деле, если преобразовать версию Гимли в "умер в первый день, умер во второй день, не умер", то, действительно, можно за два дня разделить 3^5 бочки.

komBAR

Печаль. Прочитал задачку перед уходом на четырехчасовой аспирантский английский, пока дошел до него, успел решить для произвольного изначального количества рабов и дней, пока вернулся - уже практически все расписали.
Ну, на всякий случай распишу простой метод для произвольного числа дней и рабов (скорее всего его и имеет в виду).
Пусть у нас k рабов, n дней, (n+1)^k бочек. Нумеруем их в (n+1)-ричной системе счисления, получаются числа из k цифр. В i-й день j-й раб бьет из тех бочек, в которых на j-й позиции стоит цифра i (т.е. каждый раб соответствует собственному разряду, а значение разряда --- дню, в который раб попробует эту бочку).
Если в какой-то день раб должен что-то пить, но уже умер, то мы на него забиваем (это нестрашно, т.к. множества бочек, из которых раб пьет в разные дни, попарно не пересекаются, т.е. если он отравился в один день, то ни в какой другой уже не может отравиться).
Дальше отравленная бочка элементарно восстанавливается --- в ее номере на j-й позиции стоит день смерти j-го раба (или 0, если рабу повезло и он выжил).
Очевидно, что большее число бочек различить нельзя (в смысле если их будет больше, то мы не сможем заведомо найти отравленную) --- для каждого раба у нас есть ровно n+1 вариант (умер в первый день, умер во второй день, ..., умер в н-ный день, выжил итого (n+1)^k расклад всего.
P.S. Разумеется, можно для n дней доказать и по индукции, использовав схему для перехода и воспользовавшись равенством [math]$(n+1)^k = 1 + C_n^1 n + C_n^2 n^2 + \ldots + n^k$ [/math] (собственно, у него оно магическим образом и появилось для n = 2, k = 5)

Oxana-a

не магическим, так же, как у тебя, просто с формальной математикой у меня туго, сочетания считал тож)

demiurg

Вообще, правильный ответ — 228 good enough, чего там париться из-за лишних 11 бочек чтобы лишних трёх рабов убить :)
Наверняка три раба дороже чем 11 бочек :) (Хотя на самом деле не три надо брать, а среднее число выживших)

demiurg

Да, крутая задача.

iri3955

Можно точно найти бочку. Даже если их 243.
А именно [math]$\sum\limits_{i=0}^5 C_5^i2^i = 243$[/math]
А черт, тут уже написали.

radion93

I.
Вообще, правильный ответ — 228 good enough, чего там париться из-за лишних 11 бочек чтобы лишних трёх рабов убить
Наверняка три раба дороже чем 11 бочек (Хотя на самом деле не три надо брать, а среднее число выживших)
Для отравленной бочки - троичная система не пил/пил-в-первый-день-умер/пил-во-второй-день-умер. Рабов 5 => 2/3 * 5 = 33) раба умрут в среднем, если бочек 243. Но бочек 240.
Тогда разумно будет исключить из 3 номера, при которых умираю все рабы. Например - 22222, 22221, 22211. (Цифры - это дни, в которые умирают рабы, которым соответствуют позиции цифр)
Учтем корректировку, (33) * 243 - 15) / 240 = 3,3125, получаем экономию, в среднем, 2,3125 раба на 11 бочек.
Выгодно или нет? Сложно сказать. В условии есть хан, значит, скорее всего, это восток, а значит виноград сами, вряд ли, выращивают. А людей, наоборот, много. С учетом постоянных войн, рабов может быть много. Так что же выгоднее - 2,3 раба или 11 бочек вина?
Можно обратиться к Древнему Риму. Гугл подсказывает, что 1 раб стоил до 500 денаров (динаров, денариев а 1 бочка вина (40 ведер или 492 литра) до 22500 денаров ("Эдикт Диоклетиана о ценах"). Итого, 45 рабов за одну бочку с вином. Но это Древний Рим с их безумием и дешевизной рабов.
II.
Обратимся к условию задачи:
У хана есть 5 рабов, которыми можно пожертвовать
Я хан, у меня есть 240 рабов. Но только 5-ю я могу пожертвовать. И я подхожу под условия. Я пою каждого раба из определенной для него бочки по капле вина. 1 раб умирает,а 239 неотравленных бочек определены и готовы к празднику. Ура!

stm7543347

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

a100243

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

Vlad128

braingames же :)

april75

у меня получилось 238 с таким подходом.
делим 240 бочек на 20 частей, каждый раб берет пробы из своей части (№№1-4, №№4-8 и т.д) и по 1 части от других четверок. Эти части для каждого раба свои, но при этом покрывают также весь спектр бочек, т.о. каждый на этом этапе пробует из 96 бочек, и из каждой бочки пробуют два раза. В результате на 1-м этапе сдыхают 2 раба, а "их" бочки - 12 штук (перекрывание основной четверки для пробы и дополнительной). На втором этапе (дне) осталось 3 раба и 12 бочек. Делим по аналогии на три четверки, каждый раб тоже берет свою основную четверку и по две пробы из каждой оставшихся, всего восемь. Соответственно, сдыхают еще два раба, но остаются всего две бочки, одна из которых с ядом.

a100243

у меня получилось 238 с таким подходом.
243 вышло у меня. Да и остальных вроде тоже
5 рабов могут за один раз проверить 2^5 бочек - 32, 4 - 16 и т.д. Бочки проверяются суперпозицией, когда из одной бочки могут пить несколько рабов и мы смотрим не какой раб умер, а какие из них умерли.
Но это дело можно проверять только в финальный день, потому что после такой проверки с некоторой вероятностью вовсе не останется рабов.
За день до этого мы можем проверить несколько групп бочек, но, разумеется, должны учитывать, сколько в худшем случае рабов выживет.
Рассмотрим числа от 0 до 31, 0 единиц только в одном числе, одна единица в пяти, две единицы в 10, три единицы в 10, четыре единицы в 5, все пять единиц - только в одном случае. Количество единиц указывает на число погибших рабов при испытании вина. Пятеро одновременно могут пить только из одной бочки, потому что никого не останется для тестирования во втором туре.. Вариант с четырьмя единицами приемлем, но в каждом из пяти вариантов рабам на дегустацию надо давать по две бочки, потому что четыре раба умрут в этот тур, а один оставшийся способен разрешить только две бочки но никак не больше. Неотведанных бочек следует оставить 32, поскольку все рабы живы и смогут впятером разрешить 2^32.
Итого получается 1*32+5*16+10*8+10*4+5*2+1*1=243
Ну и как тут заметили (стоит иногда читать тему) по индукции выходит (k+1)^n, где k - количество дней, и n - количество рабов

april75

спасибо, объяснил
зы не мехмат
Оставить комментарий
Имя или ник:
Комментарий: