Мартин Гарднер - Есть идея! Страница 21

Пусть кто-нибудь из зрителей задумает любое число от 1 до 64. Вручив ему карточки, попросите отобрать те из них, на которых стоит задуманное им число, и вернуть их вам. Получив карточки, вы сразу же называете задуманное число.

Секрет фокуса открывается просто: вы суммируете числа, стоящие в верхнем левом углу возвращенных вам карточек. Их сумма равна задуманному числу.

Карточки построены по системе, которая станет ясной, если все числа от 1 до 63 записать в двоичной системе, как это показано на рис. 2. Числа слева записаны в десятичной системе. Справа от каждого числа указано, как оно записывается в двоичной системе. Шесть чисел вверху таблицы означают степени числа 2, участвующие в двоичной записи чисел.

На рис. 1 в левой верхней карточке выписаны (в десятичной системе) все числа, у которых в последнем столбце их двоичной записи стоит единица. На карточке внизу справа выписаны все числа, у которых единица стоит в первом столбце их двоичной записи. Аналогичным образом устроены и остальные карточки.

Карточки для отгадывания чисел можно составлять на основе не только двоичной, но и любой другой системы счисления. Например, с помощью рис. 3 можно составить карточки для отгадывания любого числа от 1 до 26 на основе троичной системы. Над каждым столбцом справа указана соответствующая степень числа 3 (именно она должна стоять в левом верхнем углу карточки). Если в столбце стоит единица, то число вписывается в нужную карточку один раз. Если в столбце стоит двойка, то число вписывается в карточку дважды.

Три карточки для отгадывания любого числа от 1 до 26, составленные на основе этого правила, приведены на рис. 4.

Пусть кто-нибудь задумает любое число от 1 до 26. Попросите его отобрать карточки с задуманным числом и, возвращая их вам, назвать, сколько раз оно встречается на каждой из них. При суммировании ключевые числа тех карточек, на которых задуманное число встречается дважды, необходимо удвоить.

Возможно, вы захотите расширить набор с трех до шести троичных карточек. Как мы уже знаем, шесть двоичных карточек позволяют отгадывать любое число от 1 до 63. Шесть троичных карточек позволяют отгадывать любое число от 1 до 728. Теперь уже вам ясно, каким образом можно составить карточки для отгадывания чисел на основе системы счисления с любым основанием больше 3. Например, если мы остановим свой выбор на системе счисления с основанием 4, то одни числа будут встречаться на карточках по одному разу, другие — дважды, а третьи — трижды, и при суммировании вам придется одни ключевые числа брать сами по себе (с коэффициентом 1), другие — удвоенными, а третьи — утроенными.

Четверичные карточки показывают, что «троичная сортировка» в некоторых отношениях превосходит двоичную. Если мы будем последовательно делить множество не на 2, а на 3 части и каждый раз нам будут говорить, какая из частей содержит выделенный элемент, то найти его можно, задавая меньше вопросов. Разумеется, сами вопросы становятся более сложными: если раньше они требовали «двоичных» ответов («да» или «нет»), то теперь ответ на каждый вопрос должен быть «троичным».

Необычайные возможности, таящиеся в троичной сортировке, наглядно демонстрирует следующий карточный фокус. Пусть кто-нибудь из зрителей задумает любую из 3³ = 27 отобранных вами карт. Сдайте отобранные карты в три стопки, переворачивая каждую карту перед тем, как выложить ее на стол, вверх лицом, попросите зрителя указать, в какой из стопок находится задуманная им карта, после чего сложите стопки вместе и повторите всю процедуру еще дважды. Сложив стопки в третий раз, попросите зрителя назвать вслух задуманную карту и, сняв верхнюю карту, покажите ее всем зрителям. У вас в руках окажется задуманная карта! Фокус можно показывать сколько угодно раз, не опасаясь «осечек» — их нет и быть не может!

Секрет фокуса прост: необходимо лишь всякий раз, когда вы складываете стопки, держа карты вверх рубашкой, стопку с задуманной картой класть поверх остальных. Неукоснительно придерживаясь этого правила, вы будете автоматически производить троичную сортировку карт, которая и заставит «всплыть» задуманную карту из глубин.

