Задача о патриции и отравленной бочке

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

Через n дней патрицию предстоит поставить вино на пир, до этого момента крайне желательно идентифицировать отравленную бочку (возможно, и из этой бочки имеет смысл захватить пару бутылей). Начальное число рабов, которыми располагает патриций для экспериментов, k (n и k натуральные).

• 1. Какое максимальное число бочек можно гарантировано проверить в срок?

  2. С какой вероятностью при макс. числе бочек патриций к началу пира перестанет быть рабовладельцем? Какова вероятность досрочного окончания проверки?

Решение.

Информация, которую можно получить от раба - день его смерти или отсутствие таковой. Значит, (n+1)^k - оценка сверху числа бочек, иначе двум или более бочкам будет соответствовать одинаковая комбинация смертей рабов. Существует алгоритм, обеспечивающий проверку данного числа бочек. Пронумеруем бочки в системе счисления по основанию n+1, что будет записано посредством k разрядов (т.е. на первых позициях будут, если необходимо, нули).

За каждым из рабов закрепляется определенный разряд. В j-тый день до пира раб выпивает по кубку из тех бочек, в которых на месте присвоенного ему разряда стоит цифра j. Т.е. смерть раба определяет данный разряд в номере искомой бочки. Если раб так и не умер, в соответствующей позиции стоит ноль. Если нулей в номере бочки не оказалось, то наступил страховой случай - патриций перестал быть рабовладельцем. Для записи числа без нулей требуется n знаков, всего таких чисел - n^k, значит, вероятность - [n/(n+1)]^k. Досрочное проведение техосмотра состоится, если в номере бочки также отсутствует единица, вероятность - [(n-1)/(n+1)]^k

Конструктивные издержки предложенного алгоритма.

Каждый день живой раб выпивает (n+1)^k-1 кубков. Учитывая, что мат. ожидание продолжительности участия раба в эксперименте n/2 + n/(n+1) дней, то коллектив рабов может нанести погребу патриция больший, по сравнению со злоумышленником, урон. Столь значительные издержки связаны с тем, что рабы по мере приближения пира начинают пить халявное вино из заведомо безопасных бочек. Конечно, рачительный патриций может метить уже проверенные бочки, но это будет сопряжено с рядом организационных трудностей, так как территориально "хорошие" и "подозрительные" бочки не будут сгруппированы. Вообще, ведение учета при такой наивной стратегии - дело весьма кропотливое.

Оптимизированный алгоритм. Биномиальные коэффициенты на службе Древнего Рима.

Всего бочек (1+n)^k. Это бином Ньютона, который раскрывается в сумму Cⁱ_k*nⁱ, где C - число сочетаний, i - число выживших на данном этапе рабов. Бытовой смысл формулы предельно прост - каждое слагаемое показывает сколько бочек будет распиваться ровно k-i рабами. Т.е. все рабы пригубят из C⁰_k*n⁰=1 бочки, а C^k_k*n^k=n^k бочек пока останутся нетронутыми.

Преимущества:

• • "подозрительные" бочки будут располагаться рядом,

  • не потребуется сквозная нумерация,

  • рабы будут меньше страдать от алкогольной интоксикации.