WWW.KNIGA.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Онлайн материалы
 

Pages:   || 2 | 3 |

«О 1/ Mr Grnr ai a e nd t A A IS H H! NI TG Set A en FW H8r a « cn mia. Irni. 1 F n n i c S n co.7 e d f c cs 9 m i rn / c aa. Мартин Гарднер ЕСТЬ ИДЕЯ! ...»

-- [ Страница 1 ] --

О

1/

Mr Grnr

ai a e

nd

t

A A IS H

H! NI TG

Set A en FW H8r a «

cn mia. Irni. 1 F n n

i c S n co.7 e d

f c cs 9 m

i rn / c

aa.

Мартин Гарднер

ЕСТЬ ИДЕЯ!

Перевод с английского

Ю. А. ДАНИЛОВА

МОСКВА «МИР» 1982

ББК 22.1

Г 20

УДК 51-8

Гарднер М.

20 Есть идея!: Пер. с англ./Перевод Данилова Ю. А. — М. : Мир, 1982.—305 с, ил.

Книга известного американского популяризатора науки Map*

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

Рассчитана на самый широкий круг читателей.

Редакция научно-популярной и научно-фантастической литературы © 1978 by Scientific American, Ino»

© Перевод на русский язык, «Мнр», 1982 Мартин Гарднер «ЕСТЬ ИДЕЯ!»

Старший научный редактор А. Ю, Кирнй Младший научный редактор М. В. Суровова Художник Л. М. Муратова Художественный редактор Л. Е. Безрученков Технический редактор Е. С. Потапенкова Корректор К- Л. Водяннцкая ИБ № 2829.

Сдано в набор 18.06.81. Подписано к печати 04.И.81. Формат 84Х1081/,,.

Бумага типографская № 2. Гарнитура литературная. Печать высокая.

Объем 4,75. Усл. печ. л. 15,96. Усл. кр.-отт. 16,36. Уч.-иад л. 13,34.

Изд. № 12/1630. Тираж 100 000 экз. Зак. 1184. Цеиа 70 к»

ИЗДАТЕЛЬСТВО «МИР» Москва, 1-й Рижский пер., 2.



Ленинградская типография № 2 головное предприятие ордена Трудового Красного Знамени Ленинградского объединения „Техническая книга" им.

Евгении Соколовой Союзполмграфпрома при Государственном комитете СССР по делам издательств, полиграфин и книжной торговли. 198052, г. Ленинград, Л-52, Измавловскнй проспект, 29.

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

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

Кто не слышал о яблоке Ньютона, о паутинке, подсказавшей конструкцию сказочно легкого подвесного моста, об Эйнштейне, лихорадочно делающем выкладки на обратной стороне подвернувшегося под руку старого конверта? Из воспоминаний Пуанкаре мы знаем, что долго не дававшееся ему доказательство важной теоремы из теории автоморфных функций неожиданно было найдено, когда он занес было ногу на ступеньку автобуса. Из воспоминаний П. С. Александрова мы узнаём о том, как П. С. Урысон решил задачу, поставленную перед ним Д. Ф. Егоровым: дать топологическое определение линии л ловерхности. После двух месяцев напряженных размышлений П. С. Урысон «проснулся с готовым, окончательным и всем теперь хорошо известным определением размерности. Произошло это в деревне Бурково, вблизи Болшево, на берегу реки Клязьмы...

В то же утро, во время купания в Клязьме, П. С. Урысон рассказал мне [П. С. Александрову]] свое определение размерности и тут же, во время этото разговора, затянувшегося на несколько часов, набросал план всего построения теории размерности с целым рядом теорем, бывших тогда гипотезами, за которые неизвестно было как взяться и которые затем доказывались одна за другой в течение последующих месяцев».





Проблемам психологии творческого акта в математике посвящена обширная литература, созданная трудами Ж- Адамара и А. Пуанкаре, Д. Гильберта и Дж. фон Неймана, Г. Харди и Д. Пойа, а также многих других математиков, философов и психологов. Теперь она пополнилась книгой Мартина Гарднера «Есть идея!»

Замечательный американский популяризатор, бывший до недавнего времени бессменным редактором раздела «Математические игры» в журнале Scientific American, M. Гарднер во многом определил лицо современной занимательной математики, наполнив ее новым содержанием и максимально приблизив к математике серьезной. Книга «Есть идея!» выдержана в лучших, подлинно «гарднеровских» традициях. Ее отличает тщательный и умелый подбор материала, яркая занимательность формы, доступность и подлинная популярность, насыщенность новыми постановками задач, призванными пробудить творческие силы читателя, стимулировать его к самостоятельной работе, приобщить к радости открытия нового.

М. Гарднер не следует ни одному из своих предшественников. Он не предлагает читателю схемы правдоподобных рассуждений, подкрепленных интереснейшими примерами индуктивных умозаключений из математического творчества Леонарда Эйлера, как Д. Пойа, не делится своими соображениями о природе математики и математических доказательств, как Г. Вейль и Дж. фон Нейман, не углубляется в психологию математического открытия, как Ж. Адамар и А. Пуанкаре. М. Гарднер учит читателя тому, чему, казалось бы, невозможно учить: высокому искусству нешаблонного, или, как предпочитает говорить сам Гарднер, «нелинейного» мышления, учит не рассказом, а показом, давая пищу не только уму, но и сердцу, вовлекая в игру, заставляя решать удивительные по красоте задачи, предлагая увлекательные темы для дальнейших размышлений.

Можно надеяться, что для нашего читателя встреча с новой книгой М. Гарднера станет таким же праздником, какими были встречи с его предыдущими книгами.

Ю. Данилов Предисловие

–  –  –

Психологи-экспериментаторы любят рассказывать историю об одном профессоре, который изучал способность шимпанзе решать задачи. В центре комнаты к потолку достаточно высоко, чтобы обезьяна, подпрыгнув, не могла достать его, был подвешен банан.

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

Обезьяна тихо сидела в углу, наблюдая за тем, как экспериментатор расставляет ящики по комнате.

Она терпеливо ждала, пока профессор не оказался посредине комнаты, и, когда тот проходил под бананом, внезапно вспрыгнула ему на плечи и, оттолкнувшись от него, взмыла в воздух, схватила банан и была такова.

Мораль этой юмористической истории понять нетрудно: задача, которая кажется нам трудной, может Иметь неожиданно простое решение. Обезьяна могла руководствоваться природным инстинктом или накопленным опытом, но главное в том, что она сумела найти прямое решение задачи, которое ускользнуло от вттшгтгя профессора.

Суть математики — непрестанный поиск все более вроетьих «пособ©в доказательства теорем и решения задач. Мережко первое доказательство какой-нибудь теоремы требует Ц'ел-ой статьи объемом в 50 страниц убористого текста, доступного лишь посвященным.

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

Озаренья такег© рода, приводящие к кратким, изящным- рептентпш, привлекали и продолжают привлекать внимание психологов. Наступают они внезапно, как гром ереди ясного неба, Широкой известностью, пользуется история о том, как ирландский математик Уильям Роуэн Гамильтон, возвращаясь как-то вечером домой, изобрел на мосту кватернионы. Он внезапно понял, что в арифметической системе коммутативный закон отнюдь не обязательно 'должен, выполняться. Рассказывают, что эта мысль настолько поразила Гамильтона, что он остановился на мосту как вкопанный и нацарапал основные формулы алгебры кватернионов на каменных перилах, «Высеченные в камне», эти формулы и Польше украшают исторический мост.

Что именно происходит в мозгу творческой личности, когда на нее нисходит озарение? Этого не знает пока никто. Озарение, взлет, интуитивное постижение истины — процесс довольно загадочный, не поддающийся попыткам расчленить его на составные части и воспроизвести при помощи ЭВМ, Современные ЭВМ решают задачи, автоматически шаг за шагом выполняя огромнее количество операций в соответ* ствии с командами, записанными в программе. Лишь невероятные скорости, с которыми ЭВМ выполняют элементарные операции, позволяют современным ЭВМ решать некоторые задачи, остающиеся непосильными для человека, так как решение таких задач потребовало бы от него несколько тысяч лет безостановочных вычислений.

Внезапное озарение, творческий взлет разума, перед которым, как при вспышке молнии, открывается простой и короткий путь к решению задачи, по самой своей природе выделяется на фоне общего темна развития. Как показали последние исследования, личности с особо сильной склонностью к такого рода озарениям обладают средним уровнем развития и никакой корреляции между высоким уровнем развития и способностью интуитивно постигать истину, по-видимому, не существует. Человек может обладать высоким I. Q.*, измеряемым по обычным тестам, и более чем скромными способностями к нестандартному мышлению. С другой стороны, люди, не блещущие в остальном особыми талантами, могут обладать весьма ярко выраженной способностью к озарению. Например, Эйнштейн не отличался особенно глубокими познаниями в математике, и его оценки и в гимназии, и в цюрихском Политехникуме оставляли желать много лучшего. Тем не менее взлеты творческой фантазии, которые привели его к созданию общей теории относительности, были настолько мощными, что полностью революционизировали физику.

В этой книге перед вами предстанет тщательно подобранная система задач, которые кажутся трудными и действительно трудны, если пытаться решать их традиционными методами. Но стоит лишь вам избавиться от оков традиционного мышления и воспарить до высот озарения, как перед вами откроются * О тестах интеллектуальных способностей (I.Q.) см., например, в книге: Айзенк Г. Проверьте свои способности.

— М.:

Мир, 1972.

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

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

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

Способность к нестандартному мышлению отнюдь не обязательно коррелирует с быстротой соображения. Тугодумы могут получать удовольствие от задачи ничуть не меньше тех, кто схватывает все на лету, и при поиске неожиданных решений могут оказаться сильнее «скородумов». Возможно, что удовольствие, получаемое при нестандартном решении задачи, побудит кого-нибудь к более глубокому изучению традиционных методов решения. Эта книга предназначена для любого читателя, наделенного чувством юмора и способностью понимать задачи.

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

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

Восклицание «Эврика!» («Нашел!») заимствовано нами из древней легенды о том, как Архимед, сидя в ванне, открыл способ, позволяющий определить, сколько золота утаили мастера при изготовлении короны царя Сиракуз.,Рассказывают, будто Архимед так обрадовался своему открытию, что выскочил из ванны и, забыв об одежде, бросился бежать по улице, крича: «Эврика! Эврика!»

Собранные в книге задачи разделены на шесть категорий: комбинаторные, геометрические, теоретико-числовые, логические, процедурные и словесные.

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

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

К каждой задаче с замечательными иллюстрациями канадского графика Джима Глена мы я^исовокупили несколько замечаний. В них речь.идет о характере задач и показывается, как во многих случаях рассмотренная нами игровая ситуация связана с важными аспектами современней математики.

В некоторых случаях мы предоставляем читателю возможность испытать свои силы на еще не решенных задачах.

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

1. Нельзя ля свести задачу к более простому случаю?

2. Нельзя ли преобразовать задачу к изоморфной задаче, легче поддающейся решению?

3. Не существует ли для решения задачи какогонибудь простого алгоритма?

4. Нельзя ли для решения задачи применить какую-нибудь теорему из другой области математики?

5. Можно ли проверить правильность полученного решения на наглядных примерах иля контрпримерах?

6. Какие аспекты задачи несущественны для решения и лишь отвлекают ваше виимаяяе?

Не будет преувеличением сказать, что в наше время многие склонны поддаваться все более сильному искушению сводить решение всех математических задач к составлению программ для ЭВМ. Современная быстродействующая ЭВМ, проделав исчерпывающий перебор всех возможных случаев методом проб и ошибок, действительно может решить ату или иную задачу за считанные доли секунды или за несколько секунд, но на составление хорошей программы и ее отладку потребуется несколько часов или дней. Составление программы также не всегда сводится к стандартным операциям и требует своих озарений. Но удачная идея может привести к решению задачи и без обращения к ЭВМ и сделать излишним составление программы, Было бы печально, если бы блага НТР оказали на человечество растлевающее влияние и оно интеллектуально обленилось бы настолько, что утратило бы способность к творческому мышлению. Главная цель предлагаемой вниманию читателя подборки задач и состоит в том, чтобы предоставить ему широкие возможности для оттачивания и развития спо»

собности находить нестандартные решения.

–  –  –

Комбинаторные находки

НЕОЖИДАННЫЕ РЕШЕНИЯ ЗАДАЧ

НА СОСТАВЛЕНИЕ И ПЕРЕЧИСЛЕНИЕ

КОМБИНАЦИЙ Комбинаторный анализ, или комбинаторика, занимается изучением способов составления комбинаций из предметов. Пожертвовав самую малость общностью, комбинаторный анализ можно определить как раздел математики, который занимается изучением способов объединения по заранее заданным правилам элементов в множества и свойств возникающих при таком объединении множеств.

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

В комбинаторном анализе часто требуется найти число всех возможных способов объединения предметов в множества по определенным правилам.

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

В нашем случае объединяемые элементы представляют собой прямолинейные отрезки маршрутов, И проходимые по строкам или столбцам матрицы. Поскольку подсчет маршрутов связан с рассмотрением геометрических фигур, мы вступаем в область комбинаторной геометрии.

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

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

Много задач по теории вероятностей собрано в книге Уитворта «Выбор и случай»*. Слово «выбор» в заголовке книги указывает на ее комбинаторный аспект.

Самая первая задача в нашей книге также имеет непосредственное отношение к теории вероятностей:

ведь, в ней требуется указать комбинацию цветных шариков, которая с полной гарантией (то есть с вероятностью, равной 1) позволила бы удовлетворить определенным требованиям. Читая нашу книгу, нетрудно убедиться в том, что из простых вопросов о перечислении способов объединения предметов по тому или иному признаку возникает поистине безбрежное море вероятностных задач. Перечисление маршрутов, по которым Сьюзен могла бы следовать в школу, тесно связано с треугольником Паскаля и теми применениями, которые он находит при решении элементарных задач теории вероятностей.

Число комбинаций, дающих решение данной комбинаторной задачи, очевидно, может быть равно нулю, единице, любому конечному числу и даже обращаться в бесконечность. Например, нечетное число ни одним способом невозможно представить в виде суммы двух четных чисел. Число 21 представимо в виде произведения двух простых чисел одним и только одним способом. Число 7 представимо в виде суммы из двух целых положительных чисел тремя * Whitworth W. A. Choice and Chance. London, 1901.

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

