Зиммерманн-2

[Pavlovsky]

Вы писали ещё что-то про матрицу инцидентности. И писали ещё о двух решениях 20:23, что они не изоморфны друг другу.

Когда я это писал неявно подразумевал свое определение изоморфизма.
Два решения изоморфны, если изоморфны их матрицы инцедентности.

Давать определение изоморфизма матриц нет необходимости, есть общеупотребительное опредление.

[omega]

Всё ясно. Ваши ответы поняла так: иди сама ищи все определения. Тут тебе никто их давать не собирается.

Спасибо.

У вас своё определение изоморфных конструкций, у меня своё... Далеко пойдёт наша наука! Если полиция не остановит

[Pavlovsky]

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

Этого мало.

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

Как то в такой постановке она выглядит совсем не двойственной, а вариантом основной задачи.

У вас воё определение изоморфных конструкций, у меня своё

Я свое определение озвучил. Когда вы озвучите свое определение изомрфизма решений, настанет время договариваться, какие решения будем считать изоморфными.

[Pavlovsky]

Kendrick Boyd (второе место) дал описание своего алгоритма.

Все лидеры отписались.

Orchard Planting - Top N
28 39 Dieter Gehrke @ 07:47:29pm on 12-15-2011
29 41 Dieter Gehrke @ 07:47:43pm on 12-15-2011
30 44 Natalya Makarova @ 08:47:31am on 12-28-2011
31 46 Natalya Makarova @ 08:48:30am on 12-28-2011
32 48 Natalya Makarova @ 08:48:55am on 12-28-2011
33 50 Natalya Makarova @ 08:49:17am on 12-28-2011

Появилась возможность заносить рекордные результаты, несмотря на то что конкурс закончился. Воспользоался такой возможностью. Хотя эти рекорды на самом деле должны принадлежать Dieter Gehrke. Странный у него алгоритм. Способен выдвать уникальные рекорды, но не может посмотреть что творится рядом.

[omega]

Вот теперь полностью поняла то, что alexBlack тут сказал про параллельные пучки

Применила перспективное преобразование к конструкции, в которой 5 групп параллельных прямых, это решение 19:19, получено из конкурсного решения 18:17 (автор Mark Mammel):

Код: Выбрать все

(0,0),(6,0),(12,0),(12,9),(12,12),(12,18),(15,9),(15,15),(16,12),(18,6),(18,9),(18,12),(18,18),(20,12),(21,9),(24,0),(24,18),(30,18),(46/3,14)

всего 13 параллельных потенциальных прямых (4 точки на линии), но две параллельные прямые имеют уравнение вида y = -x + c, и в процессе преобразования они не повернулись! Во-о-о-т! Теперь поняла. И к ним присоединилась ещё одна прямая, которая вышла из бесконечности, она имеет уравнение y = -x + 3.
Это картинка после применения преобразования (4 точки пересечения ещё не добавлены; преобразование с p=q=1/3):



Теперь добавляю 4 точки пересечения четырёх пучков бывших параллельных прямых и получаю решение 23:11 (5 точек на линии)

Код: Выбрать все

(0,0),(2,0),(12/5,0),(12/8,9/8),(12/9,12/9),(12/11,18/11),(15/9,1),(15/11,15/11),(48/31,36/31),(2,2/3),(18/10,9/10),(18/11,12/11),(60/35,36/35),(21/11,9/11),(24/9,0),(24/15,18/15),(30/17,18/17),(138/97,126/97),(18/13,18/13),(3,0),(0,3),(3/2,3/2),(6/5,9/5)

Здесь имеем 3 параллельных потенциальных прямых (4 точки на линии). Применяю второй раз преобразование p=-q=0.1. В результате 3 параллельные прямые поворачиваются и пересекаются в одной точке. Получено решение 24:14 (5 точек на линии):

Код: Выбрать все

(0,0),(5/3,0),(60/31,0),(120/83,90/83),(4/3,4/3),(15/13,45/26),25/16,15/16),(15/11,15/11),(240/161,180/161),(30/17,10/17),(180/109,90/109),(45/29,30/29),(300/187,180/187),(105/61,45/61),(40/19,0),(20/13,15/13),(150/91,90/91),(690/491,630/491),(18/13,18/13),(30/13,0),(0,30/7),(0,30/7),(3/2,3/2),(60/47,90/47),(5,-5)

Кому известен больший результат для N=24 (5 точек на линии)?

[omega]

