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

Pavlovsky · Сообщение **Pavlovsky** » 27 дек 2011, 11:41

Я уже повернул.
Решение для двойственной задачи будет 84:46. После замены точек на прямые и наоборт получится N=46 L=84.

Приблизительная схема такая.
1) Строим для двойственного решения матрицу инцедентности точек прямым. Получается двудольный граф.
2) Далее в этой матрице точки считаем прямыми, а прямые точками. Строим по этой матрице решение с координатами. Моя процедура поворота параллельных прямых должна справится с этой задачей. Если ничего с двойственностью не напутал.

У меня была такая реализация, там искать не проще, чем в прямом случае.

Дык решение для двойственной задачи я уже нашел! Осталось по решению для двойственной задачи построить решение для конкурса.

Оптимизма добавляют контрольные цифры рекордов:
N=46 L=84(83)!
N=52 L=105(100)!
N=59 L=128(123)!

Вполне вписываются в рекорды полученные участниками конкурса. В скобках рекорд в конкурсе.

alexBlack · Сообщение **alexBlack** » 27 дек 2011, 11:48

Pavlovsky писал(а):Source of the post
Дык решение для двойственной задачи я уже нашел! Осталось по решению для двойственной задачи построить решение для конкурса.

Ну, если так...
Обратное решение просто получить. Прямую Ax+By+C = 0 в двойственном решении преобразуем в точку (A,B,C) в прямом. Я делал с ограничением C <> 0, поэтому оставалось только поделить на C и отбросить единичку.

Pavlovsky · Сообщение **Pavlovsky** » 27 дек 2011, 11:52

Обратное решение просто получить. Прямую Ax+By+C = 0 в двойственном решении преобразуем в точку (A,B,C) в прямом. Я делал с ограничением C <> 0, поэтому оставалось только поделить на C и отбросить единичку.

Так просто!!! Блин боюсь разочароваться. Потерплю до завтра.

omega · Сообщение **omega** » 27 дек 2011, 12:33

Pavlovsky писал(а):Source of the post
Блин торкнула супер-пупер идея.

Известно, что проективная геометрия обладает свойством двойственности. Двойственная задача, задаче конкурса будет звучать так:

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

Но ведь эта задача легко решается!

Ха! Идея двойственности была озвучена мной примерно месяц назад.
И вы тогда писали, что обратную задачу решать ничуть не проще, чем прямую. Запамятовали что ль? Могу найти этот ваш пост

Pavlovsky · Сообщение **Pavlovsky** » 27 дек 2011, 12:36

Берем квадрат mxm. Проводим через точки квадрата все вертикальные и горизонтальные линии. А также диоганальные линии (прямые и обратные). Тем самым через каждую точку будет проходить ровно четыре прямых.

Блин уже не получается. Возмем семейство вертикальных линий.

Уравнение этих линий будет $$X+C_i=0$$

, после преобразования получим точку $(\frac{1}{C_i},0)$ То есть все эти точки будут лежать на одной прямой.

omega · Сообщение **omega** » 27 дек 2011, 12:39

[quote=Pavlovsky в 325089 (deleted)]
Ссылку на теорему Брианшона я давал в этой ветке давным давно. Третий алгоритм пытался использовать теоремы Паппа, Дезарга, Чевы, Брианшона, Паскаля, Фано и т.п.. Увы так ничего не получилось.

Насчет двойственности тоже думал. Получается прикольная задача.

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

Как и все двойственные задачи они являются друг для друга верхней и нижней оценкой. Но получается, что двойственная задача ничуть не легче.
[/quote]

Вот он, ваш пост. Было это как раз месяц назад. Чувство времени у меня хорошо развито
И вот через месяц торкнула супер-пупер идея

Pavlovsky · Сообщение **Pavlovsky** » 27 дек 2011, 12:49

Возмем семейство паралелльных прямых $$AX+BY+C_i=0$$

после преобразования получаются точки $(\frac{A}{C_i},\frac{B}{C_i})$ Все эти точки лежат на одной прямой. То есть при решении двойственной задачи, появляется дополнительное условие в пучке паралелльных прямых должно быть не больше четырех прямых.

А если сначала к двойственному решению применить проективное преобразование? Все прямые перестанут быть паралельными. И только после этого применить преобразование переводящее прямые в точки?

omega · Сообщение **omega** » 27 дек 2011, 12:52

Никто ничего не сказал по поводу изоморфных конструкций.

Наверное, опять глупый вопрос ляпнула Да ещё и на конкурсе тоже его задала.

Ну, ладно, если глупый. А мне всё равно интересно! Вот сколько всего нашли принципиально различных (не изоморфных!) решений, скажем, для N=11?

Это все решения 11:6, полученные мной:

Сколько здесь не изоморфных решений?

По-моему, первое и последнее решения изоморфны, ещё изоморфны решения 4-6 (это решения полученные из одного интернетовского решения). Кстати, такое же решение выложено на конкурсе.

Pavlovsky · Сообщение **Pavlovsky** » 27 дек 2011, 12:56

Никто ничего не сказал по поводу изоморфных конструкций

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

omega · Сообщение **omega** » 27 дек 2011, 13:05

Что значит "договориться"? Разве понятие изоморфизма конструкций не определено? Вот даже вчера в словаре глянула, и там написано, что "изоморфный - отличающийся сходным строением кристаллов".

Я понимаю изоморфизм конструкцмй так: прямые и точки на прямых расположены одинаково, хотя углы и линейные размеры разные.

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

yourdomain.com