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