Долго я вчера тупила, прежде чем поняла, что есть еще комбинация "никто не пил"... а потом еще тупила, упорно получая две бочки и нету времени проверить.... спать злая легла, но к утру дотумкала.
Пусть рабов зовут a, b,c,d, e. Из них получается 32 неповторяющие комбинации:
a,b,c,d,e,
ab,ac,ad,ae,bc,bd,be,cd,ce, de,
abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde,
abcd,abce,abde,acde,bcde,
abcde и "никто не пил".
Из 4 рабов подобным же образом получится 16 комбинаций, из3 -- 8, из2 -- 4, из 1 -- 2.
Теперь тридцати двум комбинациям раздаем бочки и ждем, какая комбинация отравится:
abcde -- 1 бочку
abcd,abce,abde,acde,bcde -- по 2 бочки для каждой четверки,
abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde -- по 4 бочки для каждой тройки,
ab,ac,ad,ae,bc,bd,be,cd,ce, de -- по 8 бочек для каждой пары,
a,b,c,d,e -- по 16 бочек для каждого.
Всего 211 бочек, 29 бочек для "никто не пил".
Отравили abcde -- бочка найдена, отравилась одна из четверок -- оставшийся пятый проверит 2 бочки, отравилась одна из троек -- двое оставшихся поверяют 4 бочки, отравилась одна из двоек -- трое недотравленых проверяют их 8 бочек, отравился один -- оставшимися четырьмя проверяем его 16 бочек. Все выжили -- для 29 оставшихся бочек имеем 32 комбинации, хватает с избытком.
Сообщение изменил Vilhelmina (29/11/2008 09:30:12)
|
Назад
Конференция
Вперед
Списком
Не люблю комбинаторику...
[ #
Редактировать
Ответить
Цитата
