Ленивая математика

(семь нескучных задач, решаемых без напряжения)

Математика для одних – ненаглядная, а для других – не наглядная. Есть люди, которые любят математику, но не переносят физику. Оставим в стороне вопрос о качестве преподавания этих предметов в различных школах, а посмотрим на сами предметы другими глазами. Это касается не только естественных предметов (математика в средние века считалась гуманитарной наукой), но и прикладных, к коим относится и информатика.

Поставим вопрос: можно ли из соображений здравого смысла без всяких вычислений или размышлений получить значимый результат? «Конечно, нет!» – скажете вы и ошибетесь.

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

В бытность учеником школы № 444 г. Москвы (о ней была статья Елены Давыдовой «Школьный виртуальный музей информатики» в КвШ № 7, 1999), мне, как и моим однокашникам, пришлось решать (кажется, во время контрольной работы) следующую задачу.

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

Позже я обнаружил, что это – частный случай более общей задачи: поделить отрезок на любое равное количество частей. Покажем, что эта задача может быть весьма актуальна на практике, а простота ее решения – воистину божественный подарок. Что такое параллельные прямые? Да это же линии, проведенные с помощью карандаша (или гвоздя) и ровной доски!

Не будем думать о геометрии ни секунды! Будем считать данные задачи черными, а построения — цветными. Смотрите на рисунок и радуйтесь!

Возьмем точку, наиболее удаленную от линии с отмеченным отрезком. Покрасим нашу точку в синий цвет. Зачем? Ну, нам ведь нужно получить какие-то точки пересечения. А почему наиболее удаленную? Для определенности. Через синюю точку и каждую из черных проведем по синей прямой. Они пересекут ближнюю черную прямую в зеленых точках, каждую из которых (все остальное — соединено!) соединим зелеными прямыми с черными точками. Они пересекутся в красной точке. Проведем красную линию через синюю и красную точки. Точка ее пересечения (желтая) с исходным отрезком делит его пополам. Задача решена. Желающие могут доказать это из подобия. А мы — продолжим.

А если выбрать синюю точку с другой стороны? Не торопитесь чертить! Просто поменяйте черные и зеленые точки местами. И считайте, что именно эти (черные) точки и были даны. Решение не изменилось!

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

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

В заключительной части замечательной статьи Феликса Широкова «Забытое исчисление (В мире цепных дробей)» (КвШ, № 1, 2000) приведена формула из папируса Ринда для приближенной квадратуры круга S = (1 – 1/9)² D². D – диаметр круга. Точность этой формулы, как написано у Широкова, составляет около 0,3%. Теперь заметим, что квадратура круга, невыполнимая циркулем и линейкой, в приближенном варианте строится с помощью реальной линейки и угольника.

Действительно, с помощью линейки мы строим две параллельные прямые, так, что одна из них содержит диаметр круга, и делим его линейкой сначала на две, а затем на три части. Можно продолжать до 9, но проще нарисовать еще одну параллельную линию и поделить треть на три еще раз. Отбросив крайнюю девятую часть, с помощью угольника проводим перпендикуляры через концы отрезка длиной 8/9D и через центр круга. Линию, проведенную через центр (второй диаметр) подвергаем той же «экзекуции», что и первую. На рисунке линии построения квадрата намеренно смещены, чтобы не загораживать построений. В результате имеем еще одну пару точек на расстоянии 8/9D, но на перпендикулярном диаметре. Опять применяем угольник. Полученный квадрат представляет собой искомую квадратуру. Точность формулы явно превышает реальную точность построения и измерения диаметра нарисованного круга (последнее – если хочется применять современные методы, например, линейку с делениями, штанген-циркуль или сканер).

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

Пример 2. Трисекция угла: построить циркулем и линейкой угол, в три раза меньший данного.

Предлагаемый метод придуман Архимедом и описан в книге «Что такое математика» Р. Куранта и Г. Роббинса (М., Л. 1947). От себя добавлю, что циркуль у нас будет «ржавым», то есть с фиксированным радиусом. Кроме того, нам понадобится линейка, на которой этим самым циркулем отмечены две точки, соответствующие его радиусу. Именно эта линейка и позволяет преодолеть неразрешимость этой задачи. Пусть веселое солнышко на рисунке поможет прояснить наше сознание.

