- PVSM.RU - https://www.pvsm.ru -

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

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

Перевод поста Эда Пегга младшего (Ed Pegg Jr) "From Close to Perfect—A Triangle Problem [1]"
Выражаю благодарность за помощь в переводе Андрею Дудину [2].
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь [3].

В языке Wolfram Language [4] (доступном, скажем, в системе Mathematica) функция RootApproximant [5] позволяет найти замкнутую форму в виде алгебраического числа для некоторого приближённого числа, и эта функция позволила нам превратить приближенное решение задачи о разбиении квадрата на 50 подобных остроугольных треугольников с углами (45°, 60°, 75°) в точное.

Ясно, что квадрат можно разбить на треугольники (триангулировать), например, просто соединив его противоположные вершины. Известно, так же, что квадрат можно разбить на семь подобных треугольников разной площади или на десять остроугольных равнобедренных треугольников [6] (см. рис. ниже). Известны также классические задачи, связанные с разбиением квадрата на восемь остроугольных треугольников (см. рис. ниже), или на двадцать треугольников со сторонами, относящимися друг к другу как Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_1.png. На третьем чертеже (считая сверху) показано разбиение квадрата на подобные треугольники с углами (45°, 60°, 75°), но вы можете с легкостью заметить, что это решение не корректно, так как один из треугольников немного накладывается на другой.

In[1]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_2.gif

Out[9]=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_3.gif

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_4.gif

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_5.gif

Можно с легкостью найти разбиение квадрата на подобные прямоугольные треугольники. Но можно ли найти разбиение квадрата на подобные не прямоугольные треугольники? В своей статье “Tilings of Polygons with Similar Triangles [7]” (“Разбиение многоугольников на подобные треугольники”) (Combinatorica, 10(3), 1990 pp. 281–306), Ласкович (Laczkovich) доказал, что это возможно только для трёх видов треугольников с углами (22°30’, 45°, 112°30’), (15°, 45°, 120°) и (45°, 60°, 75°). Я прочёл эту статью и попытался найти в явном виде разбиение квадрата на подобные треугольники с углами (45°, 60°, 75°), но построение такого разбиения оказалось сложным, и у меня сложилось ощущение, что для решения этой задачи потребуется использовать тысячи таких треугольников. Во всех моих решениях присутствовали изъяны, аналогичные тому, что был показан выше, поэтому я решил организовать небольшое соревнование [8]: награда за найденное разбиение равна 200 долларов минус доллар за каждый треугольник в найденном решении.

Лью Бакстер начал (Lew Baxter) с тщательного изучения подхода Ласковича, и смог найти решение, использовав для этого 7 триллионов треугольников. Но он нашёл способ улучшить это решение и написал программу для поиска более оптимальных решений. Уже через несколько недель он получил решение, содержащие 198 треугольников, чего было бы достаточно для того, чтобы получить от меня приз в размере 2 долларов. Но он продолжил свои поиски и наконец пришёл к решению содержащему всего 64 треугольника. К сожалению, координаты всех вершин треугольников были найдены приближённо, хотя и с большой точностью. На тот момент казалось, что решение, которое я привожу ниже, оптимально и найти лучшего решения, ещё и в замкнутой форме, не удастся. На рисунке ниже вы можете видеть найденное разбиение для половины квадрата, ясно, что достаточно отразить это решение относительно диагонали квадрата, чтобы получить решение исходной задачи.

In[10]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_6.png

In[11]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_7.png

In[12]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_8.png

Out[12]=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_9.gif

Для построения точного решения по этому приближённому решению можно использовать функцию RootApproximant, которая ищет корень некоторого многочлена, который будет с заданной точностью аппроксимировать данное приближённое число. В геометрических задачах, подобных той, что рассматриваем мы, очень часто точное решение как раз представляет собой набор корней некоторых многочленов. Для рассматриваемой задачи, я попробовал следующее: с помощью функции RootApproximant были найдены возможные замкнутые формы для каждой из координат, которые затем были умножены на 4686 для того, чтобы избавиться от дробей. Все значения, как легко заметить, имеют вид Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_10.png, что кажется довольно обнадёживающим.

In[13]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_11.png

Out[13]=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_12.png

Ниже можно посмотреть на полученное решение, содержащее 64 треугольника.

In[14]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_13.png

Out[14]=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_14.gif

Затем, я получил новое сообщение от Лью — если поработать немного с треугольниками 6, 7, 21, и 22, то в итоге можно заменить семь треугольников всего на один.

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_15.gif

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

In[15]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_16.png

In[16]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_17.png

В итоге было получено решение, содержащее 50 треугольников. Неужели это точное решение? С помощью кода, приведённого ниже, вычислим углы всех треугольников.

In[17]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_18.png

In[18]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_19.png

Out[18]=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_20.png

Легко видеть, что каждый из треугольников имеет углы, равные в точности (45°, 60°, 75°), так что решение Бакстера в действительности точное. Теперь мы можем взглянуть на решение содержащее 50 треугольников.

In[19]:=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_21.png

Out[19]=

Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_22.gif

Таким образом, я должен Лью Бакстеру 150 долларов. Если вы когда-либо занимались проблемами численной оптимизации и поиск точного решения cложен и не понятен, возможно вам стоит попробовать использовать функции, вроде, RootApproximant в языке Wolfram Language.

Автор: OsipovRoman

Источник [9]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/programmirovanie/70322

Ссылки в тексте:

[1] From Close to Perfect—A Triangle Problem: http://blog.wolfram.com/2013/03/28/from-close-to-perfect-a-triangle-problem/

[2] Андрею Дудину: http://vk.com/id32506210

[3] здесь: http://goo.gl/3Vd1UV

[4] Wolfram Language: http://www.wolfram.com/language

[5] RootApproximant: http://reference.wolfram.com/mathematica/ref/RootApproximant.html?q=RootApproximant&lang=en

[6] остроугольных равнобедренных треугольников: http://mathworld.wolfram.com/notebooks/Dissections/SquareDissection.nb

[7] Tilings of Polygons with Similar Triangles: http://link.springer.com/article/10.1007%2FBF02122782

[8] соревнование: http://math.stackexchange.com/questions/44684/

[9] Источник: http://habrahabr.ru/post/238107/