Выкладываю Приложение к статье "Orchard Planting Problem"

[img]/modules/file/icons/application-octet-stream.png[/img] contest3A.rar

[выложила его уже давно в теме "Успешное выступление на международном конкурсе", но решила и в этой теме выложить]

Вторую часть статьи пишу пока в черновике, очень много материалов. Начну, наверное, с решения смежных задач (3 точки и 5 точек на линии). Есть замечательные примеры применения перспективного преобразования. Потом задача Т. Уилкокса. Есть несколько задач, которые мне не по силам, например, метод решения задачи с 3 точками на линии, где применяются кубические параболы. Видела одну иллюстрацию - решение 19:52, на ней очень хорошо видны эти самые параболы. Покажу эту иллюстрацию:



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

Ещё, например, разобраться в алгоритмах лидеров конкурса. А ведь это очень интересно!

Кстати, по задаче Т. Уилкокса открыла тему
[url=http://e-science.ru/forum/index.php?showtopic=35623]http://e-science.ru/forum/index.php?showtopic=35623[/url]

и по задаче 5 точек на линии тоже
[url=http://e-science.ru/forum/index.php?showtopic=35661]http://e-science.ru/forum/index.php?showtopic=35661[/url]

Но пока, к сожалению, никто задачами не заинтересовался. Конкурс закончился и задачи все бросили

[omega]

Начала писать вторую часть статьи, она будет посвящена задаче с 3 точками на линии.
Несколько решений этой задачи уже были показаны в первой части работы.
Здесь было рассказано о построении решения 12:19.

Теперь на очереди решение 13:22. В книге М. Гарднера есть картинка этого решения. Оно тоже с одной удалённой точкой, одна группа параллельных прямых, 6 штук.



Но прежде чем применить к этой конструкции перспективное преобразование, надо нарисовать её в рациональных координатах. Рисуется ли? Начала рисовать, с ходу не получилось, две точки не лежат одновременно на 5 прямых. Надо думать. Конструкция очень интересная!

Из решения 12:19 легко получилось решение 13:21, но не максимум.

[omega]

Покажу, что у меня с ходу получилось для решения 13:22 (3 точки на линии).
Но сначала то, что должно получиться (рисунок уже показан в предыдущем посте), отметила на рисунке точки поярче и обозначила их:



Должно быть 12 точек и 16 готовых прямых (3 точки на прямой), ещё 6 параллельных потенциальных прямых (2 точки на прямой). В результате перспективного преобразования добавится одна точка и 6 прямых, получится решение 13:22. Конструкция, судя по картинке, симметричная.

Вот что у меня получилось в рациональных координатах:

Код: Выбрать все

(-9,0),(9,0),(-3,18),(3,18),(-3,72/7),(3,72/7),(-3,9),(3,9),(-27/5,54/5),(27/5,54/5),(-3/5,522/35),(3/5,522/35)

Конструкция у меня симметричная.
Это картинка данного решения:



12 точек имеются, но точки G и H не лежат на прямых CK и DL соответственно (эти прямые нарисованы сиреневым цветом), в результате двух готовых прямых не хватает, имеем только 14 готовых прямых; 6 параллельных потенциальных прямых имеются (нарисованы зелёным цветом).

Задача:
нарисовать данную конструкцию в рациональных координатах или доказать, что это невозможно.

В принципе, понимаю, как надо решать задачу. Выбрать какую-то точку (может, и не одну!) с неизвестными координатами, написать уравнения прямых, проходящих через эту точку (точки) и найти из полученной системы уравнений неизвестные координаты. Такова схема. Однако так просто, в лоб, это не получается.

Может, кто поможет?

[omega]

Выкладываю вторую часть работы "Orchard Planting Problem"

[img]/modules/file/icons/application-octet-stream.png[/img] orch2.rar

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

[Pavlovsky]

Наталия вы пишете.
>>Где-то, возможно, подробно описано построение этих конструкций, но я не нашла.

Построение описано в статье:
The Orchard Problem S. A. Burr, B. Grьnbaum and N. J. A. Sloane
[url=http://www2.research.att.com/~njas/doc/ORCHARD/orchard.html]http://www2.research.att.com/~njas/doc/ORCHARD/orchard.html[/url]

Эту статью мы уже обсуждали.

[url=http://e-science.ru/forum/index.php?s=&...st&p=328478]http://e-science.ru/forum/index.php?s=&...st&p=328478[/url]