Текст книги "Есть идея!"

Автор книги: Мартин Гарднер

сообщить о нарушении

Текущая страница: 8 (всего у книги 17 страниц)

Глаза и ноги

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

Выйдя из зоопарка, Боб обратился к Элен.

Боб. Ты не пересчитала жирафов и страусов?

Элен. Нет, а сколько их было?

Боб. Сосчитай сама. Всего у страусов и жирафов было 80 глаз и 44 ноги.

Элен сразу сообразила: 30 глаз означает, что в вольере было 15 животных.

Элен. Я могла бы перебрать все возможные случаи от 6 жирафов и 15 страусов до 15 жирафов и 0 страусов, но в этом нет надобности.

Элен. Если бы все 15 животных ходили на 2 ногах, то всего у них было бы 30 ног.

Элен. Но ты, Боб, сказал, что у 15 животных 44 ноги, поэтому 14 ног «лишних». Они могут принадлежать только жирафам. Значит, в вольере 7 жирафов.

Боб. Все правильно! А раз в вольере 7 жирафов, то страусов должно быть 8.

Двуногие и четвероногие

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

А вот забавная головоломка, придуманная по образу и подобию предыдущей задачи, но требующая для решения иного подхода. На арене небольшого цирка выступает группа наездников. Если пересчитать участников номера (лошадей и всадников) по головам и ногам, то всего наберется 18 голов и 50 ног. Кроме того, в зверинце при цирке содержатся дикие животные. Если пересчитать их по головам и ногам, то получится 11 голов и 20 ног. Среди них четвероногих вдвое больше, чем двуногих. Сколько наездников и лошадей выступает в цирке и сколько диких животных содержится в его зверинце?

Вы без особого труда найдете, что в цирке выступают 11 наездников на 7 лошадях. Но когда вы попытаетесь определить число диких животных, то, к своему удивлению, получите отрицательное число.

Удастся ли вам решить задачу самостоятельно, не заглядывая в конец книги?

Столкновение на полном ходу

Когда друзья дошли до того места, где стояла спортивная машина Боба, он предложил подвести Элен к дому, куда недавно переехали ее родители.

По дороге Боб придумал для Элен хорошую задачку.

Боб. Видишь вой тот грузовик впереди? Он гонит вовсю, но я постараюсь его догнать.

Боб. Предположим, что грузовик делает 65 км/ч, а я еду со скоростью 80 км/ч.

Боб. Предположим также, что мы находимся сейчас в 1500 м от грузовика.

Боб. Если шофер грузовика и я будем выдерживать каждый свою скорость и я не сверну, мы заведомо врежемся в грузовик. Вот тебе и задачка, Элен: на каком расстоянии от грузовика мы будем за 1 мин до столкновения?

Элен. Ты мог бы придумать задачку потруднее. За 1 мин до столкновения нас будет разделять 250 м.

Элен не ошиблась. Не можете ли вы объяснить, каким образом она сумела так быстро решить задачу?

От конца к началу

Разумеется, задачу можно решать алгебраически, хотя решение получается довольно громоздким. Элен придумала неожиданный ход, позволивший получить ответ, не прибегая к алгебре: она догадалась, что задачу можно решать от конца к началу!

Грузовик развивает скорость 65 км/ч, а Боб едет со скоростью 80 км/ч. Следовательно, Боб движется относительно грузовика со скоростью 15 км/ч, или 15 000 м/ч, что составляет 250 м/мин. Значит, за минуту до столкновения легковая машина, в которой едут Боб и Элен, находится в 250 м позади грузовика.

Мы знаем также, что, когда Боб закончил рассказывать Элен задачу, их автомашина находилась в 1,5 км позади грузовика, но эта информация не нужна для решения задачи: ответ получается одним и тем же независимо от начального расстояния между машинами.

Следующие две классические головоломки также решаются «обратным ходом».

1. Два космических корабля сближаются, двигаясь по прямой навстречу друг другу. Один корабль летит со скоростью 8 км/мин, другой – со скоростью 12 км/мин. Предположим, что в некоторый момент времени корабли находятся на расстоянии ровно 5000 км друг от друга. На каком расстоянии они будут находиться друг от друга за 1 мин до столкновения?

В этой задаче так же, как и в предыдущей, ответ не зависит от начального расстояния между кораблями. Оно лишь вводит людей в заблуждение, поскольку те начинают думать, будто задачу нужно решать, следя за тем, как уменьшается со временем расстояние между кораблями. Задача решается легко и просто, если понять, что корабли сближаются со скоростью 20 км/мин и, следовательно, за 1 мин до столкновения они будут находиться на расстоянии 20 км друг от друга.

2. Некоему специалисту по молекулярной биологии удалось вывести редкую разновидность бактерий. Ежечасно каждая бактерия делится на 3 части, причем каждая часть мгновенно достигает размеров взрослой бактерии и час спустя претерпевает деление на 3 части.

Ровно в полдень биолог положил 1 бактерию в стерильный контейнер с питательной средой. К полночи контейнер оказался наполненным бактериями до отказа. Когда контейнер наполнился на одну треть?

Как и предыдущие задачи, эта головоломка решается «обратным ходом»; ясно, что на одну треть контейнер заполнился к 11 часам вечера, за час до полуночи.

А теперь мы предлагаем вам проверить свою сообразительность на новом замечательном варианте последней задачи. Все условия остаются прежними, за исключением одного: ровно в полдень биолог положил в стерильный контейнер с питательной средой не одну, а три бактерии. Когда наполнится контейнер? Ответ приведен в конце книги.