Найти «доказательство невозможности», то е€ть доказать, что не существует ни одной комбинации с требуемыми свойствами, в комбинаторном анализе зачастую бывает чрезвычайно трудно. Например, лишь недавно удалось, доказать, что для правильной раскраски стран на плоской карте достаточно четырех красок. «Проблема четырех красок» долгое время оставалась знамекитой нерешенной задачей комбинаторной топологии. Решить ее, то есть найти «доказательство невозможности», удалось лишь после тою, как была составлена специальная, необычайно сложная программа, для ЭВМ.

С другой стороны, мневие комбинаторные задачи, для которых найти «доказательство невозможности»

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

Вторая задача о непригодных пилюлях вскрывает комбинаторный характер рассуждений, связанных с использованием различных систем счисления. Как будет показано, и сами числа, и их цифровая запись в позиционной системе счисления зависят от некоторых комбинаторных правил. Более того, любое дедуктивное умозаключение, будь то в математике или в формальной логике, оперирует с комбинацией символов, выстроенных в «строку» по определенным правилам. Эти правила позволяют решить, допустима ли та или иная строка символов в рассматриваемой теории или недопустима. Именно поэтому отец комбинаторики Лейбниц называл искусство строить умозаключения комбинаторным искусством — ars combinatoria.

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

Первый близнец. Мама, купи мне жевательную резнику!

Второй близнец. И мне, и мне!

Я хочу шарик такого же цвета, как у Билли.

Автомат был почти пуст. Предугадать, какого цвета шарнк выпадет, если опустить в щель автомата монету в 1 пенс, невозможно. Сколько одиопеисовых монет придется приготовить миссис Джонс, чтобы из купленных шариков заведомо можно было выбрать 2 шарика одного и того же цвета?

Потратив 6 пенсов, миссис Джонс заведомо могла бы извлечь из автомата 2 красных шарика; 4 пенса ушли бы на «добывание» 4 белых шариков, а 2 пенса— иа 2 красных шарика. Израсходовав 8 пенсов, миссис Джонс заведомо получила бы 2 белых шарика. Следовательно, миссис Джонс необходимо приготовить 8 центов. Правильно?

Нет, не верно! Если бы первые два шарика, выкатившиеся из автомата, были разного цвета, третий шарнк непременно совпал бы по цвету с одним из них. Следовательно, миссис Джонс необходимо приготовить всего лишь 3 пенса.

–  –  –

Сколько центов?

Вторая задача о шариках жевательной резинки лишь незначительно отличается от первой. Идея решения второй задачи по существу та же: первые три шарика могут быть разного цвета (например, один шарик может быть красным, один синим и один белым). Это наименее благоприятный случай, так как к достижению желаемого результата ведет самая длинная последовательность испытаний. Четвертый шарик заведомо совпадает по цвету с одним,из трех первых шариков. Итак, чтобы 2 шарика оказались одного и того же цвета, необходимо купить 4 шарика. Следовательно, миссис Джонс следует приготовить 4 цента.

Обобщение на случай п множеств шариков (каждое множество составляют шарики одного цвета) очевидно: если имеется п множеств шариков, то следует быть готовым к тому, что придется купить п + 1 шариков (чтобы 2 шарика заведомо были одного и того же цвета).

Третья задача потруднее двух предыдущих. У миссис Смит не близнецы, а тройня. В автомате находятся б красных, 4 белых шарика и 1 синий шарик.

Сколько монет достоинством в 1 цент должна приготовить миссис Смит, чтобы среди шариков, выданных автоматом, заведомо были 3 шарика одного цвета?

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

Значит, миссис Смит должна приготовить 6 центов.

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

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

обозначить каждый из 11 шариков «своей» буквой, выписать все возможные варианты выдачи шариков из автомата и установить, в каком случае длина цепочки испытаний до появления трех шаров одного цвета имеет наибольшую длину. Но при таком решении потребовалось бы перебрать 111 = 39 916 800 последовательностей всех возможных исходов испытаний. Если мы условимся не различать шары одного цвета, то и тогда при таком подходе пришлось бы перебрать 2310 последовательностей возможных исходов.

Обобщение задачи на случай, когда требуется определить наименьшее число монет, при котором из выданных автоматом шаров заведомо можно выбрать k шариков одного цвета, приводит к следующему решению. Если имеются шары п цветов (шаров каждого цвета не меньше k), то для получения k шаров одного цвета необходимо выбрать не более n(k— 1 ) + 1 шаров. Читателю доставит удовольствие самостоятельно исследовать, что произойдет в том случае, если шаров одного или нескольких цветов будет меньше k.

Задачи этого типа можно промоделировать не только на автоматах для продажи жевательной резинки, но и многими другими способами. Например, сколько карт необходимо вытащить из колоды в 52 листа, чтобы 7 карт заведомо были одной масти?

Здесь п = 4, k = 7, и наша формула дает ответ?

4 ( 7 - 1)+ 1 = 2 5.

Мы рассмотрели лишь очень простые комбинатор* ные задачи, но и они приводят к интересным и трудным вопросам теории вероятностей. Например, какова вероятность извлечь 7 карт одной масти, если вы вытаскиваете из колоды, не возвращая, п карт, где п — любое число от 7 до 24? (Вероятность извлечь 7 карт одной масти, очевидно, равна 0, если из колоды вытащить менее 7 карт, и равна 1, если вытащить более 24 карт). Как изменятся вероятности, если мы условимся возвращать каждую извлеченную карту и тщательно тасовать колоду перед тем, как вытягивать из нее очередную карту? Более трудный вопрос: каково математическое ожидание (среднее по длинной серии испытаний) числа карт, которые необходимо извлечь (с возвратом или без возврата) из колоды, чтобы k из них заведомо были одной масти?

Турнир по настольному теннису Пять членов клуба лгобвтелей настольнгоо тенниса средней школы.им. Милларда Филмора решили провести между собой турнир по олимпийской системе.

<

–  –  –

п,л На следующий год в спертив»

кый клуб записалось 37 школьников. Тренер снова составил таблицу розыгрыша турнира, постаравшись свести до минимума число участников, которые переходят в следующий круг без игры. Сколько партий было сыграно за весь турнир на этот раз?

Как, вы еще не сосчитали?

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

Сколько участников турнира перейдут в следующий круг без игры?

Если вы пытались решить задачу о турнире по настольному теннису «в лоб», составляя различные варианты таблиц розыгрыша турнира с 37 участниками, то, должно быть, заметили, что независимо от способа составления таблицы число участников, переходящих в следующий круг без игры, всегда равно 4. В общем случае число участников, для которых в очередном круге не хватает партнера, есть функция от числа п всех участников турнира. Кате установить, сколько участников вынуждены будут перейти в следующий круг без игры?

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

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

Десятичное число 27 в двоичной системе имеет вид

11011. Поскольку в его записи 4 единицы, то за весь турнир без игры в следующий круг перейдут 4 игрока. Обоснование этого алгоритма для определения числа участников, которым не хватает партнера, мы предоставляем читателю в качестве интересного упражнения.

Описанный в задаче тип турнира иногда называют «игрой на вылет». Он аналогичен алгоритму, который вычислители, работающие на современных ЭВМ, используют для нахождения наибольшего элемента в множестве из п элементов: наибольший элемент находят, сравнивая попарно элементы множества и отбрасывая при очередном сравнении тот из двух элементов, который не больше другого. Как мы уже знаем, чтобы найти наибольший элемент, достаточно произвести ровно п — 1 попарных сравнений. При автоматической сортировке сравнивать можно не только по 2, но и по 3, 4 и т. д. элемента.

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

Стаканчики профессора Квиббла

–  –  –

Глубокая мысль Хотя предложенное профессором Квибблом шуточное решение основано на неоднозначном толковании слова «переставить» (означающего не только «поменять местат», как полагал Барни, но и «поставить по-другому», чем и воспользовался профессор Квиббл), исходная задача не столь тривиальна, как ложет показаться. Рассмотрим, например, аналогичную задачу для случая, когда из 200 стаканчиков, выстроенных в ряд, в первые 100 налита кинки-кола, а 100 остальных оставлены пустыми. Сколько пар стаканчиков следует поменять местами, чтобы пустые и полные стаканчики чередовались?

Поскольку следить за 200 стаканчиками довольно трудно, разберем сначала ту же задачу при меньших значениях п, где п—число полных (или пустых) стаканчиков, и попытаемся подметить общую закономерность. Стаканчики можно «моделировать» фишками двух цветов, игральными картами, выложенными на столе рубашкой либо вверх, либо вниз, монетами и тому подобными предметами, наделенными каким-нибудь «двузначным» признаком. При п = 1 для решения задачи не требуется переставлять ни одной пары стаканчиков. При п = 2 решение очевидно и сводится к перестановке одной пары стаканчиков. Возможно, вы удивитесь, когда узнаете, что при п = 3 чередование пустых и полных стаканчиков достигается перестановкой одной пары стаканчиков. Еще немного усилий, и вам откроется довольно простая общая закономерность. При четном п для решения задачи требуется поменять местами я/2 пар, а при нечетном п соответственно ( п — 1 ) / 2 пар стаканчиков. Следовательно, если имеется 100 пустых и 100 полных стаканчиков, то задачу можно решить, переставив 50 пар стаканчиков.

При этом вы сдвинете с места 100 стаканчиков.

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

Существует одна классическая головоломка, очень, похожая на только что рассмотренную нами задачу, но несколько более трудную. Начнем с 2п предметов, выстроенных в ряд. Пусть по-прежнему п предметов, составляющих первую половину ряда, будут одного типа, а п предметов, составляющих вторую половину ряда, будут другого типа. (Как и прежде, их можно «моделировать» стаканчиками, фишками, игральными картами и т. п.) Требуется переместить предметы так, чтобы предметы одного типа чередовались с предметами другого типа, но в отличие от предыдущей задачи слову «переместить» придается строго определенное значение. На этот раз слово «переместить» означает, что любые два соседних предмета разрешается, не изменяя их последовательности, изъять из ряда и пристроить к любому свободному концу (после одного или нескольких ходов ряд может распасться на несколько звеньев).

Вот как это делается, например, при п = 3:

XXX000 Z000ZZ Х00 X0X ХОХ0Х0 Как выглядит общее решение? При п = 1 решение тривиально. При п = 2 задача, как нетрудно выяснить, неразрешима. При всех п 2 головоломка допускает решение не менее чем за п ходов.

Найти решение при п = 4 не-так-то просто, и поиск его, несомненно, доставит вам немало удовольствия. Может быть, вам удастся сформулировать алгоритм решения головоломки за п ходов при любом п 3.

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

1. Правила перемещения пар остаются теми же за одним исключением: если пара образована предметами различных типов, то перед тем, как пристроить ее к свободному концу, последовательность предметов в паре следует изменить. Например, перемещая две фишки, первая из которых (левая) красная, а вторая (правая) черная, их необходимо поменять местами, после чего первой станет черная, а второй красная фишка, и лишь после этого пристраивать к свободному концу. При 8 фишках существует решение в 5 ходов. При 10 фишках 5 ходов также оказывается достаточно. Общее решение неизвестно. Может быть, вам удастся найти его.

2. Правила такие же, как в исходной задаче, но фишек одного цвета на 1 меньше, чем другого, то есть фишек одного цвета п, а фишек другого п+ 1. Доказано, что при любом п задачу можно решить за п2 ходов, причем это число минимально.

3. Имеются фишки трех различных цветов. Пары соседних фишек перемещаются по обычному правилу с тем, чтобы фишки каждого цвета оказались выстроенными подряд. При п = 3 (всего 9 фишек) существует решение в 5 ходов. И в этом, и во всех предыдущих вариантах головоломки предполагается, что после последнего перестроения фишки стоят в ряд «сомкнутым строем» (без пробелов). Если ряд может содержать пробелы, то существует необычное решение всего лишь в 4 хода.

Напрашиваются и другие варианты головоломки.

Насколько известно, их никто ранее не предлагал и уж конечно не решал. Например, в каждом из приведенных нами вариантов головоломки за один ход можно перемещать не по две, а по три (и более) соседние фишки.

Что произойдет, если на первом ходу переместить фишку, на втором — 2 фишки, на третьем — 3 фишки и т. д.? Если в ряд выстроены п фишек одного цвета и затем п фишек другого цвета, то всегда ли правильного чередования цветов можно добиться за п ходов?

Дороги, которые мы выбираем

–  –  –

Сьюзен. Хотела бы я знать, сколько различных дорог ведет от моего дома к школе.

Подумаем! Сосчитать их, должно быть, не просто. Впрочем... Есть идея! Сосчитать дороги тасем не трудно! Очень даже престо!

Какая, идея пришла в голову Сьюзен?

Вот как она рассудила.

Сьюзен.

У того перекрестка, возле которого я живу, поставлено на карте число 1:

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

Сьюзен. У этого перекрестка я поставлю число 2, так как к нему от моего дома ведут 2 различные дороги.

Тут Сьюзен стало ясно, что число у каждого перекрестка равно либо ближайшему числу (если оно одно), либо сум- ме двух ближайших чисел.

Сьюзен. Еще четыре перекрестка пометила числами. Скоро закончу.

Не поможете ли вы Сьюзен?

Не подскажете ли ей, сколько различных дорог ведет от ее дома к школе?

Сколько путей?

Три перекрестка на ближайшей вертикали справа следует пометить (сверху вниз) числами 1, 4, 9, а два перекрестка на следующей вертикали — числами 4 и 13. Число 13, стоящее на карте у самого правого нижнего перекрестка, показывает, что Сьюзен может выбрать кратчайшую дорогу в школу 13 различными способами.

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

•,/ / / / 7 / / / Чтобы проверить, насколько глубоко вы усвоили алгоритмы Сьюзен, попробуйте нарисовать сети улиц, имеющие другие конфигурации, и подсчитать число кратчайших путей, ведущих из точки А в точку В.

Четыре задачи этого типа представлены на рис. /.

Решать их можно по-разному, например, воспользоваться комбинаторными формулами, но все методы несколько сложнее алгоритма Сьюзен.

