Есть идея! - [33]
Четверичные карточки показывают, что «троичная сортировка» в некоторых отношениях превосходит двоичную. Если мы будем последовательно делить множество не на 2, а на 3 части и каждый раз нам будут говорить, какая из частей содержит выделенный элемент, то найти его можно, задавая меньше вопросов. Разумеется, сами вопросы становятся более сложными: если раньше они требовали «двоичных» ответов («да» или «нет»), то теперь ответ на каждый вопрос должен быть «троичным».
Необычайные возможности, таящиеся в троичной сортировке, наглядно демонстрирует следующий карточный фокус. Пусть кто-нибудь из зрителей задумает любую из 3³ = 27 отобранных вами карт. Сдайте отобранные карты в три стопки, переворачивая каждую карту перед тем, как выложить ее на стол, вверх лицом, попросите зрителя указать, в какой из стопок находится задуманная им карта, после чего сложите стопки вместе и повторите всю процедуру еще дважды. Сложив стопки в третий раз, попросите зрителя назвать вслух задуманную карту и, сняв верхнюю карту, покажите ее всем зрителям. У вас в руках окажется задуманная карта! Фокус можно показывать сколько угодно раз, не опасаясь «осечек» — их нет и быть не может!
Секрет фокуса прост: необходимо лишь всякий раз, когда вы складываете стопки, держа карты вверх рубашкой, стопку с задуманной картой класть поверх остальных. Неукоснительно придерживаясь этого правила, вы будете автоматически производить троичную сортировку карт, которая и заставит «всплыть» задуманную карту из глубин.
Нетрудно понять, почему так происходит. Принцип здесь тот же, что и при отгадывании телефонного номера, только множество делится каждый раз не на две, а на три равные или почти равные части. После первой сдачи задуманная карта оказывается среди 9 верхних карт, после второй сдачи она оказывается уже среди 3 верхних карт, а после третьей сдачи оказывается первой картой сверху. Если вы проделаете всю процедуру от начала до конца, держа карты вниз рубашкой и сдавая их снизу, то сможете наблюдать, как задуманная карта постепенно, в три этапа, спускается «на дно» перевернутой мини-колоды. Автоматическая сортировка элементов различных множеств, основанная на аналогичных принципах, играет важную роль в современной информатике — науке о накоплении, хранении и обработке информации.
Унесенная ветром
Боб и Элен решили провести летние каникулы в лесах штата Мэн, где в хижине жил дядюшка Генри.
Чтобы добраться до хижины, Бобу и Элен пришлось нанять лодку и идти на веслах вверх по течению.
Разумеется, грести вызвался Боб, а Элен села на руль. В 2 часа дня Элен сняла свою новую соломенную шляпку и повесила ее на румпель у себя за спиной.
Порывом ветра шляпку унесло, но ни Элен, ни Боб не заметили, когда это случилось.
Они успели отмахать на веслах 3 км вверх по течению, прежде чем Элен вспомнила о шляпке.
Элен. Стой! Где моя новая шляпка? Должно быть, ее унесло ветром.
Делать нечего! Пришлось повернуть назад. Боб налег на весла, и некоторое время спустя лодка настигла шляпку, плывшую по реке.
Предположим, что лодка всегда движется по воде со скоростью 6 км/ч, а скорость течения реки 2 км/ч.
В котором часу Боб и Элен догнали шляпку?
Вам удалось набрести на какую-нибудь идею, позволяющую легко и просто решить задачу? Хотите верьте, хотите проверьте, но течение одинаково сказывается на движении лодки и шляпки, и его воздействием можно пренебречь.
Значит, задачу можно решать так, как если бы лодка двигалась в стоячей воде, Боб и Элен уплыли от шляпки на расстояние 3 км, а затем вернулись, заметив пропажу. Их путь туда и обратно составил 6 км.
Так как лодка развивает скорость 6 км/ч, то весь путь туда и обратно Боб и Элен проделали за 1 ч. Следовательно, когда Элен выудила из воды шляпку, было 3 часа дня.
Потеряв шляпку, Элен и Боб сначала уплывают от нее вверх по реке, а затем, обнаружив пропажу, пускаются вдогонку за шляпкой вниз по реке. Время, затрачиваемое ими на весь путь туда и обратно (от шляпки и к шляпке), не зависит от скорости течения реки, потому что шляпка плывет по течению. В другом варианте задачи путь туда и обратно отсчитывается не от предмета, плывущего по течению, а от какого-нибудь неподвижного предмета на берегу.
Предположим, что никакого течения в реке нет. Боб и Элен идут на веслах 3 км вверх по реке от того места, где они взяли напрокат лодку, затем поворачивают и возвращаются назад. Весь путь туда и обратно занимает у них 20 мин.
Предположим теперь, что река, как ей и положено, течет от истока к устью со скоростью 2 км/ч, как в нашей задаче. Боб и Элен сначала поднимутся на веслах на 3 км вверх по реке, а затем снова вернутся туда, где взяли напрокат лодку. Сколько времени им придется затратить на весь путь туда и обратно на этот раз: больше или меньше 20 мин?
Трудно устоять перед искушением и не сказать, что время в пути останется прежним (20 мин), пояснив свою мысль примерно так: при движении вверх по реке течение уменьшает скорость лодки ровно на столько, на сколько увеличивает скорость лодки, идущей вниз по реке.
Это рассуждение не верно. Почему?
