Как простая математика меняет ход | Журнал Кванта

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

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

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

Здесь есть забавная математическая задача о том, сколько места вам нужно, чтобы развернуть машину, и математики работают над ее идеализированной версией уже более 100 лет. Все началось в 1917 году, когда японский математик Соити Какея поставил задачу, немного напоминающую нашу пробку. Предположим, у вас есть бесконечно тонкая игла длиной 1. Какова площадь наименьшего участка, в котором можно повернуть иглу на 180 градусов и вернуть ее в исходное положение? Это известно как задача Какеи об игле, и математики до сих пор изучают ее варианты. Давайте взглянем на простую геометрию, которая делает задачу Какеи об игле такой интересной и удивительной.

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

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

Область, необходимая для поворота, представляет собой полукруг радиуса 1, площадь которого равна $latex A = frac{1}{2} pi r^2 = frac{1}{2} pi (1)^2 = frac{ 1}{2} пи = frac{pi}{2}$. Итак, мы нашли один регион, который работает.

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

Вы могли бы назвать это компасом Какеи: наша стрелка вначале указывает на север, но после вращения она оказывается в том же месте, но указывает на юг. Эта область представляет собой круг радиуса $latex frac{1}{2}$, поэтому ее площадь равна $latex A=pi r^2 = pi (frac{1}{2})^2 = pi frac{1}{ 4} =frac{pi}{4}$. Это половина площади нашего первого региона, так что мы добиваемся прогресса.

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

Область, вычерченная иглой с помощью этой техники, называется дельтовидной мышцей, и она тоже удовлетворяет требованиям Какеи. Для вычисления его площади требуется нечто большее, чем просто элементарная геометрия, которую мы здесь обсуждаем (помогает знание параметрических кривых), но оказывается, что площадь этой конкретной дельтоиды — той, которую охватывает отрезок линии длиной 1 — равна в точности $latex фрак{пи}{8}$. Теперь у нас есть еще меньшая область, в которой мы можем повернуть иглу Какеи вспять, и вас можно простить за то, что вы думаете, что это лучшее, что мы можем сделать. Сам Какея думал, что это возможно.

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

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

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

Поскольку площадь треугольника равна $latex A=frac{1}{2}bh$, площадь этого треугольника равна $latex A=frac{1}{2}, умноженная на 2, умноженная на 1 = 1$.

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

Площадь этой новой фигуры должна быть меньше исходной, поскольку теперь части треугольника перекрываются. На самом деле вычислить площадь фигуры несложно: она составляет всего три четверти квадрата стороны 1, поэтому площадь равна $latex A = frac{3}{4}$, что меньше площади фигуры. треугольник, с которого мы начали.

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

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

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

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

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

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

Остаются только повороты в углах N-образной формы.

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

Формула площади сектора круга: $latex A = frac{theta}{360} pi r^2$, где $latex theta$ — это угол сектора в градусах. Независимо от высоты N, радиус сектора всегда будет равен 1: это длина иглы. Но по мере того, как буква N становится выше, угол уменьшается, что приводит к уменьшению площади сектора. Таким образом, вы можете сделать дополнительную область настолько маленькой, насколько захотите, растянув N настолько, насколько вам нужно.

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

В этой обновленной области игла по-прежнему может поворачиваться на полные 90 градусов, как и раньше, но теперь это происходит в два этапа. Сначала игла поворачивается на 45 градусов и выравнивается с вертикальным краем слева. Затем он движется по букве N, чтобы добраться до другой стороны. Как только он окажется там, остальные можно будет повернуть на 45 градусов.

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

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

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

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

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

Упражнения

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

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