Programming: theory and practice by alexBlack

Задача: требуется посадить N деревьев (расположить N точек на плоскости) так, чтобы максимизировать количество прямых, на которых расположено ровно k точек. Причем на любой из прямых нельзя располагать более k точек.

Хороший обзор по истории этой задачи и некоторые решения можно найти у Мартина Гарднера^[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 и точка O построением, показанным на рисунке слева, задают пучок прямых (на рисунке эти прямые показаны красным цветом). В этот пучок входит и сторона треугольника (или, по-другому, точка пересечения таких прямых лежит на стороне треугольника). Это следствие теоремы Дезарга. Конечно же, таким образом можно построить и пучок параллельных прямых.

Возьмем треугольник 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↑Мартин Гарднер "Путешествие во времени".

2↑Lattice Plantations by George Jelliss

3↑A chinese webpage for the problem

Ссылки

25 декабря 2011

No comments

Вы можете оставить комментарий или задать вопрос