Чему равно число кратчайших путей, по которым ладья может перейти из одного углового поля на шахматной доске в другое, диагонально противоположное? Эта задача легко решается, если каждому полю на шахматной доске приписать по числу так же, как Сьюзен приписывала числа перекресткам на карте города. Ладья ходит только по горизонтали и вертикали. Следовательно, кратчайший путь из любой клетки в любую другую состоит в преодолении разделяющего клетки расстояния по горизонтали и по вертикали. Если числа расставлены верно (см.

рис. 2), то они указывают число кратчайших путей,

–  –  –

Ш 1 53 26 \05 Ж ведущих из нижнего угла в любое поле. Например, поле в правом верхнем углу помечено числом 3432.

Следовательно, ладья может перейти с поля, стоящего в левом нижнем углу доски на диагонально противоположное поле 3432 кратчайшими путями.

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

Треугольник Паскаля позволяет находить биномиальные коэффициенты (то есть коэффициенты при любом члене разложения (а-\-Ь)п, где п — любое целое число) и решения многих задач элементарной теории вероятностей. Заметим, что на рис. 3 число кратчайших путей, ведущих из вершины треугольника в самую левую или самую правую клетку нижнего ряда, равно 1 и что по мере приближения к середине ряда число кратчайших путей возрастает.

Возможно, вам случалось видеть одно из устройств, действие которых основано на свойствах треугольника Паскаля: по наклонной доске, в которую в шахматном порядке вбиты колышки, скатываются шари~ ки и скапливаются в отсеках под колышками нижнего ряда. Распределение шариков имеет форму колоколообразной кривой, а число шариков в каждом отсеке пропорционально соответствующему биноми* альному коэффициенту, потому что число кратчайших путей, ведущих в каждый отсек, в точности совпадает с определенным биномиальным коэффициентом.

Алгоритм, предложенный Сьюзен, как нетрудно понять, остается в силе и для трехмерных сетей, в которых ячейки («кварталы») имеют форму прямоугольных параллелепипедов. Представьте себе куб с длиной ребра 3 единицы, разделенный на 27 единичных кубов. Будем считать его пространственной шахматной доской и в угловую «клетку» поместим ладью, которая может двигаться параллельно любому из ребер куба. Сколькими способами ладью можно перевести кратчайшим путем в клетку, расположенную на другом конце диагонали куба?

Перепутали

–  –  –

«Птичка в клетке»

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

Таким образом, мы имеем дело лишь с одним вариантом: каждый из 4 предметов оказывается в своей клетке.

Во многих книгах по занимательной математике встречается следующая задача, в которой речь идет лишь о 3 предметах. На столе расставлены 3 закрытые коробки. В одной из них находятся 2 монеты по 5 центов, в другой — 2 монеты по 10 центов и в третьей — 1 пятицентовая и 1 десятицентовая монета. На крышках коробок написано: 10 центов;

15 центов и 20 центов, но ни одна из надписей не соответствует содержимому коробки. Предположим, что из коробки с надписью «15 центов» (напомним, что надпись не соответствует содержимому коробки) извлекли 1 монету и положили на стол перед коробкой. Можно ли, взглянув на эту монету, сказать, какие монеты находятся в каждой из 3 коробок?

Как и в предыдущей задаче, многих вводит в заблуждение кажущаяся неоднозначность выбора: они думают, будто существует довольно много вариантов решения, тогда как на самом деле задача допускает единственное решение. Монета, извлеченная из коробки с надписью «15 центов» (не соответствующей содержимому), может быть монетой достоинством либо в 5 центов, либо в 10 центов. Если извлечена монета достоинством в 5 центов, то в коробке первоначально находились 2 монеты по 5 центов. Если извлечена монета достоинством в 10 центов, то в коробке первоначально находились 2 монеты по 10 центов. И в том и в другом случае содержимое остальных двух коробок восстанавливается одно* значно. Нетрудно видеть, что ие соответствующие содержимому каждой коробки надписи оставляют лишь 2 варианта распределения монет по: коробкам.

После того как из коробки с ложной надписью «15 центов» извлечена 1 монета, один вариант исключается, и остается единственный допустимый вариант, соответствующий правильному решению.

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

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

Какова вероятность, что ровно у 1 младенца окажется карточка с его именем? Какова вероятность», что.

по крайней мере у 2 младенцев окажутся карточки с их именами? Какова вероятность, что ровно у 2 младенцев окажутся карточки с их именами?

Какова вероятность, что не более чем у 2 младенцев окажутся карточки с их именами? И так: далее;

Вопрос о «по крайней мере одном» — независимо от того, о чем идет речь,— один из классических вопросов занимательной математики. Довольно часто его облекают в форму задачи об п посетителях ресторана, сдавших шляпы в гардероб. Рассеянный гардеробщик выдал посетителям номера наугад,, нимало не заботясь о том, кому достанется номерок от шляпы — ее владельцу или кому-нибудь другому.

Какова вероятность, что по крайней мере один посетитель получит свою шляпу? Оказывается, что при возрастании п эта вероятность быстро стремится к 1— (1/е), то есть немногим больше Уг. Здесь е—знаменитая иррациональная константа (число Эйлера), равная 2,71828... В задачах теории вероятностей она встречается так же часто, как число л в геометрических задачах.

Стаканы профессора Кеиббла

–  –  –

Счастливая идея, позволяющая сразу же решить головоломку проф. Квиббла, сводится к тому, что одни и те же монеты могут одновременно находиться более чем в одном стакане. На языке теории множеств решение задачи допускает следующее описание: имеется два множества монет, одно из которых содержит 7 элементов, а другое — 3 элемента, причем в последнем множестве выделено подмножество, содержащее 1 элемент.

Наглядно полученное решение можно изобразить в виде следующей диаграммы:

Найти все остальные решения мы предоставляем читателю. Додуматься до 10 решений, одно из которых предложил проф. Квиббл, не составит особого труда, но найти еще 5 решений (всего существует 15 решений задачи) не так-то просто: необходимо «озарение».

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

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

После тогсг как один школьник пропустил целую неделю занятий, его навестил учитель. Школьник принялся объяснять, почему ему некогда ходить в школу.

— Я сплю 8 часов в сутки. Это составляет 8 X* X 365 = 2920 часов в году, или, так как в сут»

ках 24 часа, 2920 : 24 (около 122) суток.

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

60 дней в году приходятся на летние каникулы.

На завтрак, обед и ужин у меня уходит 3 часа в день, то есть 3 X 365 = 1095 часов, или 1095 : 24 (около 45 суток) в год.

По крайней мере 2 часа в день мне необходимы для отдыха, что составляет 2 X 365 = 730 часов, или 730:24 (около 30 суток) в год.

Школьник выписал названные им числа в стол* бец и просуммировал:

На сон 122 Субботы и воскресенья 104 Летние каникулы 60 Завтраки, обеды и ужины 45 Отдых 30

Итого 361 день

— Видите,— продолжал школьник,— у меня остается всего-навсего 4 дня в год на болезни, а о праздниках я и не говорю!

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

Как поджарить ромштексы?

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

Мистер Джонсон. Чтобы поджарить с двух сторон 1 ромштекс, требуется 20 мин (по 10 мин на каждую сторону).

Значит, за 20 мин можно приготовить 2 ромштекса. Еще 20 мин мне понадобится, чтобы поджарить третий ромштекс, поэтому всего на приготовление 3 ромштексов придется затратить 40 мин.

Бетси. Папочка, ромштексы можно поджарить гораздо быстрее! Я только что придумала, как можно сэкономить 10 мин.

Какая удачная мысль позволила Бетси сократить приготовление обеда на 10 мин?

–  –  –

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

Как обычно, рассмотренная нами простая задача допускает не одно обобщение. Например, условия задачи можно варьировать, изменяя число ромштексов, которые можно одновременно поджаривать на плите, число ромштексов, которые требуется поджарить, или то и другое одновременно. Другой подход к обобщению задачи состоит в увеличении числа сторон, с которых требуется «обжарить» тот или иной предмет. Например, кому-нибудь может понадобиться окрасить со всех сторон в красный цвет п кубов, окрашивая за один раз по одной грани k кубов.

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

•приготовления 2 ромштексов, рассмотрим следующий вариант.

Из длинного списка хлопотливых домашних дел мистеру и миссис Джонс осталось выполнить три пункта:

1) произвести уборку на первом этаже (у семейства Джонсов имеется 1 пылесос, на уборку первого этажа уходит 30 мин);

2) подстричь газон перед домом (у семейства Джонсов имеется 1 машинка для стрижки газона, на выполнение этого задания необходимо затратить 30 мин);

3) накормить и уложить спать ребенка (на это также требуется затратить 30 мин).

Как следует распределить обязанности супругам Джонс, чтобы завершить все работы по дому в кратчайший срок? Если предположить, что мистер и миссис Джонс работают одновременно, то трудно удержаться от искушения дать ответ: «На выполнение 3 пунктов программы у супругов Джонс уйдет 60 мин». Но если одну из работ, например уборку первого этажа, разделить на 2 равные части и выполнение второй половины отложить (как в задаче с поджариванием ромштексов) до завершения другой работы, то на выполнение намеченной программы у супругов Джонс уйдет лишь 3 / 4 времени (по «равнению с первым вариантом), или 45 мин.

А вот более хитроумная задача на исследование впёраций: требуется как можно быстрее обжарить с двух сторон 3 ломтика хлеба и каждый из них с одной стороны намазать маслом. В нашем распоряжении имеется тостер устаревшей модели с дверцами на пружинках справа и слева. Тостер вмещает одновременно 2 ломтика хлеба и поджаривает их только с одной стороны. Чтобы поджарить тосты с двух сторон, необходимо открыть дверцы и перевернуть ломтики на другую сторону.

Чтобы положить ломтик хлеба в тостер, требуется затратить 3 с. Еще 3 с уходит на то, чтобы вынуть каждый ломтик из тостера, и 3 с требуется для того, чтобы повернуть ломтик на другую сторону, не вынимая его из тостера. Каждую из этих операций необходимо производить двумя руками. Это означает, что ли одну из них нельзя выполнить одновременно над двумя ломтиками хлеба. Кроме того, пока мы кладем ломтик хлеба в тостер, вынимаем его оттуда или переворачиваем, его нельзя намазать маслом. Ломтик хлеба поджаривается с одной стороны за 30 с. Намазать ломтик хлеба маслом можно за 12 с.

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

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

Но 9 с можно сэкономить, если вам удастся набрести на следующую счастливую идею:

ломтик хлеба можно поджарить с одной стороны не до конца, затем вынуть из тостера и дожарить позже. При таком подходе время на приготовление 3 ломтиков поджаренного хлеба с маслом удается сократить до 114 с. Но даже для тех, кому удается подобрать ключ к решению, составление оптимального графика выполненных операций остается далеко не легкой задачей. Что же касается бесчисленных проблем на составление самых эк&номичных после' довательностей операций в различных областях человеческой деятельности, то они требуют для своего решения сложных математических методов, обращения к ЭВМ и современной теории графов.

Упрямые плитки Площадка перед домом мистера Брауна выложена 40 квадратными плитками. Со временем некоторые плитки треснули, н мистер Браун решил покрыть площадку заново.

Ои отправился в магазин и выбрал новые плитки, которые имели форму прямоугольников, составленных из двух квадратов размером; в старую- плитку.

Владелец магазина. Сколько вам нужно плиток, мистер Браун?

Мистер Браун. Мне нужно покрыть 40 квадратов. Думаю, что 20 плиток будет достаточно.

Но' когда м-р Браун попытался вымостить площадку новыми плитками, то ничего хорошего из этого не получилось.

Как он ии старался, уложить плитки так, чтобы они покрыли всю площадку, это ему не удалось.

Бетси. Что случилось, папа?

Чём ты так озабочен?

М-р Браун. Никак не могу уложить эти проклятые плитки! Как ни бьюсь, два квадрата остаются непокрытыми.

С ума можно сойти!

–  –  –

Проверка на четность Дочь мистера Брауна нашла способ покрыть площадку прямоугольными плитками, воспользовавшись рассуждением, известным под названием «проверка на четность». Мы говорим о двух числах, что их четность одинакова, если они либо оба четны, либо оба нечетны. Если одно число четно, а другое нечетно, то говорят, что их четность различна, С nor добными ситуациями неоднократно приходится сталкиваться в комбинаторной геометрии.

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

Проверка на четность в самых различных вариантах лежит в основе доказательств многих теорем «несуществования» в математике. Кто не помнит, например, знаменитое доказательство иррациональности числа +Ji, предложенное Евклидом. Иррациональность -у/2 Евклид доказывает от противного, то есть сначала предполагает, что число л/2 рациональное и его можно представить в виде несократимой дроби с целым числителем и знаменателем. Числитель и знаменатель этой дроби не могут быть оба четными, так как тогда дробь не была бы несократимой. Следовательно, либо они оба нечетны, либо один из них четен, а другой нечетен. Затем Евклид доказывает, что и в том, и в другом случае дробь, которая была бы равна д/2, не существует. Иначе говоря, числитель и знаменатель дроби, которая была бы равна V2~» не могли бы быть ни одинаковой, ни различной четности. Но все дроби подразделяются на два непересекающихся класса: к одному относятся дроби с числителем и знаменателем одинаковой четности, к другому принадлежат дроби с числителем и знаменателем различной четности. Следовательно, число д/2 непредставимо в виде дроби с целым числителем и знаменателем, то есть иррационально.

Теория покрытия одних плоских фигур другими изобилует задачами, в которых доказать несуществование решения было бы трудно, если бы не проверка на четность. Задача, с которой столкнулся мистер Браун, чрезвычайно проста, поскольку в ней речь идет о покрытии площадки плитками в форме костей домино — простейших нетривиальных полимино.

(Каждая «кость» полимино составлена из квадратов, примыкающих друг к другу по целой стороне).

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

В рассмотренной нами задаче площадку перед домом можно рассматривать как прямоугольник размером 6 X 7 единиц с двумя недостающими клетками одного цвета. Если из прямоугольника вырезать 2 клетки одного цвета, то ясно, что покрыть 20 костями домино 40 остальных клеток невозможно.

С исходной задачей тесно связан следующий ее интересный вариант: всегда ли 20 костями домино можно покрыть прямоугольник размером 6 X 7 единиц, из которого вырезаны 2 клетки разного цвета?

