В минувший вторник мы предложили вам династическую задачу — найти одну-единственную отравленную бутылку из тысячи с помощью десяти кроликов.
Напомним эту животрепещущую историю: жил-был правитель, в погребе которого хранилась тысяча бутылок его любимого сорта вина. Нетерпеливый наследник решил получить трон и подослал в погреб убийцу с ядом, от которого умирают через сутки. Убийцу схватили, но одна из бутылок оказалась отравленной. Правитель решил найти ее с помощью десяти кроликов.
Каким образом?
Ответ.
Мы не зря написали, что задача должна понравиться программистам. Решить ее можно, используя двоичное счисление.
Кролик бинарен: он может быть либо жив, либо мертв, 0 или 1. Так как кроликов у нас десять, мы получаем 2 в степени 10 уникальных комбинаций, то есть 1024. На 24 комбинации больше, чем у нас бутылок. А значит, десяти кроликов вполне хватит.
Надо пронумеровать все бутылки в двоичной системе, используя для этого десять разрядов (обычно-то используют восемь!).
Первая бутылка — 0000000001
Вторая бутылка — 0000000010
Третья бутылка — 0000000011
Тогда 999 бутылка у нас будет 1111100111
Ну, а последняя, тысячная бутылка будет 1111101000
Кроликов тоже нумеруем, только в обычной, десятичной системе, от 1 до 10.
Дальше дадим кроликам вина таким образом: в каком разряде единица — тот кролик и пьет. То есть первый кролик выпьет только из первой бутылки. Второй — только из второй. А вот десятому кролику придется отхлебнуть из бутылок, начиная с 512 по тысячную…
Далее ждем сутки и смотрим, какие кролики погибли. Предположим, у нас скончались седьмой, шестой, пятый и первый кролики. Значит, искомая бутылка будет 0001110001 по счету, то есть 113-я.
До встречи в следующий вторинк!
Подготовила Яна Маевская.
Фото: Наталия Бахарева, изображение создано при помощи ИИ.