Нетрудно понять, почему так происходит. Принцип здесь тот же, что и при отгадывании телефонного номера, только множество делится каждый раз не на две, а на три равные или почти равные части. После первой сдачи задуманная карта оказывается среди 9 верхних карт, после второй сдачи она оказывается уже среди 3 верхних карт, а после третьей сдачи оказывается первой картой сверху. Если вы проделаете всю процедуру от начала до конца, держа карты вниз рубашкой и сдавая их снизу, то сможете наблюдать, как задуманная карта постепенно, в три этапа, спускается «на дно» перевернутой мини-колоды. Автоматическая сортировка элементов различных множеств, основанная на аналогичных принципах, играет важную роль в современной информатике — науке о накоплении, хранении и обработке информации.

Унесенная ветром

Боб и Элен решили провести летние каникулы в лесах штата Мэн, где в хижине жил дядюшка Генри.

Чтобы добраться до хижины, Бобу и Элен пришлось нанять лодку и идти на веслах вверх по течению.

Разумеется, грести вызвался Боб, а Элен села на руль. В 2 часа дня Элен сняла свою новую соломенную шляпку и повесила ее на румпель у себя за спиной.

Порывом ветра шляпку унесло, но ни Элен, ни Боб не заметили, когда это случилось.

Они успели отмахать на веслах 3 км вверх по течению, прежде чем Элен вспомнила о шляпке.

Элен. Стой! Где моя новая шляпка? Должно быть, ее унесло ветром.

Делать нечего! Пришлось повернуть назад. Боб налег на весла, и некоторое время спустя лодка настигла шляпку, плывшую по реке.

Предположим, что лодка всегда движется по воде со скоростью 6 км/ч, а скорость течения реки 2 км/ч.

В котором часу Боб и Элен догнали шляпку?

Вам удалось набрести на какую-нибудь идею, позволяющую легко и просто решить задачу? Хотите верьте, хотите проверьте, но течение одинаково сказывается на движении лодки и шляпки, и его воздействием можно пренебречь.

Значит, задачу можно решать так, как если бы лодка двигалась в стоячей воде, Боб и Элен уплыли от шляпки на расстояние 3 км, а затем вернулись, заметив пропажу. Их путь туда и обратно составил 6 км.

Так как лодка развивает скорость 6 км/ч, то весь путь туда и обратно Боб и Элен проделали за 1 ч. Следовательно, когда Элен выудила из воды шляпку, было 3 часа дня.

Потеряв шляпку, Элен и Боб сначала уплывают от нее вверх по реке, а затем, обнаружив пропажу, пускаются вдогонку за шляпкой вниз по реке. Время, затрачиваемое ими на весь путь туда и обратно (от шляпки и к шляпке), не зависит от скорости течения реки, потому что шляпка плывет по течению. В другом варианте задачи путь туда и обратно отсчитывается не от предмета, плывущего по течению, а от какого-нибудь неподвижного предмета на берегу.

Предположим, что никакого течения в реке нет. Боб и Элен идут на веслах 3 км вверх по реке от того места, где они взяли напрокат лодку, затем поворачивают и возвращаются назад. Весь путь туда и обратно занимает у них 20 мин.

Предположим теперь, что река, как ей и положено, течет от истока к устью со скоростью 2 км/ч, как в нашей задаче. Боб и Элен сначала поднимутся на веслах на 3 км вверх по реке, а затем снова вернутся туда, где взяли напрокат лодку. Сколько времени им придется затратить на весь путь туда и обратно на этот раз: больше или меньше 20 мин?

Трудно устоять перед искушением и не сказать, что время в пути останется прежним (20 мин), пояснив свою мысль примерно так: при движении вверх по реке течение уменьшает скорость лодки ровно на столько, на сколько увеличивает скорость лодки, идущей вниз по реке.

Это рассуждение не верно. Почему?

Правильное решение задачи мы получим, приняв во внимание, что на преодоление 3 км вверх по реке уходит больше времени, чем на преодоление тех же 3 км при движении вниз по реке. Следовательно, течение замедляет лодку дольше, чем подгоняет ее, и на путь туда и обратно по проточной воде требуется больше времени, чем на тот же путь в стоячей воде. Наш вывод нетрудно проверить, записав соответствующие алгебраические уравнения.

Те же соображения применимы к задачам о самолетах, летящих по ветру и против ветра. Если на преодоление расстояния из A в B и обратно в безветренную погоду самолет затрачивает определенное время, то на преодоление того же пути в ветреную погоду времени потребуется заведомо больше независимо от того, куда дует ветер: от A к B или от B к A.