Проверка на четность не позволяет доказать неразрешимость новой задачи, но это отнюдь не означает, будто бренные останки прямоугольника всегда можно покрыть 20 костями домино. От перебора всех фигур, возникающих при удалении из прямоугольника размером 6 X 7 единиц двух клеток разного цвета, следует заранее отказаться, так как их слишком много, что затрудняет анализ задачи. Не существует ли простое доказательство разрешимости задачи, позволяющее разом охватить все прямоугольники размером 6 X 7 с двумя недостающими клетками разного цвета?

Такое доказательство, простое и изящное,.действительно существует. Идею его предложил Ральф Гомори. Оно также использует проверку на четность.

Предположим, что прямоугольник размером,6. X 7 деликом заполнен замкнутой дорожкой шириной в 1 клетку (рис. 4). Если удалить 2 клетки разного цвета, то, где бы они ни были расположены в прямоугольнике, замкнутая дорожка распадется на две части, каждая из которых состоит из четного числа клеток, цвета которых чередуются. Ясно, что каждый

d -

• такой отрезок дорожки можно выложить костями домино. Следовательно, задача всегда допускает решение. Может быть вам захочется испытать свои силы и,применить остроумную идею Гомори к доказательству разрешимости аналогичных задач.для прямоугольников других размеров и форм, из которых вырезано более двух клеток.

Теория «покрытия» — обширный раздел комбинаторной геометрии, интерес к которому все возрастает. Области, которые требуется покрыть, могут быть любой формы, конечными или бесконечными.

Форма фигур, которыми требуется покрыть заданную фигуру, варьируется от задачи к задаче. Иногда требуется покрытие не конгруэнтными фигурами, а фигурами нескольких различных форм..Доказательство несуществования решения таких задач нередко удается получить, раскрасив клетки покрываемой фигуры специальным образом в несколько цветов.

•Трехмерным аналогом домино служит кирпич размером 1 X 2 X 4 единиц. Такими кирпичами нетрудно.заполнить ящик размером 4 X 4 X 4 единиц (заполнение пространственных тел принято называть упаковкой). Можно ли заполнить кирпичами ящик размером 6 X 6 X 6 единиц? Решение-этой задачи аналогично решению задачи о покрытии площадки неред домом мистера Брауна. Представим себе, что ящик разделен на 27 кубиков размером 2 Х2 Х2 единиц. Раскрасим кубикн в шахматном порядке в нерный и белый» цвет («шахматная доска» при этом получится не обычная, а трехмерная). Подсчитав, сколько черных и белых кубиков вмещает ящик, мы обнаружим, что кубиков одного цвета на 8 больше, чем кубиков другого.

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

Теория упаковки кирпичей — лишь небольшой фрагмент теории упаковки в трехмерном пространстве. Проблемам этой теории, среди которых имеется немало нерешенных, посвящена обширная и все возрастающая литература. Многие из задач относятся к рациональному выбору стандартной упаковки промышленных товаров, хранению товаров на складе и т. д.

Четность играет важную роль и в физике элементарных частиц. В 1957 г. два американских физика китайского происхождения, Ли Цзундао и Янг Чжэньнин, получили Нобелевскую премию за теоретическое предсказание несохранения четности. Их знаменитая работа носит слишком специальный характер, чтобы мы могли разобрать ее здесь, но сохранение четности можно продемонстрировать на примере одного замечательного фокуса с монетами.

Наберите пригоршню монет и, бросив ее на стол, сосчитайте, сколько монет выпало вверх гербом.

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

Если сначала она была нечетной, то она останется нечетной, а если была четной, то останется четной.

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

Фокус можно показывать и по-другому. Пусть ваш помощник закроет рукой не одну, а две монеты. Вы сможете безошибочно сказать, лежат ли они обе вверх гербом или «решкой», или же одна монета лежит гербом вверх, а другая — гербом вниз. Аналогичные проверки на четность лежат в основе многих хитроумных карточных фокусов.

Проф. Квиббл и его домашние животные

–  –  –

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

Пусть х — число собак, у — число кошек, г — число попугаев, а п — общее число животных.

Тогда условия задачи позволяют записать следующую систему из 4 уравнений:

Решить ее можно многими стандартными способами. Из первых трех уравнений видно, что х = у = = г. Так как п = х + 2 и п = Зх (из последнего уравнения), то х-\-2 = 3*, откуда х = 1, и мы получаем полный ответ задачи: x = y = z— 1.

Поскольку х, у и z в таких задачах принимают, как правило, целые положительные значения (кто станет.держать у себя треть кошки или четверть попугая?), то задачу о домашних животных проф. Квиббла можно отнести к так называемым диофантовым задачам. Так принято называть задачи, сводящиеся к решению алгебраических уравнений в целых числах. Иногда диофантовы уравнения не имеют решений или допускают только одно решение. Существуют также диофантовы уравнения, имеющие более одного решения и даже бесконечно много решений.

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

Корова стоит 10 долларов, свинья — 3 доллара, а овца — 50 центов. Фермер купил по крайней мере 1 корову, 1 свинью и 1 овцу, израсходовав на покупку всего 100 долларов. Сколько и каких животных он купил?

Пусть х — число коров, у — число свиней и г — число овец.

Тогда условия задачи можно записать в виде двух уравнений:

–  –  –

Какие целочисленные значения могут принимать х п у? Один из способов получить ответ на этот вопрос состоит в том, чтобы преобразовать уравнение, оставив в левой части только член с наименьшим коэффициентом при неизвестном: Ьу = 100—19*.

Разделив обе части уравнения на 5, получим у = = (100—19*)/5.

Разделим теперь 100 и 19* на 5, выделив заведомо целую часть и дробный остаток (если он существует):

у = 20 — Зх — 4х/5.

Ясно, что выражение 4*/5 должно принимать целочисленные значения. Следовательно, х должен быть кратен 5. Наименьшее кратное 5 равно 5, что соответствует j = l и (если вернуться к любому из двух исходных уравнений) г = 94. При остальных значениях х, кратных 5 (и больших 5), у принимает отрицательные значения. Значит, наша задача допускает единственное решение: фермер купил 5 коров, 1 свинью и 94 овцы.

Варьируя цены на коров, свиней и овец, можно самостоятельно открыть многие премудрости элементарной теории диофантовых уравнений. Предположим, например, что коровы продаются по 4 доллара, свиньи — по 2 доллара и овцы — по 7з доллара за голову. Сколько животных купил фермер на 100 долларов, если известно, что он купил по крайней мере 1 корову, 1 свинью и 1 овцу? Эта задача допускает 3 решения. А что можно сказать, если корова стоит 5 долларов, свинья — 2 доллара и овца — 50 центов?

Оказывается, что в этом случае решения не существует.

Теория диофантовых уравнений представляет собой обширный раздел теории чисел, имеющий бесчисленные применения во многих областях науки и техники. Одна из знаменитых задач на решение диофантовых уравнений известна под названием великой (или последней) теоремы Ферма. В ней требуется найти при любух целых положительных п 2 решение в целых числах уравнения je"+«/rt —.zn (при п = 2 эти решения называются пифагоровыми тройками; существует бесконечно много пифагоровых троек, начиная с 3 2 + 4 2 = 5 2 ). Великая теорема Ферма — наиболее известная из нерешенных проблем теории чисел. До сих пор никому еще не удалось ни найти хотя бы одно решение уравнения хп -\- уп = = 2" в целых числах (при п 2), ни доказать, что такого решения не существует.

Небольшой переполох в аптеке

–  –  –

...положить 55 отобранных пилюль на одну чашу весов и взвесить их. Предположим, что пилюли весили бы 5510 мг, или на 10 мг больше, чем следует. Тогда мисс Блек заключила бы, что среди отобранных пилюль имеется 1 пилюля с повышенной дозой лекарства, а ровно 1 пилюля была извлечена из первого флакона.

Если бы вес 55 пилюль оказался на 20 мг больше нормы, то это означало бы, что среди отобранных пилюль имеются 2 пилюли с повышенной дозой лекарства. Их можно было извлечь только из второго флакона. Так мисс Блек сумела понизить число взвешиваний до 1. Меньше не бывает!

Большой переполох в аптеке

–  –  –

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

Чтобы решить вторую задачу, необходимо воспользоваться последовательностью, которая бы сопоставляла каждому флакону отличный от других номер и обладала бы еще одним дополнительным свойством: сумма членов любой ее подпоследовательности должна быть отличной от суммы членов любой другой ее подпоследовательности. Существуют ли такие последовательности? Да, существуют. Примером может служить хотя бы геометрическая прогрессия со знаменателем 2 и первым членом 1:1, 2, 4, 8, 16 Все члены этой последовательности — степени числа 2, причем показатель возрастает от 0 с единичным шагом. Именно эта последовательность лежит в основе двоичной системы счисления.

Решение задачи состоит в том, чтобы, выстроив флаконы в ряд, взять 1 пилюлю из первого флакона, 2 пнлюли из второго флакона, 4 пилюли из третьего флакона и т. д., затем собрать все отобранные пилюли и взвесить. Предположим, что пилюли оказались на 270 мг тяжелее, чем нужно. Так как каждая пилюля с повышенной дозой лекарства тяжелее нормальной на 10 мг, то, разделив 270 на 10, мы получим 27 — число более тяжелых пилюль.

Запишем число 27 в двоичной системе: ПОИ.

Двоичные разряды, в которых стоят единицы, говорят нам, какие степени числа 2 в сумме дают двоичное число 11011 (или десятичное число 27): 1, 2, 8 и 16. Единицы стоят в первом, втором, четвертом и пятом двоичных разрядах. Следовательно, непригодные пилюли с повышенным содержанием лекарства находятся в первом, втором, четвертом и пятом флаконах.

Двоичная система счисления находит столь шире-»

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

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

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

Секрет фокуса прост. Вы заранее кладете в карман туз, двойку, четверку и восьмерку. Определить на глаз недостачу четырех карт в колоде невозможно, и ваши зрители будут пребывать в уверенности, что вы попросили перетасовать полную колоду.

Перетасованную колоду вы подкладываете под четыре карты, уже лежащие в кармане. После того как число названо, вы мысленно представляете его в виде суммы степеней числа 2 (например, если названо число 10, то вы мысленно разлагаете его в сумму 8 + 2 = 1 0 ) и, сунув руку в карман, достаете двойку и восьмерку.

На том же двоичном принципе построены и карточки «для чтения мыслей на расстоянии». На рис. / из гл. 3 показаны 6 карт, позволяющие безошибочно отгадывать любое задуманное число от 1 до 63. Попросите кого-нибудь, задумав любое число в этом диапазоне (например, свой возраст), отобрать и вручить вам все карточки, на которых оно встречается, и вы немедленно назовете задуманное число.

Секрет этого фокуса также прост: вы просто суммируете степени числа 2, стоящие в левом верхнем углу каждой таблицы. Например, если были отобраны и вручены вам таблицы С и F, то вы суммируете числа 4 и 32 и узнаете, что было задумано число 36.

По какому принципу выбраны числа на каждой карточке? Каждое число, имеющее в двоичной записи единицу в первом разряде справа, заносится в таблицу А. Следовательно, в эту таблицу вписаны все нечетные числа от 1 до 63. В карточку В заносятся все числа, имеющие в двоичной записи единицу во втором разряде справа, в карточку С — все числа, имеющие единицу в третьем разряде справа и т. д.

Заметим, что число 63 в двоичной системе записывается как 111111, то есть имеет единицы во всех шести разрядах, и поэтому встречается на всех шести карточках.

Иногда фокусники придают этому фокусу налет таинственности, окрашивая карточки в различные цвета и запоминая, какой цвет соответствует той или иной степени числа 2. Пусть, например, красная карточка означает 1, оранжевая — 2, желтая — 4, зеленая — 8, голубая — 16 и фиолетовая — 32 (мы выбрали 6 цветов радуги по порядку, пропустив синий). Фокусник становится в дальнем конце комнаты и просит кого-нибудь из зрителей отложить в сторону карточки, на которых встречается задуманное число. По цвету отложенных карточек фокусник без промедления может назвать задуманное число.

Распиленный браслет

–  –  –

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

Сколько звеньев вы бы приказали распилить на месте Глории?

Достаточно распилить лишь одно-едииствеиное звено: третье с любого конца цепи. Браслет распадется на 3 части длиной в 1 звеио, 2 звена и 4 звеиа. Отдавая их в необходимой комбинации портье и получая предыдущие, Глория сможет оставлять у портье каждый день на 1 звеио больше, чем накануне.

Решающее звено Чтобы решить эту задачу, необходимо принять во внимание два соображения. Во-нервых, понять, что наименьший набор отрезков золотой цепочки, позволяющий оставить у портье любое число звеньев от 1 до 7, состоит из 3 отрезков длиной в 1, 2 и 4 звена.

&ак МЫ уже знаем из решения предыдущей задачи, эти числа — не что иное, как последовательные степени числа 2, положенные в основу двоичной системы счисления.

Во-вторых, необходимо понять, что разделить браслет на части длиной в 1, 2 и 4 звена можно распилив одно-единственное звено.

Задача допускает обобщение на случай, когда браслет или цепочка состоят более чем из 7 звеньев.

Например, пусть у Глории имеется с собой золотая цепочка из 67 звеньев, которую необходимо распилить с той же целью, что и злосчастный браслет,— для уплаты за проживание в гостиничном номере от 1 до 67 суток по 1 звену за сутки. Оказывается, что в этом случае достаточно распилить лишь 3 звена.

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

Интересный вариант этой задачи возникает в том случае, если первоначально концы n-звенной цепочки соединены так, что цепочка превратилась в замкнутую петлю. Например, предположим, что у Глории есть золотая цепочка из 79 звеньев. Сколько звеньев необходимо распилить, чтобы Глория могла оплатить от 1 до 79 суток пребывания в гостинице из расчета по 1 звену за сутки?

Глава

Геометрические находки

НЕОЖИДАННЫЕ РЕШЕНИЯ ЗАДАЧ

О ГЕОМЕТРИЧЕСКИХ ТЕЛАХ И ФИГУРАХ

