Экспресс-тренинг
Подготовка к ЕГЭ-2022 по профильной математике в кратчайшие сроки!
До экзамена осталось совсем немного времени! Закрепите свои знания! Понятная теория и эффективные тренажеры с объяснением! Вы успеете подготовиться на 80+ баллов!
design_arrow
О королевах, ядах и двоичном коде

О королевах, ядах и двоичном коде

Многие маленькие девочки мечтают стать прекрасными принцессами из Средневековых замков, а маленькие мальчики видят себя рыцарями в сверкающих доспехах. Но большинство из нас еще из школьных уроков истории знает, что настоящее Средневековье выглядело совсем иначе, чем детские мечты. Давайте обратимся сегодня к одному из самых популярных средневековых способов устранить противника – и это отнюдь не рыцарский поединок.

Главным оружием в бесконечных придворных интригах и даже во внешней политике нередко становились всевозможные яды – достаточно вспомнить знаменитую французскую королеву Екатерину Медичи. Сегодня нам с вами предстоит попытаться спасти ее очередную жертву – адмирала Колиньи.

Итак, обрисуем проблему: в погребах замка Колиньи, славящихся своими винами, находится тысяча одинаковых бутылок красного вина, которое на следующий день предстоит подать к столу. Однако чудом адмиралу стало известно, что в одну из бутылок служащий королевы добавил яд. Было решено проверять каждую из них на мышах, вот только слугам удалось поймать живыми всего десяток будущих подопытных. Единственную отравленную бутылку необходимо найти всего за сутки, а яд действует долго – проверить бутылки поочередно не получится. Что же делать адмиралу, ставшему неугодным королеве? Неужели положиться на волю случая – ведь вероятность выжить очень близка к единице?

Конечно же, нет – ведь на помощь уже пришли мы! На первый взгляд, ситуация очень напоминает задачи про фальшивую монету, которую нужно определить при помощи чашечных весов – и в этот раз чутье вас не подводит. Алгоритм действий будет очень схож с описанным в статье «Чашечные весы и теория информации».

Наверное, одной из первых ассоциаций со словом «информация» у многих из нас является двоичный код – именно его нам с вами и предстоит сегодня использовать. В первую очередь рассадим мышей в клетки и пронумеруем их. Теперь каждой бутылке мы можем поставить в соответствие набор чисел – номера мышей, которые попробуют из нее вино. Представим этот набор как цепочку нулей и единиц – если k-той справа цифрой оказывается 1, то нужно дать вино из бутылки k-той мыши. Как сделать такие цепочки уникальными для каждой бутылки? Ответ на этот вопрос оказывается неожиданно простым – достаточно пронумеровать бутылки в двоичной системе счисления и добавить ведущие нули. Так как 1000 < 1024 = 2^10, то все номера займут не больше 10 двоичных разрядов – это означает, что для такого эксперимента нам понадобится только 10 мышей. Вот что у нас получилось:

       1 = 0000000001 – вино из первой бутылки пробует только первая мышь
       2 = 0000000010 – вино из второй бутылки пробует только вторая
       3 = 0000000011 – из третьей нужно напоить и первую, и вторую мышь
         …
1000 = 1111101000 – из тысячной бутылки вино попробуют 4, 6, 7, 8, 9 и 10 мыши

Итак, что мы получим в результате? Погибнут те и только те мыши, которые пробовали отравленное вино – отметим их единицами, а выживших – нулями. Мы с вами вновь получили двоичный код, а именно – номер отравленной бутылки. Убедитесь сами: только для нее номера попробовавших и не пробовавших вино мышей будут соответствовать погибшим и выжившим зверькам. Что ж, уверяем вас, в этот раз адмирал Колиньи спасен от знаменитой отравительницы! К сожалению, позже адмирал станет одним из первых погибших в Варфоломеевскую ночь, однако это уже совсем другая история.