Бородатая задача на чуть новый лад

[buka]

Бородатая задача на чуть новый лад.
Один монарх столкнулся со следующей проблемой.
В его подвалах хранится 1000 бутылок вина, которые должны выпить на следующий день в честь большого праздника. Но стало известно, что в одной бутылке вино отравлено. Любая, даже самая минимальная доза яда смертельна. Яд никак не проявляет себя до момента смерти, которая наступает в срок от 15 до 20 часов после отравления.
Почесал монарх репу и сказал своим мудрецам:
"В вашем распоряжении 99 моих рабов. Делайте что хотите, но до праздника осталось 20 часов и вы за это время обязаны найти отравленную бутылку! Но как гуманист, я требую от вас минимума жертв"
Каков может быть этот минимум в худшем случае (максимум минимума, так сказать) при условии, что мудрецы далеко не лыком шиты?

[Илья]

Что-то может быть лучше двоичного принципа и восьми смертей?

[buka]

Что-то может быть лучше двоичного принципа и восьми смертей?

Можно меньше смертей.
Но как у Вас получилось 8?

[Илья]

Получаем 1+10+45+120+210+252+210+120+45+10+1=1024
Здесь можно пожертвовать первыми двумя и последними двумя слагаемыми.
Остаются проверки, когда могут умереть 2-ое (45бочек), трое (120 бочек), 4-ро (210 бочек), 5-ро (252 бочек), 6-ро (210бочек), 7-ро (120 бочек), 8-мь (45 бочек). Как видим максимум может умереть восемь человек, при наихудшем развитии событий, когда отрава окажется в тех 45 бутылях, которые проверяли группы по 8 человек.

[buka]

Получаем 1+10+45+120+210+252+210+120+45+10+1=1024
Здесь можно пожертвовать первыми двумя и последними двумя слагаемыми.
Остаются проверки, когда могут умереть 2-ое (45бочек), трое (120 бочек), 4-ро (210 бочек), 5-ро (252 бочек), 6-ро (210бочек), 7-ро (120 бочек), 8-мь (45 бочек). Как видим максимум может умереть восемь человек, при наихудшем развитии событий, когда отрава окажется в тех 45 бутылях, которые проверяли группы по 8 человек.

А зачем такое неравномерное разбиение?
1000 бочек может проверить 10 рабами, царство им небесное...
2*500 бочек -> 2*9 рабов, но лишь одна из двух групп того...
4*250 -> 4*8, и т.д...
Тем не менее, фишка даже не в этом...

[Илья]

Тем не менее, фишка даже не в этом...

Я об этом и спрашивал.

[buka]

Тем не менее, фишка даже не в этом...

Я об этом и спрашивал.

Так в этом и вся соль задачи
Сам придумал!

[Илья]

И где это монарх столько мудрецов набрал, аж 99 штук.

[House Fox]

И где это монарх столько мудрецов набрал, аж 99 штук.

Это рабов 99, а мудрецов скорее всего "n"

[Логово педобразов]

2 трупа, 1000=25*40, 40 человек пьют "по вертикали", 25 "по горизонтали", пересечение даст яд.

[buka]

2 трупа, 1000=25*40, 40 человек пьют "по вертикали", 25 "по горизонтали", пересечение даст яд.

Можно и так. Меньше, чем в две смерти не уложиться. Так что браво! 
А если попытаться минимизировать матожидание количества смертей?
У Вас оно - 2. А можно добиться чуть меньше...
И ещё, какое максимальное кол-во бутылок может быть "протестировано" 99 рабами ценой не более 2 смертей?

[Логово педобразов]

Мудрецам нужно привлечь к тестам злого короля, тогда МО будет 1.96

А максимальное количество бутылок вряд-ли отличается от 49х50+1

[buka]

Мудрецам нужно привлечь к тестам злого короля, тогда МО будет 1.96

А максимальное количество бутылок вряд-ли отличается от 49х50+1

МО = 1.899, бутылок: 99*98/2 + 99 + 1 = 4951.
В любом случае Вы молодец.

[Логово педобразов]

Блин, надо было к цешкам возвращаться 

[Логово педобразов]

Хоть что-нибудь правильно напишу: 5052 бутылок можно проверить со средним количеством мертвых не более 2-х