Главная | Эксперименты | Утилиты | Компоненты | Что почитать | Контакты |
|
Хороший обзор по истории этой задачи и некоторые решения можно найти у Мартина Гарднера[1]. Гарднер пишет: "При k=3 задача не только становится нетривиальной, но и оказывается связанной с такими важными математическими понятиями, как сбалансированные блочные планы, тройки Киркмана-Штейнера, конечные геомерии, эллиптические функции Вейерштрасса, кубические кривые, проективные плоскости, коды с исправлением ошибок и многими другими.". В конце главы Гарднер приводит еще одну интересную задачу - найти наименьшую прямоугольную шахматную доску, на которой решение задачи о деревьях можно промоделировать, расставив пешки. Обзор и решение этой задачи приведены в журнале "Games and puzzles"[2]. В этом году начал работать новый контест Infinite Search Space. Первой задачей как раз была предложена задача о посадке деревьев для k=4 и N от 11 до 60 с дополнительным условием - координаты точек должны быть целочисленными. То есть то-же самое представление задачи на шахматной доске, но без ограничения размеров доски. В этом соревновании я занял только 12-е место, поэтому не буду рассказывать про свой алгоритм поиска. Интересней будет прочитать про решение победителя. Однако есть несколько любопытных моментов, связанных с решением этой задачи, которые я хотел бы здесь упомянуть. Во-первых о решении 20:23 (20 точек, 23 прямых). Решение было получено Du,Zhao Hui и приведено на форуме китайского сайта[3]. Посмотрим как это решение можно получить в рациональных координатах. Начнем с теоремы Дезарга. - Возьмем треугольник ABC (не равнобедренный), выберем произвольно прямую l , параллельную стороне BC и, начиная от этой прямой, построим серию параллельных прямых a, b, c . Последние две прямые дадут нам прямые d и e, которые, в свою очередь, дадут на стороне BC две точки D и E:
Для каждой из точек D и E мы можем построить свой пучок прямых. По одной прямой из этих пучков у нас уже есть. Остальные легко строятся. Здесь нам потребуется даже не построить пучок прямых, а всего лишь провести пару-тройку прямых через уже известные точки. На рисунке ниже выделена только центральная часть предыдущего рисунка. Добавлены две прямых из зеленого пучка и одна из красного. Точек B, C, D, E здесь не видно, но представьте, что это нарисовано на большом листе бумаги.
Осталось выбрать точки и соединить их. Получаем 20 точек и 23 прямых - тот самый рисунок с китайского сайта:
По сравнению с этим построением совсем просто строится второе решение с того же сайта. В равнобедренном треугольнике берем прямую, параллельную основанию (зеленая на рисунке). Остальные прямые и точки легко получить по первым вспомогательным прямым (на рисунке показаны синим цветом).
Конечно, просто - я имею в виду по готовому решению, когда уже известно расположение точек и прямых. Для получения этих решений китайскими товарищами была проделана огромная работа, мне же оставалось получить рациональные координаты точек для найденных решений. Кстати, на сайте приведено много решений для разного количества точек и прямых. Некоторые из них уже даны с координатами, некоторые не имеют решения в рациональных числах. Есть даже интересное решение 15:13 с мнимым параметром. Немного о проективной геометрии. Используя перспективные преобразования можно спроецировать рисунок так, что параллельные прямые будут пересекаться. Или, если рассматривать рисунок на проективной плоскости, параллельные прямые всегда пересекаются, но точка их пересечения лежит в бесконечности. Каждый пучок параллельных прямых имеет собственную точку пересечения и все эти точки образуют прямую, также лежащую в бесконечности. Если рассматривать точки в трехмерных нормализованных координатах, то перспективное преобразование - это умножение на матрицу:
Здесь p и q - задают так называемые точки схода на прямых OX и OY соответственно. Значения, равные нулю задают точки схода в бесконечности. Можно посмотреть на это преобразование по-другому - в афинной плоскости это преобразование эквивалентно делению координат точки (x,y) на коэффициент (px+qy+1). Например, для исходного рисунка мы имеем три пучка параллельных прямых
после преобразования получаем три точки пересечения этих пучков:
Таким образом можно сразу взять четыре точки в бесконечности и соответствующие им четыре пучка параллельных прямых. Ищем нужную нам конфигурацию. При этом на выбранных пучках параллельных прямых должно быть не более 3-х точек, на остальных прямых - не более 4-х. Полученную конфигурацию подвергаем преобразованию и получаем четыре дополнительные точки и еще одну прямую. Решения, показанные ниже, получены именно таким способом. Слева приведены некоторые мои решения. Для каждого решения даны координаты в двух видах - первая строка - с точками в бесконечности и, второе, преобразованный рисунок без точек в бесконечности. 1↑Мартин Гарднер "Путешествие во времени".
Ссылки
|