Король и 1000 бутылок вина: как найти одну отравленную?

Условие задачи

Вы — правитель средневековой империи, и завтра у вас намечается торжество. Это будет самая чумовая вечеринка из всех, что вы когда-либо устраивали. По такому поводу не грех открыть 1000 бутылок вина. Но вот незадача: одна из них отравлена.

У яда нет никаких симптомов, кроме смерти, которая наступает в течение 10–20 часов после принятия даже малейшей дозы яда.

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

Какое минимальное количество заключённых должно попробовать вино из бутылок, чтобы точно найти отравленную в течение 24 часов?

Решение

Спойлер: попробовать вино должны 10 узников.

Пронумеруйте все бутылки в двоичной системе (начиная с нуля). Затем присвойте каждому узнику двоичный флаг. Например, первому — 00000000001, третьему— 00000000100 (чем больше номер узника, тем дальше влево продвигается единица) и т.д. Узники должны сделать глоток из каждой бутылки, в которой попадается их флаг. Например, из восьмой бутылки (0000000111) сделают по глотку первый, второй и третий узники.

Вот как мы бы нашли отравленную бутылку, будь их всего 8:

Если все узники умерли, то отравлена седьмая бутылка (или восьмая, если считать от единицы): номера узников — 001, 010 и 100, нужно найти бутылку, в которой все единицы встречаются на тех же позициях, что и у узников. Это бутылка под номером 111 или же седьмая бутылка в нашей таблице.

Никто не умер — нулевая бутылка. Умерли A и B — яд в третьей бутылке. Не забывайте, что мы нумеруем от нуля.

Для десяти человек существует 1024 уникальные комбинации, так что мы можем проверить до 1024 бутылок вина.

Каждый узник попробует вино примерно из 500 бутылок. Узники должны пить из каждой бутылки не дольше 15 секунд и только небольшое количество вина. Небольшие глотки не просто позволят оставить побольше вина гостям, но и не дадут узникам умереть от алкогольного отравления. Поскольку они выпьют примерно по миллилитру из каждой бутылки, в сумме каждый из них выпьет всего по бутылке.

У узников будет как минимум 50-процентный шанс выжить. Только в одном случае умрут все узники. Также существует 10 комбинаций, в которых умрёт 9 из 10 человек. Таким образом, избегая двух типов этих комбинаций, можно ограничиться смертью максимум восьми узников.

А вы знаете другие решения этой задачи? Делитесь в комментариях.