Форум умных людей

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

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

Можно меньше смертей.
Но как у Вас получилось 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 человек.

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

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

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

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

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

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

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

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

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

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

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

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

А вот это уже совсем круто!
Не поделитесь крутизной?
Я до такого кол-ва не допёр... Остановился на 4951 бутылке (98*99/2 + 99 + 1)...

Ключевое слово "средним". Для 4951 гарантированно умирают не более двух, но МО<2, значит можно добавить несколько тройных жертв, оставив среднее количество умерших в пределах двух человек. Естественно, для строгих условий на число 4951 посягать я и не думал  :beer:

А как быть с минимумом максимума? То есть в первую очередь минимизировать максимум жертв? У Вас он получается равным 3...

ну в принципе можно вообще без жертв обойтись. Если каждому рабу дать по 10 бутылок, будет 990, 10 осталось, если через 20 часов 1 сдохнет, надо выкинуть те 10 бутылок которе он пил, а если повезет то не умрет никто, и нужно выкинуть бутылки из остатка)))

Э, почему-то я только сейчас осознал, что у нас не всего 10 мудрецов, а 99 и их всех можно использовать.
Тогда банальная формула С₉₉²=4851 дает нам максимум бутылок и минимум смертей 2 в наихудшем случае. Банальное число сочетаний пиратов. :wall: Ах да, еще из каждой может попить один пират по одному и одну оставить не тронутой. Итого 4851+99+1 :tormoz:

С₉₉² вытекает из столь горячо любимой нами двоичной системы... :)

Да-да, пора переходить на троичную. :)
Если бы до празднества оставалось 40 часов, рабы умирают в течение 10-20 часов после того как приняли яд, и рабов 99, сколько максимум бутылок можно было бы проверить при минимуме смертей?

ответ 1