Как и было обещано, мы поделим угол на три части, пользуясь той же методикой, что и в предыдущем примере, — но с архимедовой хитростью. Пусть дан угол x. Проведем через его вершину окружность с помощью нашего циркуля, больше похожего на землемерный инструмент, чем на средство черчения. Одну из сторон угла продолжим так, чтобы она пересекла нашу окружность с двух сторон. Теперь приложим нашу линейку к точке пересечения другой стороны угла x с окружностью (точке C), и выберем такое ее положение, чтобы одна из отмеченных на линейке точек (A) лежала на продолжении стороны угла, а другая (B) – на окружности. По оговоренному выше условию |AB| = r, где r – радиус нашего циркуля.

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

Действительно, из рисунка видно, что треугольники ABO и BCO – равнобедренные. Так как сумма углов треугольника ABO равна величине развернутого угла ABС, то угол OBC в два раза больше y. Те же рассуждения относительно углов x, y и z дают желаемое доказательство: 180° = 4y + z = x + y + z, то есть x = 3y. Как говорили древние, quod erat demonstrandum – «что и требовалось доказать». Кстати, приятно видеть в школьных или студенческих тетрадях сокращение этого словосочетания: Q.E.D. или QED.

Наверное, с методической точки зрения ознакомление учеников с такой математикой способствовало бы воспитанию уважения и даже любви к этому предмету. Я, конечно, говорю за себя, но чтение таких книг, как «Конкретная математика» (Р. Грэхем, Д. Кнут, О. Паташник, Москва, «Мир», 1998), «Что такое математика» или «Замечательные дроби» (Н. М. Бескин, Минск, Вышейшая школа, 1980) приводит меня в восторг. Я бы не стал навязывать свое видение, если бы не тот факт, что книгу «Что такое математика» зачитывали до дыр, когда я еще пешком под стол ходил.

Академик В. И. Арнольд считает, что систематическое изучение математики не только «ум в порядок приводит», но и формирует адекватное мировоззрение. Кто из учеников знает, почему в году 365 дней и какой год будет високосным? Меня этому не учили даже в родной школе № 444, окончив которую, я с ходу решал любую задачу из Сканави («были когда-то и мы рысаками!»)... Вообще, средний образовательный уровень в наше время катастрофически падает. Я это вижу по молодежи, с которой приходится общаться. Нельзя всю жизнь выбирать Pepsi: не хлебом единым...

Кстати, о Pepsi. В эпоху перестройки мне довелось общаться с представителем одного из европейских филиалов фирмы Honeywell, известной не только в компьютерном мире. У бедолаги (видимо, от нашей еды) болел живот. Участники технической учебы, которую он вел, предложили ему что-нибудь принять, но он отказался, объяснив, что Кока-Кола – это как раз такое средство, изобретенное для армии США. Не могу ручаться за достоверность этой информации, но состав — вода, сахар, карамель и фосфорная кислота (что там еще?) – весьма вероятно губителен для наших очень меньших болезнетворных братьев. Кислая среда парализует все живое. Почему бы учителям химии не развлечь своих питомцев во время факультатива простеньким анализом тех же Pepsi или Coka? По крайней мере, ученики быстро поймут, что никакого кислотно-щелочного баланса не бывает, и что pH нормальной кожи 6-7 и более, а не 5,5.

Но вернемся к примерам. Раз уж мы говорим о геометрических построениях с намеком на практическое применение, приведу еще один пример из проективной геометрии, описанный в книге «Что такое математика».

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

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

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

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

«Все эти задачки достаточно простые!» – скажете вы, и тогда я вас спрошу...

Пример 4. Как с помощью бухгалтерского калькулятора (4 действия) определить логарифмический декремент затухания временного ряда?

«Что определить?!» – возмутитесь вы. А вот что. Все слышали о законе радиоактивного распада: m = = m⁰exp(-at), здесь m – масса вещества, m⁰ – масса в начале измерений, t – время, а a – тот самый логарифмический декремент (характеристика скорости уменьшения, прологарифмируйте выражение для m, и название станет ясно). Строго говоря, этот закон можно переписать в виде m_n = m₀ x_n, (x < 1) так как замеры не делаются непрерывно, вернее, даже непрерывную запись для обсчета приходится дискретизировать. Здесь n – номер точки, причем n = t/dt, где dt – интервал между измерениями (шаг дискретизации). Основание показательной функции x = exp(-adt).

