Кошмар трактирщика и 73 бочки.

[e_kaspersky]

Возрадуйтесь! Сегодня будет не просто ещё одна логическая задачка, а задачка на злобу дня :) На этот раз средней сложности. Вот такая:

Ещё одна беда пришла к трактирщику (помимо всеобщего карантина и закрытия общепита).

Стало известно, что чистоплюйные поборники абсолютной нравственности взломали замки на дверях, тайком проникли в погреба

Comments

[interier]

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

[e_kaspersky]

Так дней-то сколько получается?

[chmyrnovich]

после 4х дней

[kitushin]

Получается, что после четвертой "дегустации" (на пятый день) плохая бочка будет найдена (если не повезет раньше).
Но главное - уже на второй день трактирщик сможет торговать алкоголем из не менее, чем 75-15=60 бочек. 😀

[kitushin]

Решение, собственно, такое:

1. Делим бочки на пять групп (15 15 14 14 14).
Из четырех групп даём попить четырем слугам (коктейли из алкоголя из каждой бочки группы). Каждому слуге - коктейль из какой-то одной группы бочек.

2. На утро отбраковываем группу бочек, в которую затесалась отравленная.
Если повезло, то все слуги по-прежнему "алкоголики". Ну или один все же выбыл.

3. Делим плохую группу из 15 (или 14) бочек на 4 подгруппы (4 4 4 3).
Снова поим коктейлями оставшихся 3-х слуг, каждому коктейль из отдельной подгруппы бочек.

4. На третий день мы знаем, в какой подгруппе из 5 или 4 бочек находиться плохая бочка.
Повторяем процедуру с коктейлями для оставшихся двух слуг, разлелив 5 бочек на три группы (2 2 1).

5. Если не повезло, то на четвертый день придется ещё раз выбирать из 2 оставшихся под подозрением бочек, с помощью последнего оставшегося слуги.

Итого, на пятый день мы все узнаем.

[e_kaspersky]

Есть решение за 4 дня.

[master_of_coin]

Хотя у меня методика и не такая оптимальная, но все равно получается пятый день.

День 1.
Делим бочки на равные группы: 18 + 18 + 18+ 18 +1 и делаем купаж, даем каждому из слуг попробовать купажи из 18 ведер. Если кто-то отравился - выводим остальные из карантина и исследуем дальше эту группу, если нет - всем повезло, и отравленная бочка оказалась той самой единственной.

День 2. Осталось трое слуг.

Делим 18 на 3, по 6 на каждого. Один отравится, 12 выводим из карантина и исследуем дальше сомнительные 6.

День 3. Осталось двое слуг.

Делим 6 на 2, один отравится, 3 выводим из карантина и сомнительные три исследуем дальше.

День 4. Остался один слуга и 3 бочки.
Пробуем по одной. Попробовал - не отравился, остались две бочки.

День 5. Остались 2 бочки.
Пробуем одну из них, отравился - это она, не отравился - значит, другая.

[e_kaspersky]

Не самое оптимальное решение, можно быстрее.

[master_of_coin]

ОК, оптимизируем

[e_kaspersky]

Есть решение за 3 дня.

[sir_derryk]

Странное число 73. Можно и 81, по-моему. И все равно два дня.
В каждый день работник может либо отравиться, либо не отравиться. Соответственно, за N дней он может либо отравиться в какой-то из дней, либо не отравиться вообще. Соответственно, каждый работник нам дает N+1 исходов, а 4 работника - N+1 в четвертой степени исходов (если подойти правильно). Итого достаточно двух дней (2 в четвертой меньше 73, 3 в четвертой больше).
Проще всего, наверное, перенумеровать бочки в троичной системе и пусть работник (мы их перенумеруем от 1 до 4) пьет из тех бочек, в которых на его порядковой позиции стоит номер соответствующего дня. Т.е. первый работник в первый день пьет из бочек вида 1ХХХ, второй Х1ХХ и т.д. А во второй, соответственно, 2ХХХ, Х2ХХ и т.д.
А дальше смотрим, кто из работников отравился и когда.

[e_kaspersky]

Неверно! Читайте условие. Троичная система здесь никак не работает.

Кстати, когда мне попалась эта задачка, то там было 64 бочки :)

[sir_derryk]

Перечитал и все равно не понял, чего я не учел. Если вы о том, что после отравления человек в пробах не участвует, то это в алгоритме учитывается

[vnarod]

А где, например, бочка 53? Не помечена?

[korund]

На 4 день.

В первый день поим 13 порциями напитка. 21 бочка в стороне.

Во второй день поим 3 порциями из отравленной части оставшихся трёх слуг или 4 порциями из нейтральных бочек 4 слуг (если все могут пить).

В третий день каждому достанется одна порция при любом варианте.

На 4 день решение известно.

[korund]

В общем случае на любом шаге для расчёта нейтральной части бочек можно поделить общее их число на число слуг. Исходя из этого вычисляется число бочек, из которых должен выпить каждый слуга.

Смысл в том, чтобы размер нейтральной части бочек, которые будут тестировать на следующий день 4 выживших слуги, примерно был пропорционален размеру отравленной части, которую придется тестировать трём оставшимся слугам.

[e_kaspersky]

Всё верно!

Ура!

[ext_1392815]

Поздравляем, вы выиграли)
Пожалуйста, напишите на почту sp@kaspersky.com об этом, чтобы мы могли вас наградить :)