Дмитрий Медведев готовится к церемонии вступления в должность одного своего друга, которая состоится через 2 месяца. В качестве подарка он подготовил 1000 бутылок дорогого французского вина.
Совершенно случайно он узнал, что в одну из бутылокагенты Госдепа недоброжелатели подмешали споры оранжевой чумы. Тот, кто выпьет отравленного вина из этой бутылки, ровно через 2 месяца станет совершенно оранжевым на всю жизнь, а до этого момента яд никак себя не проявляет. К сожалению, Дмитрий Медведев не знает, какая именно из бутылок отравлена, а найти её по внешнему виду или запаху невозможно.
В распоряжении Дмитрия Медведева есть 10оппозиционеров подопытных кроликов. Он хочет за оставшиеся до церемонии 2 месяца вычислить отравленную бутылку, а остальные 999 подарить. Что он должен для этого сделать?
Решение
Если бы кроликов было бы столько же, сколько и бутылок, то решение задачи было бы тривиальным. Даём очередному кролику попробовать вина из очередной бутылки (у каждого кролика своя бутылка), а через 2 месяца смотрим, кто из них заболеет.
Поскольку испытуемых всего 10, давать каждому только по одной бутылке - бессмысленная трата времени. Но если подопытный выпил вина из двух бутылок и в конце концов заболел, как определить, которая из бутылок стала причиной?
Можно дать попробовать вина из одной из бутылок двум кроликам. Допустим, что кролик А выпил вина из бутылок 1 и 3, а кролику Б дали вино из бутылок 2 и 3. Если заболеет только кролик А, то отравлена 1-я бутылка. Если же заболеют и А и Б, то отравлена бутылка номер 3.
Отсюда уже недалеко до решения задачи.
Пронумеруем кроликов от 1 до 10, а бутылки от 1 до 1000. Запишем номер каждой бутылки в двоичной системе счисления. Поскольку всего бутылок 1000, нам хватит для этого 10 двоичных разрядов, а если разрядов в числе меньше, будем дополнять запись ведущими нулями. Кролик номер i получит вино из очередной бутылки тогда и только тогда, когда i-й разряд в двоичной записи номера бутылки - единица.
Например, бутылку номер 15410 = 00100110102 получат кролики с номерами 3, 6, 7 и 9.
Через два месяца выстроим кроликов в ряд и посмотрим, кто из них стал оранжевым. Заболевших будем считать за 1, а здоровых за 0. Составленное таким образом двоичное число даст номер отравленной бутылки.
Например, если заболели кролики 2, 5, 6, 8 и 10, то отравлена бутылка номер 01001101012 = 30910.
Совершенно случайно он узнал, что в одну из бутылок
В распоряжении Дмитрия Медведева есть 10
Решение
Если бы кроликов было бы столько же, сколько и бутылок, то решение задачи было бы тривиальным. Даём очередному кролику попробовать вина из очередной бутылки (у каждого кролика своя бутылка), а через 2 месяца смотрим, кто из них заболеет.
Поскольку испытуемых всего 10, давать каждому только по одной бутылке - бессмысленная трата времени. Но если подопытный выпил вина из двух бутылок и в конце концов заболел, как определить, которая из бутылок стала причиной?
Можно дать попробовать вина из одной из бутылок двум кроликам. Допустим, что кролик А выпил вина из бутылок 1 и 3, а кролику Б дали вино из бутылок 2 и 3. Если заболеет только кролик А, то отравлена 1-я бутылка. Если же заболеют и А и Б, то отравлена бутылка номер 3.
Отсюда уже недалеко до решения задачи.
Пронумеруем кроликов от 1 до 10, а бутылки от 1 до 1000. Запишем номер каждой бутылки в двоичной системе счисления. Поскольку всего бутылок 1000, нам хватит для этого 10 двоичных разрядов, а если разрядов в числе меньше, будем дополнять запись ведущими нулями. Кролик номер i получит вино из очередной бутылки тогда и только тогда, когда i-й разряд в двоичной записи номера бутылки - единица.
Например, бутылку номер 15410 = 00100110102 получат кролики с номерами 3, 6, 7 и 9.
Через два месяца выстроим кроликов в ряд и посмотрим, кто из них стал оранжевым. Заболевших будем считать за 1, а здоровых за 0. Составленное таким образом двоичное число даст номер отравленной бутылки.
Например, если заболели кролики 2, 5, 6, 8 и 10, то отравлена бутылка номер 01001101012 = 30910.
Комментариев нет:
Отправить комментарий