Геометрия занимается изучением свойств тел и фигур, хотя такое определение настолько широко, что почти лишено смысла. Так, оно позволяет считать геометром члена жюри любого конкурса красоты, поскольку тот судит о «свойствах тел и фигур», хотя под телами и фигурами он понимает нечто иное, чем геометр. Когда о какой-нибудь линии ктолибо замечает, что она необычайно изящна или выразительна, то, хоть речь идет о кривой, то есть объекте, действительно изучаемом в геометрии, само высказывание относится скорее к области эстетики, чем к математике.

Попробуем уточнить, что такое геометрия, и определим ее с помощью такого понятия, как симметрия.

Под симметрией принято понимать такое преобразование фигуры, которое оставляет фигуру неизменной.

Например, буква Н симметрична относительно поворота на 180°. Это означает, что если букву Н повернуть на 180° (поставить «вверх ногами»), то она перейдет в фигуру, неотличимую от буквы Н в исходном положении (разумеется, при условии, если перекладина в букве Н находится строго посредине).

Слово «AHA», стоящее на обложке этой книги, обладает зеркальной, или двусторонней симметрией: если приставить к нему справа или слева зеркало, то зеркальное отражение слова будет неотличимо от оригинала.

Любой раздел геометрии можно определить как науку о свойствах фигур, не изменяющихся при определенных преобразованиях симметрии. Например, евклидова геометрия на плоскости занимается изучением свойств, остающихся неизменными (ин^ вариантных) при движении фигуры по плоскости, поворотах, зеркальных отражениях и равномерных сжатиях и растяжениях. Аффинная геометрия занимает* ся изучением свойств, инвариантных относительно «перекашивания» фигуры. Проективная геометрия изучает свойства, инвариантные относительно проецирования. Топология имеет дело со свойствами, которые сохраняются неизменными, когда фигура претерпевает сколь угодно сильные искажения без разрывов и склеиваний, аналогичные деформациям фигуры, изготовленной из гибкого, растяжимого и прочного материала.

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

«Пасутся кони на другом поле», как ни странно,—« топологическая задача. Метод нитей и пуговиц позволяет свести ее к задаче о точках на простой замкнутой кривой. Форма замкнутой кривой для решения задачи не имеет ни малейшего значения —• • важны лишь топологические свойства кривой. Мы приводим решение задачи для случая, когда точки расположены на окружности, но с тем же успехом мы могли взять кривую, образующую периметр квадрата или треугольника.

Следующие две задачи («Невиданный меч» и «Пари на полюсе») снова выводят нас из плоскости в евклидову геометрию трехмерного пространства.

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

Задача о ковровом покрытии для кольцевого коридора и ее трехмерный аналог — задача о просверленной насквозь сфере — могут служить прекрасными примерами того, как некая величина, которая, казалось бы, должна изменяться в зависимости от значений других параметров, в действительности принимает лишь одно значение. Кто мог бы ожидать, что при просверливании в сфере сквозного цилиндрического канала заданной длины объем оставшейся части сферы при постоянной длине канала не зависит ни от радиуса сферы, ни от диаметра канала?

Впервые столкнувшись с теоремой о таком удивительном постоянстве, математик выразит свое изумление и почти заведомо скажет: «Красивый результат!»

Что именно имеют в виду математики, называя теорему или формулу красивой, точно не известно.

Красота в их понимании каким-то образом связана с неожиданной простотой, но сколь ни трудно объяснить, в чем состоит эстетическая привлекательность математического утверждения, все математики умеют отличать красивую теорему или изящное доказательство с такой же легкостью, с какой мы отличаем красавицу от дурнушки. Геометрия, изучающая объекты, доступные не только мысленному взору, но н непосредственному созерцанию, необычайно богата красивыми теоремами и доказательствами. Некоторые из них вы встретите в этой главе, Как разделить головку сыра

–  –  –

Три разреза?

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

–  –  –

показано, как тремя разрезами разделить сыр на 8 одинаковых порций. В этом решении предполагается, что все три разреза проведены одновременно.

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

После третьего разреза головка сыра окажется разделенной на 8 одинаковых порций.

Решение Рози столь просто, что кажется почти травиальным, и тем не менее оно может служить хорешим введением в серию важных задач на разрезание, теОрйя которых связана с исчислением конечных разностей, а многие доказательства проводятся методом Математической индукции. Конечные разности служат мощным средством получения формул общих членов числовых последовательностей.

Интерес к числовом последовательностям неуклонно возрастает, что объясняется по крайней мере двумя причинами:

во-первых, тем, что числовые последовательности встречаются во многих числовых задачах, и, во-вторых, быстротой, с которой ЭВМ позволяют производить ц а д числовыми последовательностями любые действия.

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

Выяснцм, какие числовые последовательности может порождать разрезание верхней поверхности сыра npHMbiHjHj пересекающимися в центре (ясно, что п одноврем е н н о проведенных разрезов позволяют разделить cbjp н е более чем на 2п кусков).

Мо% н о Л и считать, что In — максимальное число частей, на которые п прямых, проходящих через одну точку, ^огут разделить любую плоскую фигуру, ограниченную простой замкнутой кривой? Нет: нетрудно построить невыпуклую фигуру (например, такую, как на рис, 2), которую одной прямой можно разделить на з н а ч и т е л ь н о большее число частей. А можно ли построить фигуру, которую одной прямой можно было бы разделить на любое конечное число конгруэнтных частей? Если да, то какими свойствами должен обладать периметр фигуры, чтобы одной прямой от нее можно было отсечь п конгруэнтных частей?

Задача о разрезании пирога или сыра становится еще более интересной, когда линии разреза не пересекаются в одной точке. Нетрудно видеть, что начиная с и = 3 при таком способе разрезания исходный круг будет распадаться более чем на 2п частей (пока нас не интересует, будут ли эти части конгруэнтными или равновеликими). На рис. 3 показано, каким образом достигается максимальное число частей при числе разрезов п, равном 1, 2, 3 и 4 (круг делится соответственно на 2, 4, 7 и 11 частей).

Числа 2, 4, 7 и 11 образуют отрезок известной последовательности с общим членом, задаваемым формулой,, п(п-\) 2 г1.

где п — число разрезов. Полагая п = 0, 1, 2,,..,9, получаем первые десять членов последовательности:

1, 2, 4, 7, 11, 16, 22, 29, 37, 46,.... Первые разности равны 1, 2, 3, 4, 5, 6, 7, 8, 9,..., вторые разности равны 1, 1, 1, 1, 1, 1, 1, 1 Постоянство вторых разностей основательно подкрепляет нашу догадку о тем, что общий член этой последовательности квадратичен по п.

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

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

Определить максимальное число частей, на которые можно разделить:

1) подковообразный пирог п прямыми;

2) головку сыра в форме шара или цилиндра п плоскими разрезами;

3) пирог п круговыми разрезами, проводимыми специальным ножом;

4) пирог, испеченный в форме кольца (с круглым отверстием посредине) п прямыми;

5) бублик (тор) п плоскими разрезами.

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

Невидимые размеры В центре городского парка находится, круглая площадка для игр. Магистрат вознамерился устроить на этой площадке бассейн в форме ромба.

Мэр города Дорис Райт, рассмотрев представленные архитектором проекты, высказала свое мнение.

Мэр Райт. Мне нравится вот этот проект бассейна, облицованного красным кафелем. Какова длина каждой стороны ромба?

Вопрос мэра поставил в тупик архитектора Фрэнка Лойда Ронга.

Мистер Ронг. Сейчас прикину.

Расстояние от А до В равно 5 м, а расстояние от В до С — 4 м. По этим данным можно найти длину стороны BD, например вычислить ее по теореме Пифагора.

ГТ Мистер Ронг приступил было к вычислениям, как вдруг достопочтенную. миссис Райт осенило.

Мэр Райт. Есть идея! Длина стороны бассейна — ровно 9 м, Тут и считать нечего.

–  –  –

Диагональ и радиус Миссис Райт заметила, что каждая сторона бассейна совпадает с диагональю некоего прямоугольника, другая диагональ которого равна радиусу круглой площадки для игр. Диагонали прямоугольника равны. Следовательно, длина стороны бассейна равна радиусу круглой площадки для игр. А поскольку этот радиус составляет 5 + 4 = 9 м, т о й длина каждой стороны бассейна равна 9 м. Теорема Пифагора не понадобилась.

Вы сможете лучше оценить все остроумие догадки миссис Райт, если Попытаетесь вычислить длину стороны бассейна более традиционным способом.

Если вы захотите воспользоваться только теоремой Пифагора и подобием треугольников, то решение получится чрезмерно громоздким. Известная из планиметрии теорема о пересекающихся хордах, гласящая, что произведение длин отрезков, на которые точка пересечения делит хорды, одинаково для всех хорд, пересекающихся в данной точке, позволяет несколько сократить решение. Применяя эту теорему, вы вычислите высоту прямоугольного треугольника (составляющего четверть бассейна), равную ^56. Затем по теореме Пифагора, зная два катета, вы найдете гипотенузу, равную 9 м.

С задачей о бассейне, так изящно решенной миссис Райт, тесно связана знаменитая задача о водяной лилии, встречающаяся в одном из произведений Лонгфелло. Когда стебель лилии стоит вертикально, цветок ее на 10 см возвышается над поверхностью озера. Если лилию оттянуть в сторону, не давая стеблю провиснуть, то цветок ее коснется воды в точке, отстоящей на 21 см от того места, в котором выходил из воды прямостоящий стебель. Какова глубина озера в том месте, где растет лилия?

Задачу Лонгфелло нетрудно решить, если начертить схему, изображенную на рис. 4. По существу эта схема ничем не отличается от проекта бассейна, представленного архитектором Ронгом. Требуется определить длину отрезка х. Как и задачу о длине стороны бассейна, задачу о лилии можно решить разными способами. Но если воспользоваться теоремой о пересекающихся хордах, то ответ получается особенно легко и быстро.

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

Задача о дельфине решается легко и просто, если воспользоваться теоремой о том, что любой вписанный угол, опирающийся на диаметр окружности,— прямой, и заметить, что угол ABC именно такой угол.

Катеты прямоугольного треугольника ABC равны 5 м и 12 м. Следовательно, гипотенуза равна 13 м. Мораль всех этих задач ясна: во многих случаях геометрическую задачу можно решить до смешного просто, если вовремя вспомнить соответствующую теорему евклидовой геометрии.

Пасутся кони на другом поле На заседании шахматного клуба мистер Бишоп предложил следующую задачу.

Мистер Бишоп. Как поменять позиции черных и белых коней за наименьшее число ходов?

Один из членов клуба сделал 2 первых хода так, как показано на диаграмме. Переставить белых коней в верхние углы доски, а черных — в нижние он сумел за 24 хода.

Другому члену клуба удалось решить задачу мистера Бишопа за 20 ходов.

–  –  –

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

–  –  –

Мисс Фиш. Каждый ход на доске соответствует вполне определенному ходу на окружности. Чтобы поменять позиции коией, их необходимо переместить по окружности, двигая в одном направлении.

Мистер Бишоп. Вы совершенно правы, Фаннн. Чтобы перейти иа новую позицию, каждый из 4 коией должен совершить по 4 хода. Таким образом, задачу можно решить за 16 ходов, а более экономного решения не существует.

Фанни заменила одного из белых коней красным и задала членам шахматного клуба новую задачку: как поменять местами белого и красного коня за наименьшее число ходов?

Как, по-вашему, почему Фаиии улыбалась, предлагая эту задачку?

Шахматные кони и звездчатые фигуры Фанни решила шахматную задачу, сведя ее к изоморфной задаче, допускавшей простое (хотя и далеко не тривиальное!) решение. Поставленную Фанни задачу можно решить тем же методом. Соединив нитями клетки, занятые конями, и развернув получившееся «ожерелье» в окружность, мы увидим, что кони нанизаны на нити в следующем порядке: черный, черный, красный, белый. Фанни улыбалась, так как понимала, что переставить красного и белого коней невозможно: они следуют друг за другом в неизменном порядке, потому что ни один конь не может перепрыгнуть через другого коня, если они оба движутся по кругу (в любом направлении) и обгон запрещен. Понятно ли вам почему?

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

Получить доказательство «несуществования» другим способом было бы чрезвычайно трудно. Попробуйте, и вы убедитесь в этом сами. • Вам понравилась задача о перестановке шахматных коней? Вот еще одна такая задача, по трудности даже превосходящая обе предыдущие. Рассмотрим позицию на шахматной доске 3 X 4, изображенную на рис. 5. Как и прежде, трех черных и трех белых коней требуется поменять местами так, чтобы белые * *

–  –  –

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

В этом случае, как видно на рис. 6, изоморфный граф более сложен. Этот граф представляет собой диаграмму, на которой показаны все возможные ходы коней, Предположив, что вершины нашего графа — пуговицы или бусины, а ребра — нити, мы обнаружим, что развернуть его в окружность, как в предыдущей задаче, невозможно, но наш граф из нитей и пуговиц нам удастся уложить так, как показано на рис. 7. Числа на этом рисунке соответствуют номерам клеток на рис. 4 и 5.

И 7 Ясно, что задача о перестановке шахматных коней на этом графе изоморфна исходной задаче, но решается несравненно легче. Удастся ли вам найти минимальное решение в 18 ходов?

Метод нитей и пуговиц позволяет проанализировать одну старинную игру. Для нее нам понадобится особая «доска» — звездчатый граф, изображенный на рис. 8, и семь монет или небольших фишек.

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

Затем вы кладете вторую монету на любую незанятую вершину графа и передвигаете ее вдоль ребер в любую другую незанятую вершину. Так вы продолжаете действовать до тех пор, пока все семь монет не займут свое место на вершинах графа.

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

Звездчатый граф можно полностью «раскрыть»

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

Предложите сыграть в эту игру своим друзьям.

Лишь очень немногие из них смогут расставить все семь монет, даже если вы один раз быстро продемонстрируете им, как следует играть, Невиданный меч

–  –  –

Винтовая линия играет важную роль в современ^ ной науке,-особенно в биологии и физике элементарных частиц. Молекулы ДНК имеют форму винтовой линии. В отличие от своих одно- и двумерных двоюродных сестер — прямых и окружностей — винтовая линия обладает «закрученностью», то есть может быть правой и левой. Прямая и окружность неотличимы от своих зеркальных отражений, но отличить винтовую линию от ее зеркального отражения не составляет ни малейшего труда. В зеркале винтовая линия, по выражению Алисы из Зазеркалья (Льюис Кэрролл), «идет наоборот».

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

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

