Самый большой диван, который можно передвинуть за угол

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

Если вы когда-либо переезжали в новый дом, то знаете, как сложно протащить громоздкую мебель по узким коридорам или огибать неудобные углы. Математики тоже пытаются решить эту задачу с 1966 года, когда Лео Мозер сформулировал её количественно. Допустим, вам нужно переместить двумерный предмет — ваш диван (без учёта его высоты) — по Г-образному коридору. Для простоты предположим, что ширина коридора составляет одну единицу. Каков размер самого большого предмета, который не застрянет?

Достаточно просто найти различные фигуры, которые можно использовать для маневра в 90-градусном углу коридора. Квадрат со стороной 1 подойдёт. Также подойдёт полукруг с радиусом 1 (и площадью π/2, или примерно 1,57). Но такие фигуры относительно малы. Задача о передвижном диване, как её вскоре стали называть, потребовала от математиков поиска более хитроумных решений.

В 1992 году Джозеф Гервер из Ратгерского университета предложил особенно остроумную криволинейную фигуру с площадью приблизительно 2,2195. Математики подозревали, что она отвечает на вопрос Мозера. Но доказать это им не удалось.

Теперь это удалось молодому исследователю, получившему докторскую степень. В 119-страничной статье Джинон Бэк из Университета Ёнсе в Сеуле показал, что диван Gerver — самая большая конструкция, которую можно успешно пронести через коридор.

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

Возможно, ещё более интригующим является то, что диван Гервера, в отличие от более привычных форм, определён таким образом, что его площадь не может быть выражена через известные величины (например, число π или квадратные корни). Но для задачи о перемещении дивана — очень простого вопроса — это оптимальное решение. Результат показывает, что даже самые простые задачи оптимизации могут иметь неожиданно сложные ответы.

Диваны и телефоны

Первый значительный прогресс в решении задачи о передвижном диване произошел в 1968 году, всего через два года после того, как Мозер ее сформулировал. Джон Хаммерсли соединил две четверти окружности прямоугольником, а затем вырезал из него полукруг, образовав фигуру, напоминающую старый телефон. Его площадь составила π/2 + 2/π, или приблизительно 2,2074.

Хаммерсли также показал, что любое решение задачи может иметь площадь не более $latex 2sqrt{2}$, или около 2,8284.

Пару лет спустя Джервер, тогда аспирант Калифорнийского университета в Беркли, узнал об этом вопросе. «Другой аспирант рассказал мне об этой задаче и бросил мне вызов, поставив передо мной задачу найти ответ», — сказал он. «Он ни словом не обмолвился о том, что она не решена. Поэтому я размышлял над ней несколько дней. В конце концов, я вернулся к нему и сказал: „Ладно, я сдаюсь. Где решение?“ Но он отказался мне сказать! Он сказал: „Просто продолжай думать. У тебя получится“».

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

Диван Джервера был очень похож на телефон Хаммерсли, но его было гораздо сложнее описать, поскольку он состоял из 18 различных деталей. (Как выяснилось, Бен Логан, инженер из Bell Labs, независимо открыл ту же форму, но так и не опубликовал свою работу.) Некоторые детали представляли собой простые отрезки прямых и дуги. Другие были более необычными и их было сложнее описать.

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

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

В следующем году Ромик и Йоав Каллус с помощью компьютерных технологий снизили верхнюю границу площади дивана, предложенную Хаммерсли, приблизив её к нижней границе, предложенной Гервером. Однако полностью устранить разрыв им не удалось. Требовалась новая идея.

Пространство диванов

Вскоре после поступления в аспирантуру Мичиганского университета в 2016 году Бэк взял четырёхлетний отпуск, чтобы отслужить в армии Южной Кореи (что является обязательным требованием для граждан мужского пола). В это время он столкнулся с проблемой передвижного дивана, о которой написал в своём блоге. По его словам, сначала работа над ней «была способом отвлечься от повседневной работы». Но вскоре он начал думать об этом более серьёзно. У него появилась идея, как доказать, что диван Джервера — решение, но ему ещё предстояло уточнить множество деталей. Вернувшись в аспирантуру в 2021 году, он решил посвятить себя этой проблеме.

Обычно аспирант по математике выбирает себе научного руководителя, который затем поручает ему задачу. Но Бэк был полон решимости заняться задачей о передвижении дивана. Это затрудняло поиск научного руководителя; никто в Мичиганском университете не считал, что у него есть необходимые знания. Но в конце концов Бэк обратился к Майклу Зиву, специалисту в отдалённой области алгебры. Он согласился. «Я никогда раньше не давал советов человеку, настолько далёкому от моих знаний», — сказал Зив. «Но я готов консультировать студентов практически по любым вопросам».

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

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

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

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

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

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

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

Одного этого было недостаточно для решения задачи о передвижении дивана. Но Бэк также определил Q таким образом, что для дивана Жервера функция давала не просто верхнюю границу. Её выходное значение было в точности равно площади дивана. Поэтому Бэку оставалось лишь доказать, что Q достигает максимального значения, когда на входе находился диван Жервера. Это означало бы, что диван Жервера имел наибольшую площадь среди всех возможных диванов, что и делало его решением задачи о передвижении дивана.

Именно здесь определение Q, данное Беком, стало ещё более важным. Он всё настроил так, чтобы Q вёл себя определённым образом — по сути, как простая парабола. Найти максимальное значение такой функции относительно легко. В данном случае Беку удалось показать, что максимизация Q даёт ему форму, удовлетворяющую определённому набору условий, и что уравнения, определяющие диван Жервера, также удовлетворяют этим условиям.

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

Доказательство, которое всё ещё проходит рецензирование, предлагает новый подход к задачам оптимизации. Оно объединяет методы из разных областей математики, делая невероятно сложную задачу разрешимой — и всё это без помощи компьютера. «Тот факт, что Джин смог сделать это без компьютеров, впечатляет», — сказал Зиве. «Это показывает, что существуют действительно важные новые идеи».

Всё это радует Гервера, даже спустя более 30 лет после того, как он предложил своё решение. «Мне уже 75», — сказал он. «Мне повезло, что я дожил до того, чтобы увидеть, как кто-то наконец решил эту проблему».

Источник: www.quantamagazine.org