Есть идея!
Шрифт:
А теперь мы предлагаем вам проверить свою сообразительность на новом замечательном варианте последней задачи. Все условия остаются прежними, за исключением одного: ровно в полдень биолог положил в стерильный контейнер с питательной средой не одну, а три бактерии. Когда наполнится контейнер? Ответ приведен в конце книги.
Загадочная покупка
Когда друзья доехали до дома, где жили родители Элен, она вручила
Элен. Здесь то, что ты собирался купить для дома, папочка!
Мистер Браун. Спасибо, дочка! А сколько это стоило?
Элен. Пятьсот стоили 3 доллара.
Мистер Браун. 3 доллара? Значит, по 1 доллару за штуку.
Элен. Правильно, папочка.
Что, по-вашему, Элен купила в подарок отцу?
Возможно, вы догадались, что слово «пятьсот» может иметь 2 значения: число пятьсот и 3 цифры 500, написанные подряд. Если одна цифра стоит 1 доллар, то 3 цифры стоят 3 доллара: Элен купила три цифры для номера дома, в котором живут ее родители.
Эта задача-шутка наглядно показывает, что в поисках решения иной раз бывает полезно перечитать условия задачи.
Как отгадать номер телефона?
Боб. Кстати, Элен, ты до сих пор не дала мне номер своего нового телефона.
Элен. Ты знаешь, мы уговорились не сообщать его никому, но для тебя я готова нарушить уговор. Можешь задать мне любые 24 вопроса о номере телефона, на которые можно ответить «да» или «нет», и я отвечу на них.
Боб. Помилуй, Элен! Семизначных телефонных номеров почти 10 млн. Как я смогу отгадать один из них, задав всего 24 вопроса?
Элен. Подумай хорошенько, Боб, и я уверена, что ты сумеешь отгадать мой телефонный номер.
Боб не обманул ожиданий Элен и вскоре действительно придумал простой способ, позволяющий отгадывать любой семизначный телефонный номер, задавая не более 24 вопросов. Придумав такой способ, вы сможете испытать его на своих друзьях и знакомых.
Боб догадался, что с помощью вопросов, допускающих ответы «да» и «нет», выделенный элемент множества лучше всего искать, придерживаясь следующей стратегии. Если множество содержит четное число элементов, то его следует разделить на две равные части, содержащие одинаковое число элементов. Если множество содержит нечетное число элементов, то его следует разделить на две части так, чтобы они
Чтобы найти выделенный элемент в множестве из 2 элементов, достаточно задать 1 вопрос, отвечать на который можно только «да» или «нет». В множестве из 4 элементов выделенный элемент будет найден за 2 таких вопроса, в множестве из 8 элементов — за 3 вопроса, в множестве из 16 элементов — за 4 вопроса и т. д. В общем случае n вопросов, допускающих ответы типа «да» или «нет», достаточно, чтобы найти выделенный элемент в множестве из 2n элементов.
В задаче о телефонном номере 24 вопроса позволяют отгадать любое число от 1 до 224 = 16777216, что больше 9999999 — «наибольшего» из семизначных телефонных номеров. Двадцати трех вопросов может не хватить, так как число 223 = 8388608 меньше некоторых семизначных телефонных номеров.
Прежде всего Бобу нужно спросить у Элен: «Номер твоего телефона больше 5000000?» Ответ на этот вопрос позволит Бобу отбросить половину номеров и тем самым вдвое сузить круг дальнейших поисков. Продолжая дихотомию, он заведомо «попадет» в номер телефона Элен, задав не более 24 вопросов.
Большинство людей с трудом верят, что с помощью 24 вопросов, допускающих ответы «да» или «нет», можно отгадать любое число от 1 до 16 777 216, поскольку не сознают, как быстро возрастают члены геометрической прогрессии со знаменателем 2. Именно этот чрезвычайно быстрый рост позволяет сравнительно легко отгадывать, любое задуманное слово, задавая тому, кто его задумал, только вопросы, допускающие ответы «да» или «нет». Если вы достаточно поднаторели в дихотомии, то, хотя задуманное слово может означать что угодно, обычно его можно отгадать, задавая менее 20 вопросов.
Описанную нами процедуру отгадывания семизначного номера телефона специалисты по вычислительной технике называют алгоритмом двоичной сортировки. На том же принципе основан остроумный фокус с отгадыванием чисел. Необходимый реквизит состоит из 6 карточек, показанных на рис. 1.
Пусть кто-нибудь из зрителей задумает любое число от 1 до 64. Вручив ему карточки, попросите отобрать те из них, на которых стоит задуманное им число, и вернуть их вам. Получив карточки, вы сразу же называете задуманное число.
Секрет фокуса открывается просто: вы суммируете числа, стоящие в верхнем левом углу возвращенных вам карточек. Их сумма равна задуманному числу.
Карточки построены по системе, которая станет ясной, если все числа от 1 до 63 записать в двоичной системе, как это показано на рис. 2. Числа слева записаны в десятичной системе. Справа от каждого числа указано, как оно записывается в двоичной системе. Шесть чисел вверху таблицы означают степени числа 2, участвующие в двоичной записи чисел.