Правильная винтовая линия — это кривая, навитая на круговой цилиндр под постоянным углом к * Гарднер М. Этот правый, левый мир. — М.: Мир," 1967.

образующим (напомним, что образующими называются прямые на поверхности цилиндра, параллельные его оси). Пусть ф — угол, под которым винтовая линия пересекает образующие цилиндра. При 0 = 0° винтовая линия, как нетрудно видеть, вырождается в прямую, а при Ф = 90° — в окружность.

Аналитически в этом можно удостовериться, если записать параметрические уравнения винтовой линии и проварьировать входящий в них угол • от ИГ & до 90°. И прямая, и окружность — предельные формы более общей пространственной кривой, получившей название винтовой линии. Правильная винтовая линия — единственная пространственная кривая постоянной кривизны. Этим и объясняется, почему мечи, вкладывающиеся в ножны, можно изготовить только в форме правильной винтовой линии (что выглядело бы несколько необычно) и двух ее предельных случаев — прямой и-окружности.

Проекция винтовой линии на плоскость, перпендикулярную ее оси, имеет форму окружности. Спроецировав винтовую линию на плоскость, параллельную оси, мы получим синусоиду. В этом нетрудно убедиться, если снова воспользоваться параметрическими уравнениями кривой. Многие свойства синусоиды можно изучать по ее близкой родственнице — винтовой линии.

В этой связи мы хотим рассказать одну забавную историю-задачу, допускающую (при надлежащем подходе) очень простое решение. Внутри цилиндрической башни высотой 100 м ходит лифт. Снаружи башни имеется винтовая лестница, образующая с вертикалью постоянный угол • = 60°. Диаметр башни 13 м.

& Однажды мистер и миссис Пицца поднялись на лифте на смотровую площадку, расположенную на вершине башни. Их сын Томато Пицца предпочел идти наверх пешком. Когда он добрался до смотровой площадки, вид у него был не блестящий.

— Не мудрено, что ты устал, сынок,— заметил мистер Пицца.— Ведь тебе пришлось проделать вчетверо больший путь, чем нам, и все пешком.

— Ты ошибаешься, папа,— ответил Том.— Я прошел лишь вдвое больший путь, чем вы проехали.

Кто прав; Том или его отец?

Кое-кто склонен думать, будто для того, чтобы вычислить длину винтовой лестницы, необходимо знать диаметр башни. В действительности информация о диаметре башни совершенно лишняя!

Дело в том, что винтовую лестницу можно развер* Hyib в гипотенуау прямоугольного треугольника с острым углом 30° и высотой 100 м, а гипотенуза такого треугольника вдвое больше высоты (катета, лежащего против угла 30°), Следовательно, прав был Том.

Убедиться в этом вы можете, развернув какуюнибудь картонную трубку. Возможно, исход эксперимента несколько удивит вас: вы увидите, что длина шва (винтовой линии, как бы навитой на трубку) не зависит от диаметра цилиндра, в который скручен прямоугольный треугольник.

Пари на полюсе

–  –  –

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

Дик. Ясно, что в этом случае конечная точка маршрута не может совпадать с исходной.

Если же самолет вылетает из точки, расположенной на экваторе, то конечная точка маршрута оказывается примерно в 100 км от исходной точки.

Дик. Если же самолет вылетает из точки, расположенной в южном полушарии, то конечная точка будет отстоять от исходной более чем на 100 км.

–  –  –

Бедный Дик снова проиграл.

Какую важную идею он упустил из виду?

Откуда вылетать?

Заключая второе пари, Дик упустил из виду весьма важное обстоятельство: точка, откуда вылетает самолет, может быть выбрана так близко от Южного полюса, что, пролетев 100 км на восток, он опишет вокруг полюса не один оборот, как в предыдущем решении, а два полных оборота. Так возникает новая параллель, все точки которой служат решениями исходной задачи. Аналогичным образом самолет может вылететь из любой точки еще меньшей окружности и, держа курс на восток, совершить три, четыре и т. д. оборота вокруг полюса. При любом целом положительном п можно указать соответствующую параллель, вылетев из любой точки которой и держа курс на восток, самолет совершит п оборотов вокруг полюса. Следовательно, точки, из которых может вылететь самолет, заполняют бесконечно много параллелей, стягивающихся к полюсу, А вот еще одна навигационная задача, связанная с замечательной кривой на сфере — локсодромой, или линией постоянного курса. Самолет вылетает из точки, расположенной на экваторе, и берет курс на северо-восток. Где закончится его полет, если запасы горючего можно считать неограниченными? Какова длина маршрута и как он выглядит?

Возможно, вы удивитесь, когда узнаете, что маршрут полета имеет вид спирали, пересекающей все меридианы под одним и тем же углом и заканчивающейся на Северном полюсе. Такую кривую правильнее было бы рассматривать как винтовую линию, навитую на сферу, стягивающуюся к Северному полюсу и успевающую описать вокруг полюса бесконечно много витков. Если самолет условно принять за точку, то маршрут, хотя и успевает совершить бесконечно много оборотов вокруг полюса, имеет ко^ нечную длину, которая поддается вычислению. Следовательно, поддерживая в полете постоянную скорость, самолет достигнет Северный полюс за конечноэ время.

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

А что произойдет, если самолет, взлетев с Северного полюса, возьмет курс на юго-запад? Эта задача обратна предыдущей. Полет, как и прежде, будет происходить по локсодроме, но сказать, где приземлится самолет в конце пути, мы не можем. В этом можно легко убедиться, обратив время: из какой бы точки, расположенной на экваторе, ни вылетел самолет, он, двигаясь вспять, неизменно окажется на Северном полюсе. Если же самолет, достигнув экватора, пересечет его и будет лететь тем же курсом, то локсодрома стянется к Южному полюсу.

При проецировании на плоскость, касательную к полюсу (и параллельную плоскости экватора), локсодрома переходит в равноугольную, или логарифмиче^ скую, спираль. Эта спираль пересекает радиус-вектор под постоянным углом.

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

Том Пицца, тренер и художественный руководитель черепашек, выдрессировал своих питомцев так, что Абнер (Л) всегда полз к Берте, Берта (В) — к Чарлзу, Чарлз (С) — к Далиле (D) и Д а л и л а — к Абнеру. Однажды он расставил черепашек по углам квадратной комнаты так, что они образовали вершины квадрата ABCD, включил секундомер и принялся наблюдать за тем, что произойдет.

— Интересно получается, сынок,— сказал мистер Пицца. — Каждая черепашка ползет прямиком к своему соседу справа. Все черепашки движутся с одинаковой скоростью и поэтому в любой момент времени находятся в вершинах некоторого квадрата (рис. 9).

— И квадрат этот все время поворачивается и уменьшается,— добавил Том.— Смотри! Видишь?

Черепашки сошлись в центре!

Предположим, что каждая черепашка ползет с постоянной скоростью 1 см/с и что комната, где они находятся, имеет форму квадрата со стороной 3 м.