Загадочная покупка

Когда друзья доехали до дома, где жили родители Элен, она вручила отцу сверток.

Элен. Здесь то, что ты собирался купить для дома, папочка!

Мистер Браун. Спасибо, дочка! А сколько это стоило?

Элен. Пятьсот стоили 3 доллара.

Мистер Браун. 3 доллара? Значит, по 1 доллару за штуку.

Элен. Правильно, папочка.

Что, по-вашему, Элен купила в подарок отцу?

Плата поштучно

Возможно, вы догадались, что слово «пятьсот» может иметь 2 значения: число пятьсот и 3 цифры 500, написанные подряд. Если одна цифра стоит 1 доллар, то 3 цифры стоят 3 доллара: Элен купила три цифры для номера дома, в котором живут ее родители.

Эта задача-шутка наглядно показывает, что в поисках решения иной раз бывает полезно перечитать условия задачи.

Как отгадать номер телефона?

Боб. Кстати, Элен, ты до сих пор не дала мне номер своего нового телефона.

Элен. Ты знаешь, мы уговорились не сообщать его никому, но для тебя я готова нарушить уговор. Можешь задать мне любые 24 вопроса о номере телефона, на которые можно ответить «да» или «нет», и я отвечу на них.

Боб. Помилуй, Элен! Семизначных телефонных номеров почти 10 млн. Как я смогу отгадать один из них, задав всего 24 вопроса?

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

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

Дихотомия, или разбиение на две части

Боб догадался, что с помощью вопросов, допускающих ответы «да» и «нет», выделенный элемент множества лучше всего искать, придерживаясь следующей стратегии. Если множество содержит четное число элементов, то его следует разделить на две равные части, содержащие одинаковое число элементов. Если множество содержит нечетное число элементов, то его следует разделить на две части так, чтобы они как можно меньше отличались по числу элементов. После того как множество разделено на две части, следует спросить, указывая на одну из них, содержится ли в ней выделенный элемент. Получив ответ и выбрав ту из двух частей, которая содержит выделенный элемент, надлежит повторить всю процедуру сначала. После конечного числа шагов (зависящего от числа элементов в исходном множестве) останется подмножество, содержащее только выделенный элемент – тот самый, который требовалось найти.

Чтобы найти выделенный элемент в множестве из 2 элементов, достаточно задать 1 вопрос, отвечать на который можно только «да» или «нет». В множестве из 4 элементов выделенный элемент будет найден за 2 таких вопроса, в множестве из 8 элементов – за 3 вопроса, в множестве из 16 элементов – за 4 вопроса и т. д. В общем случае n вопросов, допускающих ответы типа «да» или «нет», достаточно, чтобы найти выделенный элемент в множестве из 2ⁿ элементов.

В задаче о телефонном номере 24 вопроса позволяют отгадать любое число от 1 до 2²⁴ = 16777216, что больше 9999999 – «наибольшего» из семизначных телефонных номеров. Двадцати трех вопросов может не хватить, так как число 2²³ = 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), другие – удвоенными, а третьи – утроенными.

Четверичные карточки показывают, что «троичная сортировка» в некоторых отношениях превосходит двоичную. Если мы будем последовательно делить множество не на 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.

Не менее известна еще одна хорошая задача на относительное движение. Девушка садится в последний вагон поезда. Обнаружив, что все места в вагоне заняты, она оставляет в тамбуре тяжелый чемодан и в тот самый момент, когда за окном проплывает фабрика детских игрушек «Зайки из байки», отправляется на поиск свободного места, идя размеренным шагом, и через 5 мин доходит до первого вагона. Убедившись, что свободных мест нигде нет, девушка поворачивается и идет назад с той же скоростью. В тот момент, когда она возвращается к чемодану, за окном мелькает магазин бакалейных товаров «Супы, крупы и ступы», находящийся от фабрики «Зайки из байки» на расстоянии 5 км. С какой скоростью идет поезд?

Решение этой задачи аналогично решению задачи о шляпке Элен, унесенной ветром: знать, с какой скоростью идет девушка по вагонам и какое расстояние ей приходится пройти, совсем не нужно. Путь туда и обратно она проделывает за 10 мин. Следовательно, ее чемодан проезжает 5 км за 10 мин. Значит, поезд идет со скоростью 0,5 км/мин, или 30 км/ч.

А вот малоизвестная задача на относительное движение, способная поставить в тупик даже сильных математиков. Юноша и девушка участвуют в забеге на 100 м. К тому моменту, когда девушка пересекает линию финиша, юноша успевают пробежать 95 м, и девушка выигрывает забег с преимуществом в 5 м.

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

Если вы думаете, что оба участника забега пересекли линию финиша одновременно, то мы настоятельно рекомендуем поразмыслить над задачей еще немного. Может быть, вы все-таки догадаетесь, как правильно решить эту задачу? (Указание: где девушка догонит юношу?)

Еще одна забавная задачка рассказывает о божьей коровке, отравленной какими-то химикалиями и утратившей способность ориентироваться в пространстве. Божья коровка находится на одном конце метровой рейки и хочет доползти до другого конца. Каждую секунду она проползает 3 см вперед и 2 см назад. За сколько времени она доползет до другого конца рейки? (Те, кто думает, что это произойдет через 100 с, ошибаются!)