Забегая вперед, отметим следующее: важно, чтобы exp(-adt) не оказалось бы слишком близким к единице, то есть чтобы шаг dt не был слишком мал.

Итак, рассмотрим «фазовый портрет» системы, описываемой уравнением m_n = m₀x_n. Под фазовым портретом чаще всего понимают зависимость скорости от координаты, но, как говорится, возможны варианты. Наш фазовый портрет будет выглядеть так: m_{n + 1}(m_n). Обратите внимание: ничего считать не нужно! Нужно просто построить график зависимости следующей измеренной точки от предыдущей. Построенная линия называется фазовой траекторией.

А теперь – барабаны и фанфары! m_n+1 = m₀x_n+1 = = m₀ xⁿx = m_nx. Не ошеломляет? Я пришел в восторг, когда записал эту формулу. Траектория на фазовом портрете представляет собой прямую линию, выходящую из начала координат. Достаточно как-либо провести усреднение экспериментальных точек на фазовом портрете, чтобы получить искомое значение x, например, просто найти среднее отношение m_n+1 /m_n или применить метод наименьших квадратов, поставив перед числителем и знаменателем знаки сумм. Никаких логарифмирований! Если процедура поиска a является частью циклического вычислительного процесса, то, заменив a на x, можно фантастически ускорить вычисления, так как накладные расходы на вычисление функций весьма значительны. Конечно, речь не идет о высокой точности. На таком фазовом портрете линейная зависимость тоже выглядит прямой (вырожденный случай экспоненты: a = 0), причем наличие свободного члена дает смещение этой прямой. Можно показать, что при малых значениях dt надежно определить прохождение траектории через 0 не удается, как и точно определить x.

После экскурса в физику и математику перейдем к информатике.

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

Пусть есть две битовые (логические) переменные a и b. Нетрудно видеть, что всего возможны четыре варианта сочетаний их значений: (0,0); (0,1); (1,0); (1,1). Пусть переменная c получает значения всевозможных логических функций от a и b. Знатоки комбинаторики сразу найдут, что всего возможны 16 вариантов. Стоп! Не будем думать, а просто переберем их все:

Шестнадцать всевозможных четверок значений определяют все мыслимые функции алгебры логики двух аргументов, или бинарных операций, некоторые из которых имеют специальный смысл. Так, например, c₂ – логическое сложение (ИЛИ), c₁₁ – сложение по модулю два (исключающее ИЛИ), c₁₅ – логическое умножение (И).

Вот это да! Мы получили значимый всеобъемлющий результат, ничего не считая, ни о чем не думая.

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

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

Доказательство этого факта из физических соображений я услышал когда-то в центральном лектории от лектора популярного курса «Физика в задачах и парадоксах» д. ф. - м. н. В. М. Колыбасова.

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

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

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

Такая программа не должна использовать дизассемблер или аналогичную методику. Известно, что написание подобной программы возможно практически на любом языке программирования. Более того, мне удалось сделать генератор такой программы на языках FORTRAN, REXX и KEXX. Не знаю, нужно ли приводить пример этих бестолковых с точки зрения полезности программ, подобных вирусам (они самовоспроизводятся), но читателям рекомендуется по крайней мере испытать себя в этом деле. На языке REXX удается написать эту программу в одну не слишком длинную строку.

Ясно, что язык должен позволять вводить текстовые константы, представляющие собой половину текста программы, и выводить их значения дважды — как текст программы и как значения текстовых констант. И все! Написание представляет собой итерационный процесс, который, к счастью, сходится. Можно даже предусмотреть дополнительный текст для идентификации автора. Идея генератора связана с тем, что нужно сгенерировать выполняемые операторы и инициализацию текстовых переменных, имея только последние. При использовании интерпретируемого языка, такого как BASIC, REXX или Perl, можно в генераторе указать не только авторские пометки, но и дополнительные команды. Какой простор для творчества! И важна не сама программа, а организация своей работы для достижения необычного результата.

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

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