Через сколько времени черепашки встретятся в центре комнаты? (Каждую черепашку мы условно "принимаем за точку.) Мистер Пицца попытался было решить задачу, интегрируя по траектории черепашки, и уже достал из кармана программируемый микрокалькулятор последней модели, как вдруг миссис Пицца воскликнула:

— Не нужно никакой высшей математики, Пеппероне! Задача решается очень просто! Черепашки встречаются в центре комнаты через 5 мин, Какая идея пришла в голову миссис Пицца?

Рассмотрим каких-нибудь двух черепашек, расположенных в двух соседних вершинах квадрата, например Абнера и Берту. В каждый момент Берта движется под прямым углом к Абнеру, ползущему к ней, так как Абнер всегда ползет к Берте, а Берта всегда ползет к Чарлзу. Именно поэтому черепашки все время находятся в вершинах квадрата. Поскольку Берта никогда не ползет к Абнеру и не уползает от него, то ее движение не увеличивает и не уменьшает разделяющее их расстояние и при подсчете времени движением можно пренебречь. Дело обстоит так, как если бы Берта оставалась в своем углу комнаты, а Абнер полз к ней вдоль стенки.

В этом и состоит ключ к решению задачи. Криволинейный путь Абнера должен совпадать по длине со стороной начального квадрата, а так как эта сторона равна 300 см и Абнер ползет со скоростью 1 см/с, то он доползет до Берты за 300 с, или 5 мин.

То же можно сказать и о всех остальных черепашках. Следовательно, все черепашки встречаются в центре комнаты по истечении 5 мин.

При помощи микрокалькулятора можно построить траектории черепашек — кривые, описываемое вершинами вращающегося и одновременно сжимающегося квадрата, если нанести на диаграмму последовательные положения вершин через определенные промежутки времени. Результат такого рода выкладок представлен на рис. 10.

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

Предположим теперь, что исходные многоугольники неправильные. Что произойдет, например, если четыре черепашки займут исходные позиции в вершинах прямоугольной, а не квадратной комнаты?

Предположим, что черепашки Тома Пиццы после встречи в центре комнаты расползаются, причем каждая из них движется по прямой от своего соседа слева? Можно ли утверждать, что черепашки непременно расползутся по углам комнаты?

Экономия на спичках

–  –  –

Игры со спичками Мабель упустила из виду одно важное обстоятельство: ставя задачу, проф. Квиббл не говорил, что спички должны оставаться на плоскости. Если же выйти из плоскости в трехмерное пространство, то из 12 спичек можно составить 12 ребер куба, у которого, как известно имеется 6 квадратных граней. Мы видим, что ключ к решению спичечной головоломки проф. Квиббла аналогичен идее, позволившей Рози по-новому разрезать головку сыра.

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

А вот еще 6 «спичечных» задач на сообразительность. Удастся ли вам их решить?

I. Передвинув как можно меньше спичек, составьте квадрат.

2. Уберите.как можно меньше спичек так, чтобы оставшиеся спички образовали 4 равносторонних треугольника таких же размеров, как и 8 треугольников в исходной конфигурации, и нигде не торчали свободные концы.

^

3. Передвинув как межно меньше спичек, заставь* те рыбку плыть в противоположную сторону.

4. Передвинув как можно меньше спичек, заставьте поросенка повернуться в противоположную сторону.

5. Передвинув как можно меньше спичек, извлеките вишенку из бокала. «Пустой» бокал не обязательно должен стоять на иожке: он может лежать на боку. Передвигать вишенку запрещается.

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

Поместив решения этих забавных головоломок, мы бы только испортили вам удовольствие. Сообщаем лищь, что первую задачу можно решить, передвинув 1 спичку, вторую — убрав 4 спички, третью, четвертую и пятую — передвинув соответственно 3, 2 и 2 спички, шестую — не передвинув ни одной спички, Хитроумные разбиения Рэнсом — землемер, который специализируется в разбиении участков самой причудливой формы на конгруэнтные части.

Однажды его попросили разделить вот такой участок на 4 одинаковые части. Как это сделать?

Разделить участок можно единственным способом — так, как показано иа рисунке.

В следующий раз Рэнсому понадобилось разделить на 4 конгруэнтные части участок, имевший форму равнобочной трапеции. Сделать это было нелегко.

Однако Рэнсом не отступил перед трудностями и сумел найти единственное решение.

Разделить на 4 конгруэнтные части квадратный участок для такого специалиста, как Рэнсом, было сущей забавой, но когда его попросили разделить квадратный участок на 5 конгруэнтных частей, он стал в тупик.

–  –  –

Задачи на разрезание Если хотите позабавиться, предложите своим друзьям решить три задачи Рэнсома. В двух первых задачах участки в форме угла и равносторонней трапе»

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

Предложенное Рэнсомом простое решение приходит в голову очень немногим. Можно доказать, что квадрат можно разделить на 5 конгруэнтных частей только так, как это сделал Рэнсом, и никак иначе.

Если вашприятель «попадется» на третьей задаче, вам удастся поймать его вторично, задав ему четвертую задачу, тесно связанную с предыдущей. Прежде всего покажите ему, как поле, изображенное на рис. //, можно разделить на 4 конгруэнтные части, и спросите, можно ли это поле разделить на 3 конгруэнтные части?

После нескольких попыток ваш друг скорее всего признает себя побежденным и преисполнится уверенности, что ему досталась необычайно трудная задача. Каково же будет его удивление, когда он узнает, что эта задача допускает неожиданно простое решение, аналогичное предложенному Рэнсомом разбиению квадрата на 5 конгруэнтных частей. Это решение приведено на рис. 12. Как и в случае квадрата, метод позволяет производить разбиение поля на любое число конгруэнтных частей.

Задачи, которые вриходится решать землемеру Рэнсому и ресторатору Джо, относятся к одному из увлекательнейших разделов занимательной ыатематики, называемому иногда теорией разбиений. Их неожиданны* решения могут нодеказать, как следует браться за многие практические задачи геометрии на плоскости и в пространстве. Две первые задачи Рэнсома представляют особый интерес, поскольку в каждой из них участок делится на меньшие участки, повторяющие по форме исходный- Фигуры, которые можно без просветов и наложений, как плитками, вымостить уменьшенными их копиями (репликами), принято называть реп-плитками.

На рис. 13 показано еще несколько реп-плиток.

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

Например, рассмотрим Г-образную фигуру, «репплиточность» которой доказал, решив первую задачу, Рэнсом. Сложенные вместе, четыре такие фигуры образуют новую Г-образную фигуру, которая в 4 раза больше исходной. Из четырех новых фигур в свою очередь можно составить еще большую Г-образную фигуру. Этот процесс можно продолжать сколь угодно долго и выложить Г-образными фигурами все возрастающих размеров бесконечную плоскость. Неограниченно долго можно продолжать не только составление все более крупных Г-образныя реп-плиток, но и разрезание их на все более мелкие фигуры.

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

Еще меньше известно об объемных реп-плитках.

К числу их заведомо принадлежит куб, так как из 8 кубов можно составить 1 куб большего размера так же, как из 4 квадратов можно сложить 1 квадрат побольше. Можете ли вы назвать еще какиенибудь объемные реп-плитки?

Если конгруэнтные части по форме не должны повторять составленную из них фигуру, то ВОЗМОЖНОСТИ для придумывания задач-головоломок расширяются* Например, Т-образная фигура на рис. 14 составлена из 5 квадратов. Ее невозможно разрезать на четыре Т-образные фигуры, но, может быть, вам удастся разбить ее на 4 конгруэнтные фигуры какой-нибудь другой формы?

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

J5 Решения (способы раэрезания) приведены в конце книги.

Еще один интересный класс задач на разрезание образуют задачи на разрезание одного заданного многоугольника на наименьшее число частей любой формы, из которых можно составить другой заданный многоугольник. Например, на сколько частей достаточно разрезать квадрат, чтобы из них можно было составить равносторонний треугольник? (На 4 части.) Наиболее полно теория разбиений и весь круг вопросов, связанных с разрезанием, изложен в книге Гарри Линдгрена «Занимательные задачи на разрезание» *.

* Лиидгрен Г. Занимательные задачи на разрезание. — М.:

Мир, 1977.

Мисс Евклид и ее кубики

–  –  –

Прежде чем задать свой третий вопрос, мнсс Евклид положила на верхнюю грань куба линейку.

Мисс Евклид. Как с помощью этой линейки проще всего измерять длину диагонали куба АВ?

На сколько вопросов мисс Евклид вы смогли бы ответить?

Я смог ответить на 2 из 3 вопросов.

Каверзные задачи Решение задачи 1. Докажем, что куб 4 X 4 X 4 невозможно разрезать на 64 кубика менее чем 6 плоскими разрезами (при условии, что после каждого разреза части куба разрешается перекладывать).

Рассмотрим для этого любой из 8 внутренних кубиков.

Ни один из внутренних кубиков не имеет «готовых»

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

Существует ли общий метод, позволяющий распилить любой прямоугольный параллелепипед с целочисленными длинами ребер на единичные кубы при минимальном числе разрезов (части параллелепипеда разрешается переставлять)? Да, такой метод существует и заключается в следующем. Рассмотрим 3 разных куба, длины ребер которых равны длине, ширине и высоте параллелепипеда. Для каждого куба определим минимальное число разрезов, которые необходимо провести, чтобы разделить его на слои единичной толщины. Для этого проведем плоский разрез перпендикулярно ребру куба через целую точку, расположенную как можно ближе к середвнё ребра (если в длине ребра укладывается четное число единиц, то распил делит ребро пополам; если же в длине ребра укладывается нечетное число единиц, то распил проходит на расстоянии половины единицы длины от середины ребра), переложим полученные части и будем повторять всю процедуру до тех пор, пока весь куб не распадется на слои единичной толщины. Сумма трех минимумов (по одному для каждого ребра) даст нам ответ задачи.

Например, чтобы распилить на единичные кубики прямоугольный параллелепипед 3 4 Х 5, необходимо провести 7 плоских разрезов: 2 для ребра 3, 2 для ребра 4 и 3 для ребра 5. Доказательство этого алгоритма было впервые опубликовано в журнале Mathematics Magazine в 1952 г.

Решение задачи 2. Задача решается просто, если сообразить, что на еще одной грани куба можно провести третью диагональ, соединяющую концы диагоналей, проведенных мисс Евклид (рис. 16).

Три диагонали образуют равносторонний треугольник. Так как каждый из углов равностороннего треугольника равен 60°, то и угол между проведенными мисс Евклид диагоналями равен 60°, Вторая задача мисс Евклид допускает изящное обобщение. Предположим, что мисс Евклид провела на поверхности куба две прямые, соединяющие середины Л, б и С трех ребер (рис. 17). Чему равен угол ABC между этими прямыми?

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

То, что поперечное сечение, делящее куб на две половины, может иметь форму правильного шестиугольника, неожиданно и в какой-то мере противоречит интуиции. Ну, а коль скоро мы знаем, что две проведенные мисс Евклид линии являются двумя смежными сторонами правильного шестиугольника, то найти угол между ними не составляет никакого труда: он равен 120°.

Рис. 17 наводит на мысль о еще одной интересной задаче. Предположим, что муха хочет проползти по поверхности куба из точки А в точку С. Можно ли считать путь, образованный отрезками АВ и ВС, кратчайшим?

Эту задачу легко и просто решит тот, кто догадается, что кратчайший путь из точки А в точку В на поверхности куба можно найти, если две смежные грани куба развернуть так, чтобы их плоскости совпали: кратчайшим будет отрезок прямой, соединяющий на развертке точки Л и С. Развернуть две смежные грани куба так, чтобы плоскости их совпали, можно двумя способами, выбрав либо переднюю и верхнюю грань, либо переднюю и правую грань, поэтому при решении задачи необходимо соблюдать осторожность. В первом случае мы получаем путь длиной д/2~, во втором — путь длиной V2.5.Следовательно, на рис. 17 изображен кратчайший путь на поверхности куба из Л в С.

Решение задачи 3. Разумеется, длину диагонали куба можно определить, измерив линейкой длину ребра и дважды применив теорему Пифагора. Но диагональ куба можно измерить линейкой гораздо более простым способом. Поставив куб на край стола, отмерим отрезок, равный по длине ребру куба, и концы отрезка пометим, после чего сдвинем куб на длину ребра вдоль края стола (рис. 18). Расстояние от А до В в точности равно диагонали куба, и его можно измерить линейкой.

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

ПО По ковровой дорожке Ковровое покрытие для кольцевого коридора в здании нового аэропорта было поручено изготовить компании, возглавляемой мистером Тэком.

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

Мистер Тэк, Уберите чертеж, чтобы я его больше не видел!

Как, скажите на милость, я смогу представить смету иа ковровое покрытие, если мне ие известна площадь коридора? Посоветуюсь-ка я с моим дизайнером мистером Шарпом.

–  –  –

Удивительная теорема Мистер Тэк рассуждал следующим образом. Мистер Шарп пользуется заслуженной репутацией искусного и сведущего геометра, поэтому, если он говорит, что у него есть формула, позволяющая вычислять площадь кольца по длине хорды, касательной к внутренней окружности, то она у него действительно есть. Если длина хорды, касательной к внутренней окружности, будет оставаться равной 100 м, то, как бы ни изменялись радиусы внешней и внутренней окружностей, по формуле мистера Шарпа площадь кольца должна оставаться неизменной.

Далее мистер Тэк спросил себя, что произойдет, если радиус внутреннего кольца уменьшится до нуля — своего минимального значения. Кольцо в этом случае превратится в круг, а хорда длиной 100 м станет диаметром круга. Площадь круга равна я-50 2 кв. м « 7854 км. м. Следовательно, если предположить, что формула мистера Шарпа существует, то площадь кольца также должна быть равна 7854 кв. м.

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

Эту удивительную теорему нетрудно доказать, если воспользоваться формулой для площади круга.

Трехмерный аналог этой задачи звучит так: найти объем отрезка толстостенной цилиндрической трубы, если помимо его длины известна длина самого длинного отрезка, который только умещается на одном из торцов трубы (рис. 19). Этот отрезок соответствует касательной в двумерной задаче, и, зная его длину, мы без труда находим площадь поперечного сечения трубы. Умножив площадь сечения на длину отрезка трубы, найдем его объем.

Менее очевидным трехмерным аналогом задачи о площади кольца является следующая красивая задача. Через центр шара просверлено сквозное цилиндрическое отверстие. Длина канала 6 см. Чему равен объем оставшейся части сферы? И в этом случае кажется, что ответить на вопрос задачи, невозможно: слишком скудны сведения, которыми мы располагаем. Однако исходя из совершенно элементарных соображений, можно показать, что оставшаяся часть сферы имеет такой же объем, как сплошная сфера, диаметр которой равен длине просверленного канала.

Как и в предыдущем случае, ответ задачи мы получаем сразу же, как только предположим, что задача разрешима! Действительно, если решение задачи существует, то объем части сферы, оставшейся после просверливания сквозного отверстия, не должен зависеть от диаметра отверстия. Устремим поэтому диаметр отверстия к наименьшему значению — нулю.

Отверстие при этом сжимается в прямую — дааиетр сплошной сферы. Следовательно, объем оставшейся части сферы равен 4 /з-Я"3 3 куб, см = 36л куб. см.

Торт для именинницы

–  –  –

Мистер Джонс. Вы оба заблуждаетесь. Сьюзен получила ровно четверть торта и ровно четверть глазури.

Не могли бы вы объяснить, прав ли мистер Джонс?

Чтобы убедиться в правоте мистера Джойса, достаточно продолжить линии разрезов за центр до пересечения с противоположными сторонами торта. Продлив каждый разрез, вы тотчас же убедитесь, что они делят торт на четыре конгруэнтные части.

Как разрезать праздничный пирог?

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

Предположим, например, что торт или праздничный пирог испечены в форме равностороннего треугольника и разрезы проведены под углом 120° из центра (рис. 20). Ясно, что каждый кусок составляет треть пирога. В этом нетрудно убедиться, если провести штриховую линию. Если пирог испечен в форме правильного пятиугольника, то, проведя из центра два разреза под углом 72°, мы отрежем от пирога го одну пятую. Если пирог имеет форму правильного шестиугольника, то, чтобы отрезать от него одну шестую, необходимо провести из центра два разреза под углом 360° : 6 = 60°. Тот же метод обобщается и на правильные многоугольники с большим числом сторон, хотя угол между разрезами не всегда выражается целым числом градусов.

Разрезание квадрата на 4 конгруэнтные части другой формы долгое время было одной из излюбленных задач на разрезание. Если, разрезав картонный квадрат на 4 части так, как показано на рис. 21, вы предложите кому-нибудь из своих знакомых составить квадрат из четвертушек, то, как правило, ваш приятель сочтет задачу трудной. После того как он успешно справится с ней, попросите его составить из тех же четвертушек два квадрата.

Последняя задача в отличие от предыдущих носит несколько жульнический характер: решить ее ваш приятель сможет лишь в том случае, если догадается, что одним из двух квадратов служит отверстие в середине другого квадрата (рис. 22). Размеры отверстия зависят от угла, который линия разреза составляет со стороной исходного квадрата. Если этот угол равен 90°, то отверстие исчезает. Если угол равен 45°, то отверстие достигает наибольших размеров.

Глава о

Находки в мире чисел

НЕОЖИДАННЫЕ РЕШЕНИЯ

АРИФМЕТИЧЕСКИХ ЗАДАЧ

Говоря об арифметике, разные люди вкладывают в это понятие различное содержание. Мы будем понимать под арифметикой все, что так или иначе связано с изучением свойств целых чисел и операций сложения, вычитания, умножения и деления, производимых над числами.

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

Такие арифметические теоремы, как «2 -f 1 = 3», созревали и становились достоянием умов на протяжении нескольких столетий. Если бы мы могли прокрутить назад пленку, на которой была бы запечатлена история человечества, то вряд ли нам удалось найти какой-то век, о котором можно было бы с уверенностью сказать: «Именно тогда человечество открыло арифметику». Маленькие дети овладевают понятием числа так же постепенно и незаметно, В один прекрасный день ребенок может впервые заявить изумленным родителям: «Один плюс один — два», но смысл этого утверждения ясен малышу задолго до того, как он выскажет свою первую арифметическую теорему.

Все истинные теоремы арифметики следуют непо-1 средственно из аксиом и определений числовой системы, но это отнюдь не означает, будто истинность или ложность любого арифметического утверждения легко распознается на слух. Если кто-нибудь скажет, что при умножении 12 345679 на 9 получается 111 111 111, вы можете не верить ему до тех пор, пока сами не умножите одно число на другое. Существуют арифметические теоремы, которые просто сформулировать, но так трудно доказать, что никто пока не знает, верны ли они. Примерам таких утверждений может служить знаменитая гипотеза Гольбаха: всякое четное число больше 2 представимо в виде суммы двух простых чисел. Никому до сих пор не удалось ни доказать ее, ни построить контрлример.

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

Дихотомия (последовательное разбиение множества на 2 части), играющая важную роль в вычислительной технике и теории автоматической сортировки данных, лежит в основе задачи об угадывании номера телефона Элен и позволяет читателю войти в круг вопросов, связанных с двоичной системой счисления. Принцип «птичка в клетке», известный также под названием принципа Дирихле, позволяет доказывать многие важные факты из теории чисел. Мы используем его для доказательства двух забавных утверждений: о бумажных долларах и о числе волос на голове человека. Свойство двух целых чисел быть взаимно простыми (не иметь общих делителей, кроме единицы) позволяет доказать, что, за исключением 12 часов, часовая, минутная и секундная стрелки часов никогда не совпадают (обычно это вычисление доказывают, проделывая довольно громоздкие выкладки).

Задача о счете по бутылкам легко решается, если воспользоваться понятием сравнения по модулю, и заставляет вспомнить о знаменитой задаче Иосифа Флавия, которую можно удивительно наглядно продемонстрировать при помощи колоды игральных карт.

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

Разбитые грампластинки

–  –  –

Половинки целого Неужели вы попались в ловушку и не подумали, что половина чего-то и 7г могут оказаться целым числом? Если да, то, должно быть, попытались решить задачу, ведя счет на половинки грампластинок, и, запутавшись вскоре в вычислениях, оставили затею как безнадежную. Неожиданно простым решение получается, если догадаться, что половина от нечетного числа и еще половина равны целому числу.

По словам Элен, у нее после того, как она преподнесла свой второй подарок, осталась 1 пластинка, Значит, до того, как она подарила часть своих пластинок Джо, у нее должны были остаться 3 пластинки. Половина от 3 составляет %, а 3 / 2 + '/г = 2, поэтому Элен подарила Джо 2 нластинки, после чего у нее осталась 1 пластинка. Продолжая решать задачи «задним ходом», нетрудно установить, что сначала у Элен было 7 пластинок и что 4 пластинки она подарила Сьюзи.

Разумеется, задачу можно было бы решать и алгебраически. Составление и решение соответствующего уравнения — превосходное упражнение по элементарной алгебре. Удивительно, что такая простая задача приводит к такому сложному уравнениюз Л1* + 2 —• J V 2) Новые головоломки того же типа мы получим, варьируя параметры задачи. Предположим, например, что Элен каждый раз дарит кому-нибудь половину своих пластинок и еще полпластинки, проделывает это не дважды, а трижды и остается не с одной пластинкой, а без единой пластинки. Сколько пластинок было у нее сначала? Возможно, вам покажется странным, что ответ остается прежним — 7 пластинок, но удивительного здесь ничего нет: в третий раз Элен дарят последнюю оставшуюся у нее пластинку.

А сколько пластинок было у нее сначала, если она дарит каждый раз половину своих пластинок и еще полплаетияки и проделывает эту процедуру 4 раза, после чего у нее остается 1 пластинка? А если Элен дарит пластинки & раз? Какого рода последовательность порождают возникающие в этой серии задач числа?

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

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

При каких ограничениях в задачах этого типа необходимость дарить пластинки «частями» вообще отпадает?

Доля, которую осколки «разбитой» пластинки составляют от целого, может варьироваться от подарка к подарку. Вот, например, задача, в которой эта доля не остается постоянной.

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

Свое решение он осуществил в 5 этапов:

1. Продал половину всех своих рыбок и еще полрыбки.

2. Продал треть оставшихся рыбок н еще треть рыбки.

3. Продал четверть оставшихся рыбок и еще четверть рыбки.

4. Продал пятую часть оставшихся рыбок и еще одну пятую рыбки.

После этого у него осталось 19 рыбок. Разумеется, с золотыми рыбками он обращался бережно и ему и в голову не приходило делить рыбку на части. Сколько рыбок было у мальчика сначала? Ответ: 101 рыбка, но решить эту задачу не так просто, как предыдущие. Попробуйте и вы убедитесь в этом сами.

А вот еще одна разновидность задач того же типа.

У одной дамы было в сумочке несколько купюр достоинством в 1 доллар каждая. Других денег у нее с собой не было.

1. Половину денег дама израсходовала на покупку новой шляпки, а 1 доллар заплатила за освежающий напиток.

2. Зайдя в кафе позавтракать, дама израсходовала половину оставшихся у нее денег и еще 2 доллара заплатила за сигареты.

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

Ответ приведен в конце книги.

Заметим, что во всех вариантах в условиях задачи непременно говорится, сколько грампластинок, золотых рыбок или купюр остается у действующего лица по окончании всех перипетий. Во многих случаях ответ задачи можно получить и без такой информации, но для этого пришлось бы решать в целых числах некоторые неопределенные уравнения. Наиболее известная задача такого рода легла в основу рассказа американского писателя Бена Эймса Уильямса «Кокосовые орехи».

Действие рассказа происходит на острове, на который после кораблекрушения попадают 5 человек и 1 обезьяна. Первый день они собирают кокосовые орехи. Ночью один из людей просыпается и решает забрать причитающуюся ему долю орехов. Он раскладывает орехи на 5 одинаковых кучек, отдает лишний орех обезьяне и, спрятав свою долю, укладывается снова спать.

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

Затем по очереди просыпается третий, четвертый и пятый невольный обитатель острова, и каждый делает то же, что и первые два. Утром вся пятерка делит оставшиеся орехи на 5 равных частей. На этот раз ни одного лишнего ореха не остается.

Сколько кокосовых орехов было собрано первоначально?

Задача допускает бесконечно много решений. Наименьшее из них — 3121 орех. Решить задачу не очень просто.

Коль скоро мы заговорили о кокосовых орехах, я хочу предложить вам одну задачу, которую можно решить сразу. При расчистке джунглей было собрано 25 кокосовых орехов, обезьяна стащила все орехи, кроме 7, Сколько орехов осталось? Ответ: не 18.

Лохнесское чудовище

–  –  –

Половина длины?

По словам Боба, лохнесское чудовище имеет в длину 20 м и еще половину своей длины, то есть длина чудовища равна сумме 2 слагаемых: 20 м и половины длины чудовища. Разделите мысленно длину чу~ довища пополам. Если вся длина равна сумме 2 слагаемых, из которых одно равно половине длины, а другое 20 м, то на 20 м приходится другая половина длины. Следовательно, полная длина составляет 40 м.

Задача Боба допускает простое алгебраическое решение: если х — полная длина лохнесского чудовища, то х = 20 + х/2.

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

Кирпич иа одной чаше весов уравновешен на другой чаше 3 Д кирпича и гирей в 3 / 4 кг. Чему равна масса кирпича?

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

Один лишний

–  –  –

Даже когда музыканты разбились на пары, Спнро все равно остался без партнера.

Хотя это было не ее дело, Элен подошла к дирижеру.

Элен. Позвольте мне дать вам один совет?

Дирижер. Мне сейчас не до, вас, милая девушка! И без того голова идет кругом.

Элен. Хоть вы и не очень вежливы, я все равно скажу вам, что нужно делать. Перестройте музыкантов в колонну по пять!

Боб. Я как раз собирался предложить то же самое!

Когда оркестр перестроили в колонну по пять, все шеренги оказались заполнены.

Сколько музыкантов было в оркестре?

Как восстановить все число по остаткам Элен просто пересчитала всех музыкантов в оркестре и обнаружила, что число их кратно 5. Но как можете вы, не видя всего оркестра, определить, сколько в нем музыкантов?

Сделать это можно следующим образом. Пусть N — число музыкантов в оркестре. Мы знаем, что при делении на 2, 3 и 4 оно дает остаток 1 (живым воплощением остатка служит Спиро, в одиночестве марширующий вслед за оркестром). Наименьшее число, обладающее этим свойством, на 1 больше наименьшего общего кратного (НОК.) чисел 2, 3 и 4, то есть числа 12. Рассмотрим теперь все числа, кратные 12. Увеличив любое из них на 1, мы получим число, которое при делении на 2, 3 и 4 дает остаток 1.

Когда оркестр перестраивается в колонну по 5, то остаток равен 0. Следовательно, N делится на б без остатка. Решением задачи служат числа, кратные б, которые встречаются в последовательности 13, 25, 37, 49, 61, 73, 85, 97, 109, 121, 133, 145,...

Поскольку число 145 слишком велико для школьного оркестра, то N равно либо 85, либо 25. Имеющаяся у нас информация не позволяет отдать предпочтение какому-нибудь из этих двух чисел.

Хорошим вариантом предыдущей задачи может служить следующая задача. При перестроениях оркестра в колонну по два, три и четыре в последней шеренге каждый раз недостает одного человека, а при построении в колонну по пять все шеренги оказываются заполненными. Сколько музыкантов в оркестре? На этот раз мы должны выписать последовательность чисел, которые на 1 меньше кратных двенадцати и делятся на 5 без остатка: 35, 95, 155,...



Pages:   || 2 | 3 |
Похожие работы:

«1 УТВЕРЖДАЮ УТВЕРЖДАЮ Председатель Министр общественной организации спорта, туризма и "Самарская областная федерация молодежной политики спортивного туризма" Самарской области Р.И.Хакимов _С.П.Бамбуров ""_2012 года ""_2012 года ПОЛОЖЕНИЕ о проведении официальных спортивных соревнований Самарско...»

«Ордена Ленина и ордена Октябрьской Революции Институт атомной энергии им. И. В. Курчатова В.В. Гончаров, К.П. Дубровин, ИАЭ-4866/3 Е.Г. Иванов, А.Ф. Швоев, В.А. Шестернин ИЗУЧЕНИЕ РАБОТОСПОСОБНОСТИ ОПЫТНЫХ ПАРТИЙ ТВС ВВЭР-440...»

«В лучистой филиграни. Сборник научных трудов к 65-летию С. М. Шаулова Уфа — 2014 УДК 82/821.0 ББК 83.3. В11 В лучистой филиграни. Сборник научных трудов к 65летию С. М. Шаулова / Сост. Б. В. Орехов, С. С. Шаулов. — Уфа: Изд-во БГПУ,...»

«Русский язык демо14 – 1 / 8 Тест по русскому языку Демонстрационный вариант 2014 г. ИНСТРУКЦИЯ Тест состоит из частей А и В. На его выполнение отводится 100 минут. Задания рекомендуем выполнять по порядку. Если задание не удается выполнить сразу, перейдите к следующему. Если останется время, вернитесь к пропущенным заданиям. Часть А В...»

«Структура сложных сетей Лекция N 4 курса “Алгоритмы для Интернета” Юрий Лифшиц ПОМИ РАН СПбГУ ИТМО Осень 2006 1 / 34 M.E.J. Newman Six degrees of separation это гипотеза, утверждающая что от любой человек на Земле...»

«\ql ГОСТ Р 12.0.007-2009. Система стандартов безопасности труда. Система управления охраной труда в организации. Общие требования по разработке, применению, оценке и совершенствованию (утв. и введен в действие Приказом Ростехрегулирования от 21.04.2009 N 138-ст) Доку...»

«РифРингRR-2TS СТАЦИОНАРНЫЙПЕРЕДАТЧИК РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ Стационарный радиопередатчик “RR-2TS” входит в состав аппаратуры радиоканальной охранной сигнализации “Риф Ринг-2” и предназначен для беспроводной передачи тревожных сигналов с выходов различных объектовых приборов, охранных из...»

«Старший методист В.Н. Дмитриев 160-я танковая бригада 160-я танковая бригада начала формироваться 13 апреля 1942 г. Горьковским автобронетанковым центром согласно Постановлению № ГКОсс от 16 февраля 1942 г. О формировании танковых бриг...»

«В лучистой филиграни. Сборник научных трудов к 65-летию С. М. Шаулова Уфа — 2014 УДК 82/821.0 ББК 83.3. В11 В лучистой филиграни. Сборник научных трудов к 65летию С. М. Шаулова / Сост. Б. В. Орехов,...»

«Руководство пользователя Интернет-банкинг для физических лиц КристалБанк Версия 2.1.6.Х Интернет-банкинг для физических лиц (КристалБанк) Руководство пользователя ОГЛАВЛЕНИЕ 1. РЕГИСТРАЦИЯ 2. ВХОД В СИСТЕМУ 2.1. Восстановление пароля 3. ОБЩИЕ ПРИН...»

«КОМПЬЮТЕРНЫЕ ИССЛЕДОВАНИЯ И МОДЕЛИРОВАНИЕ 2011 Т. 3 № 4 С. 413420 АНАЛИЗ И МОДЕЛИРОВАНИЕ СЛОЖНЫХ ЖИВЫХ СИСТЕМ УДК: 539.3 Метод моделирования структуры компактной костной ткани Т. В. Колмакова Томский государственный университет, Россия, 634050, г. Томск,...»

«Иван Сергеевич Шмелев Солнце мертвых (сборник) Текст предоставлен издательством http://www.litres.ru/pages/biblio_book/?art=6994781 Солнце мертвых / Иван Шмелев: Эксмо; Москва; 2014 ISBN 978-5-699-73291-3 Аннотация Иван Сергеевич Шмелев (1873–1950) – выдающийся русский писатель, великий мастер образа и слова, сохранивший в своих произведениях...»

«Випуск 1 (54)’ 2015   Науковий часопис НПУ імені М.П. Драгоманова оцінці якості підготовки у гирьовому спорті та дає змогу підвищити функціональні можливості спортсменів. Застосування біомеханіки в гир...»

«Утвержден "30" апреля 2013 г. Правлением ЗАО ЮниКредит Банк Решение № 05C/2013 от "30" апреля 2013 г. ЕЖЕКВАРТАЛЬНЫЙ ОТЧЕТ Закрытое акционерное общество "ЮниКредит Банк" Код кредитной организации эмитента: 00001-В за 1 квартал 2013...»

«1 1АР1РКСКАЯ резня /дсасгвуюшие лиил К а р л Д е в я т ы й, король французский. Г е р ц о г А н ж у й с к и й, его брат, затем король Генрих Третий. Король Наваррский. П р и н ц К о н д е, двоюродный брат короля Наварр ского. ГерцогГиз Кардинал Лотарингский J 0Ратья· ГерцогДюмен Сын г е р ц о г а Г и з а, мал...»

«ОГЛАВЛЕНИЕ БЛАГОДАРНОСТИ АВТОРА................................................ 9 ПРЕДИСЛОВИЕ....................................................... 11...»

«Георгий Иванович Свиридов Ринг за колючей проволокой текст предоставлен издательством http://www.litres.ru/pages/biblio_book/?art=146544 Георгий Свиридов Ринг за колючей проволокой: Вече; Москва; ISBN 5-9533-0672-5 Аннотация Эсэсовцы сделали все, чтобы превратить Бухенвальд в настоящий ад. Но и в кошмаре концентрационн...»

«Перед применением внимательно прочесть данное руководство пользователя ГАРАНТИЯ EM420A/420B Гарантируется отсутствие дефектов материала и производства данного прибора на период один год. При обнаружении дефектов прибора в т...»

«Ученые записки Таврического национального университета им. В.И. Вернадского Серия География. Том 24 (63). 2011 г. №1. С.258-266. УДК 911.3:338.48 ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ ОПЫТА СТРАТЕГИЧЕСКОГО ПЛАНИРОВАНИЯ РЕКРЕАЦИОННОЙ СФЕРЫ РОССИЙСКОЙ ФЕДЕРАЦИИ, РЕСПУБЛИКИ БОЛГАРИЯ И ТУРЕЦКОЙ РЕСПУБЛИКИ В ПРОЦЕССЕ ПРЕОДОЛЕНИЯ ТЕ...»

«Неприкосновенный запас. 2009. №3 Андрей Макарычев Власть, политика и федерализм в России: уроки "критической теории" Введение Некоторые симптомы последнего времени показывают, что в российской академиче...»

«ISSN 0536 – 1036. ИВУЗ. "Лесной журнал". 2015. № 1 УДК 630*5 ДИНАМИКА ОТПАДА ДЕРЕВЬЕВ В СМЕШАННЫХ СРЕДНЕТАЕЖНЫХ ОСИНОВЫХ НАСАЖДЕНИЯХ АРХАНГЕЛЬСКОЙ ОБЛАСТИ © А.А. Горбунов, асп. С.В. Третьяков, д-р с.-х. наук, доц. Северный (Арктический) федеральный университет им. М.В. Ломоносова, наб. Северн...»

«УДК 514 О.В. Зацепина КЛАССИФИКАЦИЯ ГИПЕРКОМПЛЕКСОВ ПРЯМЫХ В 1 S 5 В РЕПЕРЕ ПЕРВОГО ПОРЯДКА Многообразие прямых в n-мерном пространстве зависит от 2n – 2 параметров. Одно дополнительное условие на плюккеровы координаты задает 2n – 3 параметрическое множество прямых, которо...»








 
2017 www.kniga.lib-i.ru - «Бесплатная электронная библиотека - онлайн материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.